When I was in college there was a term for such kind of activities - “D!” - pronounced as “D not”. which was an acronym for “Dhandaa not” - meaning someone who has nothing better to do. The following can be classified as a pure "D!" activity!
The Problem 50 in Project Euler is stated as
The Problem 50 in Project Euler is stated as
The prime 41, can be written as the sum of six consecutive primes:
41 = 2 + 3 + 5 + 7 + 11 + 13
This is the longest sum of consecutive primes that adds to a prime below one-hundred.
The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.
Which prime, below one-million, can be written as the sum of the most consecutive primes?
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”.
On the other hand, the smallest prime with SCP number 3 is 1151.
The smallest prime with SCP number 5 is 34421.
Below 1 million, there is only one prime with SCP number as 6, and that is 442019.
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.
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.There are many 3 digit primes that have SCP number more than 1. For example
So SCP(41) = 2
983 = 23 + 29 + … + 89 + 97 (17 primes)There are no 3 digit primes with SCP = 3. But There are 2 primes with SCP number as 4.
983 = 47 + 53 + … + 101 + 103 (13 primes)
So SCP(983) = 2.
311 = 11 + 13 + .. + 43 + 47 (11 primes)The other prime is 863.
311 = 31 + 37 + … + 53 + 59 (7 primes)
311 = 53 + 59 + 61 + 67 + 71
311 = 101 + 103 + 107
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)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
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
988321 = 113 + 127 + … + 3919 + 3923And it’s NOT the answer to the Project Euler problem. The SCP number for the answer is just 3.
This has a whopping 515 consecutive primes !
Below 1 million, there is only one prime with SCP number as 6, and that is 442019.
442019 = 419 + 421 + … + 2617 + 2621 (301 primes)That’s a special number. There is no prime below 1 million with SCP = 7.
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
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.
Is 1 not a prime number? If it is prime then
ReplyDelete1 + 2 + 3 = 6 (does not add up to a prime number) !
Will you please explain?
Kedar,
Delete1 is not considered a prime number for good reasons. Any integer > 1 can be expressed as UNIQUE product of primes. For example, 21=3 x 7. If you consider 1 as prime, then this would never be true, as 21=3x7x1 and 21=3x7x1x1x1x1 etc. Multiplying by 1 is pointless. So considering 1 as non-prime, makes many theorems useful.
Secondly, not every addition of consecutive primes gives a prime. For example,
2 + 3 = 5 (prime)
2 + 3 + 5 = 10 (non-prime)
2 + 3 + 5 + 7 = 17 (prime)
If you keep adding consecutive primes, you will get alternatively odd and even numbers. Since even numbers except 2 are not primes, at least half of the sequences of consecutive primes won't generate a prime.
Hope that helps.
This is beautiful. What would the largest set be if you restricted those sets to a prime number of prime numbers? What would the largest set be then?
ReplyDeleteSmallest example is 5=2+3
All are prime and so is the size of the set.
Thanks for the interesting idea. I have added some more analysis in the follow up post at http://abhayavachat.blogspot.com/2014/09/sum-of-consecutive-primes-part-2.html
Delete