When I was in college there was a term for such kind of activities -

The Problem 50 in Project Euler is stated as

*“*- pronounced as “**D!**”**”. which was an acronym for “***D not***” - meaning someone who has nothing better to do. The following can be classified as a pure "***Dhandaa not***" activity!***D!*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,

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

On the other hand, the smallest prime with

The smallest prime with

Below 1 million, there is only one prime with

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”.There are many 3 digit primes that haveSCP(n)= the number of sets of consecutive primes that can be added to get n.

SoSCP(41) = 2

**SCP**number more than 1. For exampleThere are no 3 digit primes with983 = 23 + 29 + … + 89 + 97(17 primes)

983 = 47 + 53 + … + 101 + 103(13 primes)

SoSCP(983) = 2.

**SCP = 3**. But There are 2 primes with**SCP**number as 4.The other prime is 863.311 = 11 + 13 + .. + 43 + 47(11 primes)

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**.Below one million, the largest prime with34421 = 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

**SCP**number as 5 is**988321**. One of the set of consecutive primes that add up to that number isAnd it’s NOT the answer to the Project Euler problem. The988321 = 113 + 127 + … + 3919 + 3923

This has a whopping 515 consecutive primes !

**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**.That’s a special number. There is no prime below 1 million with442019 = 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

**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.

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