Puzzle 46.- Primes expressible as sum of consecutive primes in K ways.

I have found that the prime 34421 is expressible as a sum of consecutive primes in five (5) ways :

34421 = 269 + … + 709 (71 primes)
34421 = 1429 + … + 1571 (23 primes)
34421 = 3793 + … + 3853 (9 primes)
34421 = 4889 + … + 4937 (7 primes)
34421 = 11467 + … + 11483 (3 primes)

First of all, I need to make a correction: 34421 is expressible in six distinct ways as a sum of consecutive primes - and not in five ways as I stated - just because 34421 is prime and then 34421 is the sum of 71 or 23 or 9 or 7 or 3 or 1 consecutive primes.

This is congruent with the function f(n) defined, and the questions posed, by Leo Moser (see C2, p. 108, R.K. Guy's book). According to his function then f(34421) = 6

This week I made another search for the same subject, but now I decided to eliminate the condition of n to be a prime number, and I got two nice surprises f(130638)=6 and f(218918) = 7.

218918 =
= 3301 + … + 3769    (62)
= 4561 + … + 4957    (46)
= 5623 + … + 5897    (38)
= 7691 + … + 7937    (28)
= 9851 + … + 10069   (22)
= 13619 + … + 13729   (16)
= 18199 + … + 18289   (12)

I don't have at hand my first code, the one used when I got f(34421) = 6 but or I had a bug in my original program or I simply ignored the n composite numbers. Now I have suspended my search in n = 300,000.

Today I'm more confident that f(n)=k has solution for higher and higher values. C'mon my friends!... Let's produce the least solutions for k = 8, 9 & 10.

Jean Charles Meyrignac has gotten (8/4/2000) the following results: f(442019)=7 & f(3634531)=8, f(48205429) = 9 being 442019, 3634531, 48205429 all prime numbers!.... Congratulations Jean Charles!...

The problem of this method is that since I don't store the decompositions, we need to re-compute the sums for the full decomposition. But the advantage is that we have no memory limitation for the sums !The source file is compilable with Visual C++ 6"

Jean-Charles sent his code to Nuutti Kuosa - who has a faster PC - to run his code with the hope of finding the least solution for f(n)=10. Nuutti found 8 more solutions for f(n)=9, but no one solution smaller than 710000000 for f(n)=10. His largest solutions was f(460421347)=9 and f(556259425)=9, being 460421347 prime.

"I have been running that puzzle program since you mailed it to me and here is current log...I don't know if there is bug or there is quite large gar, because it was about two weeks when I found last 9 result...", says Nuutti to Jean-Charles.

Jud McCranie has verified the Nuutti solutions and has gotten other 12 solutions for f(n)=9 beyond 710,000,000 up to 1,500,000,000 without any solution for f(n)=10:

This past week worked on puz46. Attached are the results of systematically searching up to 260 billion. 7 years of Moore's Law definitely helps!

Found 5722 values for f(x)=9 (2107 were prime, 3615 not prime).

Found 300 values for f(x)=10 (119 were prime, 181 not prime).

Found 13 values for f(x)=11 (8 were prime, 5 not prime).

Found 1 values for f(x)=12 (it was prime).

Only soln. found with 12 ways:

There were 12 ways found to sum to 166400805323 which is prime
166400805323 = 55466935091 + ... + 55466935123 (3)
166400805323 = 18488978293 + ... + 18488978441 (9)
166400805323 = 3025468583 + ... + 3025469801 (55)
166400805323 = 155650259 + ... + 155670083 (1069)
166400805323 = 135604109 + ... + 135627281 (1227)
166400805323 = 50227297 + ... + 50286373 (3311)
166400805323 = 29640257 + ... + 29735219 (5605)
166400805323 = 19365569 + ... + 19509173 (8561)
166400805323 = 6284627 + ... + 6688103 (25655)
166400805323 = 3188819 + ... + 3897083 (46977)
166400805323 = 429467 + ... + 2213353 (127483)

(The other results gotten by Wilfred available on request, CR)

Looks like each level requires finding typically around 20 of the previous level.

Note: A compact prime seive was used up to 82 billion. For larger N, the GMP big number library was used with 6 Miller-Rabins (slowing things down considerably). Fortunately only a small fraction of the summing involved Miller-Rabin tested primes.

Attached are the results (more stuff than you need, just for your interest). It is interesting that the density of X with f(X)>=9 seems to stay uniform (about 23 solutions per billion).

1st X with f(X)=10 is 1,798,467,197 which is prime (4,611,108,324 is the first non-prime with 10) - oh were they close

1st X with f(X)=11 is 12,941,709,050 which is not prime (36,154,343,837 is the first prime with 11)

1st X with f(X)=12 is 166,400,805,323 which is prime (only one found up to 260 Billion)

PS. Largest gap found out of all the 6036 solns with f(X)>=9 was the gap found by Nutti and Jean-Charles from 556,259,425 to 990,240,515 (a gap of 433,981,090). Smallest gap found was between 138,899,337,197 and 138,899,340,891 (a gap of only 3694)