Problems & Puzzles:
Puzzles
Puzzle 135.
Partitions
into distinct primes with maximum product
In the well known R. K. Guy's book (UPiNT), the article
F19 p. 258 entitled "Partitions into distinct primes with maximum product" poses several interesting
questions
"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 having 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
Product = 39888810865593690, Parts = 14
319 = 3 + 5 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
Product = 43920698756320815, Parts = 13
"... the partition with the smaller number of parts gives the largest possible product"
And asks "is this the least counterexample? Can the cardinality of the two sets differ by an
arbitrary large amount"
As far as my approach is correct & exhaustive my answer to the first question is affirmative:
319 is the least counterexample.
Moreover I claim that:
a) the next counterexample is N = 372
372 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 + 23 + 29 + 41 + 43 + 47 + 53 + 59
P= 1676338579035930810, Parts = 15
372 = 3 + 5 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53
P= 2327797034085003195, Parts = 14
b) the first prime counterexample is N=1063
1063 = 2 + 3 + 5 + 7 + 11 + 13 + 17 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53
+ 59 + 61 + 67 + 71 + 73 + 83 + 89 + 97 + 101
P= 155138150805128155163266700120258070, Parts = 24
1063 = 3 + 5 + 11 + 13 + 17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47 + 53 +
59 + 61 + 67 + 71 + 73 + 79 + 83 + 97 + 101
P= 186887932871988251123646321733954545, Parts = 23
c) between 372 & 1063 there are other five (5) counterexamples.
(BTW, all the counterexamples from 319 to 1063 are such that the
cardinality of both sets differ by 1)
Questions:
1. Can you find the five (5) counterexamples between 372 & 1063
2. Can you find 3 more prime
counterexamples?
3. Can you find the least example such that the cardinality of the two sets
involved differ by more than 1 (if it exists)
Solution
Blessed amnesia!
Jud McCranie reminded to me that this question
was already posted as Problem 6 in my own pages!!
As a matter of fact Jud himself solved more
than two years ago (August 1998) the first of my claims (319 is the least
counterexample). Moreover, now he (Jud) found that Adam Atkinson
had published the complete sequence (A53020) of values asked in my
question 1 of this puzzle.
As a byproduct of the Atkinson's work it results
also that my approach (code) to produce counter examples has a logical
error that produced the all the true solutions plus other false solutions.
As a matter of fact 1063 is NOT a solution and between 372 & 1063
there are only four (4) and not five (5) counterexamples.
The Atkinson's approach and code is explained in
the link of his published sequence.
I have no excuse for solving this problem late, twice
and bad. Sorry folks!
***
But not all was tragedy in this act. In the meanwhile
met the Atkinson's email quotes. I really feel bad if I do not
share them:
"I never could get the hang of Thursdays"
"You got a light, mac? No, but I've got a dark
brown overcoat."
"Our royal family died out because the last
queen was impregnable" "No, she was unbearable."
"No, she was inconceivable."
In a more technical line he has sent to share its code.
Just ask for it and I will email it?
***
Adam has sent (24/4/01) his latest results of
counterexamples calculated with a newer program in faster machine. His
larger counterexample is 117783, and all of them show a difference of
cardinality of the two sets of primes of value equal to 1.
***
