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 by-product 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.

***

 Records   |  Conjectures  |  Problems  |  Puzzles