#WeHateMath Project Euler 10 – Summation of Primes

Summation of primes

Problem 10

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

We’ve spoken about primes before but this problem is different. First of all, it seems pretty straightforward. We’re adding up a list of numbers. Granted, we have to generate the list of numbers first but generating a list of primes is not unknown technology. (Like any nerd, I let a computer do the hard work).

The question is (as it is with all of these problems), why do it?  What’s the point? That’s what I had to ponder for a while. So I decided to let my computer grind through a few possibilities. Using a combination of a spreadsheet and some computer code (and there’s no reasonable way to do this without some programming skills), I poked at some numbers.

One of the first things I discovered was that (no surprise) the sums get big pretty quickly. I started by asking Wolfram Alpha to do prime sums for me. It worked fine for 10, 100, 1000 and up to 1000000. But when I asked for the sum of primes less than 2,000,000 it crapped out on me. You see, Wolfram Alpha has built-in limits on how much processing time you can use.

Okay, you have my interest now.

I poked around and found some program code that did sums of primes, loaded it into XCode, compiled and ran it. At first I used it to check the numbers that Wolfram Alpha had given me (no harm in checking). Of course, as the numbers got bigger, the processing took longer and longer. I decided to shorten things by asking for the sum of primes between 1,000,000 and 2,000,000 (since I already had the sum for 1,000,000). I dumped it into my spreadsheet and made a table:

 

N

Sum of Primes

Sum of N

Diff(N, Sum_of_Primes)

Diff(N, Sum_of_N)

10

17.00

55.00

7.00

45.00

100

1,060.00

5,050.00

960.00

4,950.00

1000

76,127.00

500,500.00

75,127.00

499,500.00

10000

5,736,396.00

50,005,000.00

5,726,396.00

49,995,000.00

100000

454,396,537.00

5,000,050,000.00

454,296,537.00

4,999,950,000.00

200000

1,709,600,813.00

20,000,100,000.00

1,709,400,813.00

19,999,900,000.00

1000000

37,550,402,023.00

500,000,500,000.00

37,549,402,023.00

499,999,500,000.00

2000000

142,913,828,922.00

2,000,001,000,000.00

142,911,828,922.00

1,999,999,000,000.00

 

Just for fun, I added a column of straightforward sums plus differences. (You never know what relationships will pop up.) I also ran my prime summing program with a timer and here are the results:

 

Enter min range: 2
Enter max range: 2000000
Sum of prime numbers is: 142913828922
real19m57.296s
user19m42.095s
sys0m0.625s

 

In human-speak, this means that the calculation took almost twenty minutes of ‘real’ time (as in wall-clock time) and about two-thirds of a second of computing time. Just out of curiosity, I ran the same program but just for the primes between one million and two million:

 

Enter min range: 1000000
Enter max range: 2000000
Sum of prime numbers is: 105363426899
real14m20.074s
user14m9.366s
sys0m0.195s

 

Interestingly enough, it took almost the same amount of ‘real’ time but about a third of the computing time. Just for fun, I wondered how much time it would take to do sum of primes up to 1 million:

 

Enter min range: 2
Enter max range: 1000000
Sum of prime numbers is: 37550402023
real5m15.445s
user5m7.393s
sys0m0.213s

 

Well, about one-third of ‘real’ time and a bit more computing time. The latter was to be expected but the former isn’t.

In any event, I’m still not sure about the point to this problem. If I figure it out, I’ll post an update.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s