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.

Friday, March 8, 2013

We Bought A Zoo

Movie Review : We bought A Zoo
Director : Cameron Crowe
Genre : Drama
Starring : Matt Damon, Scarlett Johansson
Released : 2011
My Rating : 5 out of 10

I have a bias towards movies based on real life stories. Reality is not only stranger than fiction, it can also be more uplifting, and sometimes more traumatic. This movie is loosely based on the true story of Benjamin Mee who bought a zoo in England and wrote a book about it.

In the movie, Benjamin Mee (Matt Damon) is in California, and a widower who is trying his best to take care of his two children. The daughter is too young and is attached to her dad, but the son is having a hard time getting over the loss of his mother. When he gets expelled out of the school, Benjamin decides a change might be better for all. He starts looking for a new house, and ends up buying one with a small zoo, just because the young daughter loves it. He has no idea what zoology is, and what kind of commitment it requires. In addition, the staff is running very low on morale. Benjamin desperately needs the zoo to be opened, but he has to first satisfy the demands of a tough inspector. To make matters worse, his relationship with his son gets more and more stressful.

This is a feel good movie, so we know Benjamin is eventually going to beat the odds, and everything is going to be fine. We just want to enjoy the ride, have a few good laughs and be genuinely happy for the characters. Benjamin is likeable, and we understand why he doesn’t want any more sympathy. We understand what his son is going through. The movie does a good job of setting the context, and then fails at convincing us how the problems got solved. We want to cheer for Benjamin and his team, but we never know when to cheer for them.

This is a huge problem with the script, and the direction by Cameron Crowe does not help. He has many successes under his belt, but this one feel like a halfhearted effort. The actors do a decent job with whatever material they have been given. The story has all the elements needed for making a fun, uplifting movie. Unfortunately it remains very flat and never rises above cliched, ineffective scenes.

I cannot recommend this movie. But it’s an OK movie to watch with the entire family. My guess would be that, no one is going to get really bored, but no one is going to love it either.
Related Posts Plugin for WordPress, Blogger...