Find a set of ...

[kemasa]

The question of a set of number whose sum = C with the maximum product.

n ___
__ \
max || Xi over all partitions (n): > Xi = C
i=1 /___

1) Start by considering a fixed value of n.

Maximize:

n
___
\
> Ln[Xi] Since Ln is monotonic increasing for increasing X
/___
i=1

Given:
n
___
\
> Xi = C
/___
i=1

1 \
Lagrange multiplers => --- = /\ forevery i
Xi

n
___
. \ 1 \ n
. . > --- = C => /\ = ---
/___ \ C
i=1 /\

+-------------------------+
| C |
| Xi = --- for every i |
| n |
+-------------------------+

2) For each n, max is:

n
___
\ C C
> Ln[---] = nLn[---]
/___ n n
i=1

C C -1
To maximize xLn[---] : Ln[---] + x(---) = 0 {Zero}
x x x

C C C
=> Ln[---] = 1 --- = e x = ---
x x e

Then since x (or n) must be an integer, test integer values above and below x

C
3) C = 100, --- = about 36.7
e

=> n = 37

The Graphs are just to show that this is really true.

Graph of [x Ln[100/x]] for x = 1 to 100

| *************
| **** ******
| *** ****
30 *** ****
| ** ***
| * ***
| ** **
| * ***
20 * **
| * **
| * **
| ** **
10* *
|* **
|* **
| **
| **
0-------------20--------------40-------------60-------------80--------------

Graph of [x Ln[100/x]] for x = 36 to 37

| ********************
| ******* *******
| *****
| *****
36.786 ***
| ***
| ***
| ***
36.784 **
| ***
| **
| **
36.782 **
| **
| **
| **
36.78
36-----------------------------------36.5----------------------------------37

Graph of Ln[100/x]-1 for x = 1 to 100

|
|*
3*
|*
|**
| *
2 *
| **
| **
| **
1 ***
| *****
| *****
0-------------20--------------40-------------60-------------80--------------
| *********
| ************
| ****************
-1 **********

Graph of Ln[100/x]-1 for x = 1 to 100

|**
0.02***
| ****
| *****
| ****
| *****
| ****
0.01 *****
| *****
| ****
| *****
| ****
| ****
06-----------------------------------36.5----------------------------------37
| *****
| ***
| *****
| ***

This work re-printed with permission, I am not that into math do
to such a thing.

Kemasa.

[Jeff Baron]

In article <32...@sdcc3.UUCP> kem...@sdcc3.UUCP (kemasa) writes:

>
>The question of a set of number whose sum = C with the maximum product.
>

Try to do this when the set of numbers equal to C can be composed only of
integers, ie. find the set of integers whose sum is equal to C and
whose product is as large as possible.

--
Jeff Baron
{allegra,genrad,ucbvax}!harvard!baron