Determine the maximum value that is obtained by multiplying together a set of positive integers which are all different and whose sum is 100.
Initial thoughts:
The number of integers cannot be 14 or more because the sum from 1 to 14 is 105, which is more than 100.
With some trial and error I found this, and it seemed to be optimal:
[2,3,5,6,7,8,9,10,11,12,13,14]
Product: 21794572800
Confirmed with a program. Here N is the number of numbers in the list; hi is the largest of the numbers. For the next N, there is no need to test integers larger than the value of hi for the prior N.
The winner is with N=12, and hi=14. This is the same list as was found with trial and error.
For N=13, the product is smaller.
product N hi list
[387504, 4, 27, (23, 24, 26, 27)]
[3160080, 5, 22, (18, 19, 20, 21, 22)]
[20563200, 6, 20, (14, 15, 16, 17, 18, 20)]
[110270160, 7, 18, (11, 12, 13, 14, 15, 17, 18)]
[518918400, 8, 16, (9, 10, 11, 12, 13, 14, 15, 16)]
[1937295360, 9, 16, (7, 8, 9, 10, 11, 12, 13, 14, 16)]
[5448643200, 10, 15, (5, 6, 7, 8, 9, 11, 12, 13, 14, 15)]
[15567552000, 11, 15, (4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15)]
[21794572800, 12, 14, (2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)]
[17435658240, 13, 14, (1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14)]
-------------
import math
from itertools import combinations_with_replacement
from itertools import combinations
def product(aList):
if len(aList)==0: return 1
else: return aList[0]*product(aList[1:])
def groups(smallest,n,g,listing=False):
""" Ways to divide n items into g groups, when the smallest number of items in a bin is 'smallest'; returns the full list of ways if the 4th parameter is True, or just the count if False. """
poss = [i for i in range(smallest, n+1)]
ans = []
for comb in combinations_with_replacement(poss,g):
comb = list(comb)
if comb != sorted(comb):
continue
if sum(comb) != n:
continue
ans.append(comb)
if listing:
return ans
else:
return len(ans)
nums = [n for n in range(1,28)]
top = 100
for bins in range(4,14):
bestprod = 10
besttuple = [1]
for comb in combinations(nums, bins):
if sum(comb) != 100:
continue
if product(comb) > bestprod:
bestprod = product(comb)
besttuple = comb
print([bestprod, bins, max(besttuple), besttuple])
|
|
Posted by Larry
on 2025-03-11 16:53:37 |
Solution
