Problems & Puzzles: Problems
Problem 6.- Primes and partitions
J, Riddell & H. Taylor asked if, among the partitions of n into distinct primes, the one having the maximum product of parts is necessarily one of those with the maximum number of parts, but Selfridge answered this negatively with the example :
319 = 2+3+5+7+11+13+17+23+29+31+37+41+47+53
319 = 3+5+11+13+17+19+23+29+31+37+41+43+47
As you can see the partition with the small number of parts gives the largest possible product.
Is this the least counterexample ?
(p. 259, Ref 1)
The ink of the 6th Edition was still fresh when Jud McCranie came up (Saturday 1st August, 1998) with the solution of this problem.
According to a code developed by McCranie, the answer is that there is not any other small number than the found by Selfridge (319) where "the partition with the small number of parts gives the largest possible product"
His program reached to the first solution at 319 "in just a couple of minutes". Very soon he found the next two other cases : 372 and 492. Jud stopped his search at n=666 because "the program is bogging down" due to the increasing number of combinations that has to deal with.
This are his results for n= 372 and 492
"(terms, followed by the log of the product of the terms)
16 terms: 3+5+11+13+17+19+23+29+31+37+41+43+47+53+59+61
No others for n <= 666."