Euler Problem 10: Summation of Primes

Euler Problem 10 asks for the summation of primes. Computationally this is a simple problem because we can re-use the prime sieve developed for problem 3.

When generating a large number of primes the erratic pattern at which they occur is much more interesting than their sum. Mathematicians consider primes the basic building blocks of number theory. No matter how hard we look, however, they do not seem to obey any logical sequence. This Euler Problem is simply

Euler Problem 10 Definition

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

Solution

The sieve of Eratosthenes function used in Euler Problem 3 can be reused once again to generate the prime numbers between two and two million. An interesting problem occurs when I run the code. When I sum all the primes without the as.numeric conversion, R throws an integer overflow error and recommends the conversion.

primes <- esieve(2e6)
answer <- (sum(as.numeric(primes)))
print(answer)

This results in a vector containing the first 148,933 prime numbers. The largest prime gap is 132 and it seems that sexy primes are more common than any of the other twin primes (note the spikes at intervals of 6 in the bar chart).

Euler Problem 10: Prime gaps for all primes up to two million

The summing of primes reveals an interesting problem in mathematics. Goldbach’s conjecture is one of the oldest and best-known unsolved problems in number theory and states that:

Every even integer greater than 2 can be expressed as the sum of two primes.

Note that this conjecture is only about even numbers. Goldbach also theorised that every odd composite number can be written as the sum of a prime and twice a square. This conjecture is the subject of the Euler Problem 46, which I will work on soon.

3 thoughts on “Euler Problem 10: Summation of Primes

  1. Pingback: Euler Problem 10: Summation of Primes - Use-R!Use-R!

  2. Ok, that’s a method. Isn’t the interesting part, i.e. the point of the problem, to come up either with a more efficient algorithm or to discover an algorithm for knowing the sum of primes even if the primes themselves aren’t known? I’m not a number theorist, so I’d be happy with a link to a theorem proving the latter is impossible.

    • The code is indeed less interesting than the theory about prime numbers. I am pretty sure that there is no efficient way to determine primes other than sieving and finding each of them. Prime numbers don’t follow any known patterns, which is why they are used in cryptography.

Leave a Reply