I had no idea that consecutive primes can be added to get another prime ! That’s simply beautiful.
Once you have a prime number generator, solving problems related to prime numbers becomes easier, if not easy. The best generator is of course the
Sieve Of Eratosthenes, for which you can find the code
here.
Using it, you can generate primes up to the required limit, and implement a brute force algorithm. Just have a loop iterating over the list of primes, and keep adding up all the primes starting from that position. The sum is prime if it exists in our list. Note it down and how many primes were added to get it. Keep only the sum that was generated using more number of primes than the last one.
Well, what’s the fun in doing only that ? So I just added a data structure to keep track of which primes can be generated by adding a set of consecutive primes, and if there are more than one set of consecutive primes that add up to a prime, keep a track of that as well. The results are fun to analyze.
It’s not that just 2 or 3 primes can be added to get another prime, some of the primes below 1 million, can be constructed by adding over 500 consecutive primes. More, some of these can be constructed using more than one list ! Astonishing.
The number 41, mentioned in the problem, can also be written as sum of a different set of consecutive primes,
41 = 11 + 13 + 17. That’s the only 2-digit prime that can be obtained via adding more than one set of consecutive primes.
So what other primes can be written as sum of more than 1 set of consecutive primes ? To save typing, I am going to define a new function
SCP for “sum of consecutive primes”.
SCP(n) = the number of sets of consecutive primes that can be added to get n.
So SCP(41) = 2
There are many 3 digit primes that have
SCP number more than 1. For example
983 = 23 + 29 + … + 89 + 97 (17 primes)
983 = 47 + 53 + … + 101 + 103 (13 primes)
So SCP(983) = 2.
There are no 3 digit primes with
SCP = 3. But There are 2 primes with
SCP number as 4.
311 = 11 + 13 + .. + 43 + 47 (11 primes)
311 = 31 + 37 + … + 53 + 59 (7 primes)
311 = 53 + 59 + 61 + 67 + 71
311 = 101 + 103 + 107
The other prime is 863.
On the other hand, the smallest prime with
SCP number 3 is
1151.
The smallest prime with
SCP number 5 is
34421.
34421 = 269 + 271 + … + 701 + 709 (71 primes)
34421 = 1429 + 1433 + … + 1567 + 1571 (23 primes)
34421 = 3793 + 3797 + … + 3851 + 3853 (9 primes)
34421 = 4889 + 4903 + … + 4933 + 4937 (7 primes)
34421 = 11467 + 11471 + 11483
Below one million, the largest prime with
SCP number as 5 is
988321. One of the set of consecutive primes that add up to that number is
988321 = 113 + 127 + … + 3919 + 3923
This has a whopping 515 consecutive primes !
And it’s NOT the answer to the Project Euler problem. The
SCP number for the answer is just 3.
Below 1 million, there is only one prime with
SCP number as 6, and that is
442019.
442019 = 419 + 421 + … + 2617 + 2621 (301 primes)
442019 = 7529 + 7537 + … + 8011 + 8017 (57 primes)
442019 = 13229 + 13241 + … + 13553 + 13567 (33 primes)
442019 = 17569 + 17573 + … + 17791 + 17807 (25 primes)
442019 = 49069 + 49081 + … + 49139 + 49157 (9 primes)
442019 = 147331 + 147341 + 147347
That’s a special number. There is no prime below 1 million with
SCP = 7.
What’s the point of all this ? Not much, except that prime numbers are fascinating. If you want to know more about the mathematical research done on them, I highly recommend reading
Prime Obsession. Don’t let the topic turn you away from reading it. It’s a very easy book to read, and is enormous fun. I know that’s hard to believe, but it really is, and that’s why it’s one of my all time favorite books.
UPDATE : Added some more analysis in a
follow-up post.