Conference dypss1::brain_bogglers

So why isn't this solved yet, hmmmm?

I think that .1 is the key to the whole thing.  However, John missed one
simple algebraic step that would make it easier to see.  That is:

.1:	log k = log 17 - 1 = 1.833

is equal to:

	k = e^(log 17) / e^1

	k = 17 / e

The maximum solution is then = e ^ (17 / e) = 520.0632..

For any N the max is = e ^ (N / e).  This implies that you want each
term in your approximation to be as close to "e" as possible.  And 
you want INT(N/e + 1/2) terms. This is the recipe for integer and
fraction solutions.

INTEGER SOLUTION

Rounding k (6.2539...) to the nearest integer 6 means that there should be
six terms. Each term should be as close to "e" as possible.  

Hence the 3*3*3*3*3*2 = 486 solution. 

FRACTION SOLUTION

There should be six terms with each being as close to "e" as possible.

Assume a denominator of 10:

(A)	28   28   29   28   28   29    516.926 E+6
	-- * -- * -- * -- * -- * --  = ----------- = 516.926
	10   10   10   10   10   10      1.0   E+6

This is better than the integer solution.  Try a denominator of 100:

(B)    	283   283   284   283   283   284   517.348 E+12
	--- * --- * --- * --- * --- * --- = ------------ = 517.348
	100   100   100   100   100   100     1.0   E+12

This is better still because each fraction in the series is closer to "e".

Example C shows how deviating slightly from "e" makes the max drop off.

(C)	28   28   28   28   28         516.311 E+6
	-- * -- * -- * -- * -- * 3  = ----------- = 516.311
	10   10   10   10   10           1.0   E+6

    But
    
      283   283   284   283   283   284
      --- * --- * --- * --- * --- * ---    is not an integer.
      100   100   100   100   100   100
    
    (You can obviously get as close as you like to 520... using this
    technique).
    
    Sorry, my fault for not being precise in .0, but I think Ellie realised
    this in .8 . The product of the fractions in question 2 must yield an
    integer, just as the product of integers would in question 1.
    
    Can you improve on
    
      9   9   4   4
      - * - * - * -  ?
      2   2   1   1
    
    Dick

    I posted a reply in .12 which totally missed the boat, so to save
    myself the embarrassment, I've set it hidden.
    
    Martin

    Re .11:
    
    >     (You can obviously get as close as you like to 520... using this
    > technique).
    
    I don't think so.  The fractions get closer to 17/6, not to e.  You
    could just jump to 17/6, and (17/6)^6 is about 517.35187.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

First, let's review...

> 1. Divide up the number 17 [or in general S] into smaller integers [actually
> I think Dick means +ve integers. Call them x_i, i=1..n] so that the product 
> [P] of these smaller numbers is as large as possible.

	Differentiation etc is irrelevant to this. But .3 got it...

	If any x_i >= 4, then split it into 2 & (x-2) which gives a larger or 
equal P for the same S. If any x_i = 1 then combine it with some other x_j to 
give a larger P for the same S. So we've just got 2's & 3's. Replace any 2*2*2 
by 3*3. Let S = 3q+r.

	If r = 0, then P = 3^q
	If r = 1, then P = 4*3^(q-1)
	If r = 2, then P = 2*3^q

	Problem solved.

>   2. Same thing, but you are allowed to divide into fractions.
>   eg. (9/2)*(9/2)*4*4 = 324.

	Much of the discussion has been about the solution where P is free
to be non-integral. Basically then, P = max[(S/n')^n', (S/n")/n"], where n'= 
ceiling(k) and n" = floor(k), and k = S/e.

	However, as clarified by .13...

>	The product of the fractions in question 2 must yield an
>    integer, just as the product of integers would in question 1.

	If we drop the requirement that the x_i in question 2 be rational,
then I think that continuity arguments can show that the maximum attainable
is P = floor(max[(S/n')^n', (S/n")^n"]) (*) This is nearly as well as we could 
do when P was non-integral.

	I think it's pretty easy to achieve the value of P shown in (*) with n-2
of the x_i rational. But the other two x_i would be quadratic.

	But with *all* x_i rational, and P integer, the world is more
diophantine and complicated. The value of P given in (*) nevertheless remains 
an upper bound.

	Given the diophantine nature of this problem, I think that the best way
forward is the kind of "local" approach that worked so well for question 1.

	With the original S=17 problem, (2, 2, 2, 5/2, 5/2, 3, 3) is
one suggestion. This yields P = 450, against the theoretical maximum of 517 
given by (*). However a better answer is (8/3, 8/3, 8/3, 3, 3, 3), which
delivers a scorching 512.

	I conjecture that this is the best answer for S=17. It could only be
beaten by a solution with n=6. [We know this from (S/n)^n considerations.] 

Cheers,
Andrew.