Saturday, March 23, 2013

Sum of consecutive primes

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

4 comments:

  1. Is 1 not a prime number? If it is prime then

    1 + 2 + 3 = 6 (does not add up to a prime number) !

    Will you please explain?

    ReplyDelete
    Replies
    1. Kedar,

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

      Delete
  2. 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?

    Smallest example is 5=2+3

    All are prime and so is the size of the set.

    ReplyDelete
    Replies
    1. 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

Related Posts Plugin for WordPress, Blogger...