Solutions to Project Euler 10 in the R language. Find the sum of all primes below two million, using the Sieve of Erarosthenes.

Project Euler 10: Summation of Primes

Peter Prevos

Peter Prevos |

551 words | 3 minutes

Share this content

Project Euler 10 asks for the summation of primes. Computationally this is a simple problem because we can re-use the prime sieve developed for Project Euler 3. 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. There is thus no algorithm to create prime numbers, all we can do is mine them from the infinite field of integers.

Project Euler 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 from Project Euler 3 generates the prime numbers between two and two million, which can then easily be summed.

  ## Project Euler 10: Summation of Primes
  source("problem003.R", echo = FALSE)

  primes <- esieve(2e6)
  answer <- sum(primes)
  print(answer)

Goldbach's Conjecture

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. In 1742 Goldbach wrote a letter to Euler in which he states that:

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

A Goldbach partition is the expression of a given even number as a sum of two primes, for example:

$$100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53$$

All even numbers greater than 12 can be written as the sum of two primes in more than two ways. Sequence A045917 in the Online Encyclopedia of Integer Sequences lists the number of ways in which \(2n\) can be written as the sum of two primes (\(n\geq1\)). This conjecture is as yet unproven and one of the most persistent problems in mathematics.

Goldbach Conjecture - Numberphile.

We can write some code to verify that every integer greater than two and less than \(n\) can be expressed as the sum of two primes. This code recreates sequence A045917 and visualises the first 1000 results. There does not seem to be a pattern in the number of ways to sum two primes. However, When visualising the sequence with a scatter plot, horizontal bands of points appear.

  ## Goldbach's Conjecture
  goldbach <- function(n) {
      if (n%%2 != 0) return("This only works for even numbers")
      if (n == 2) return(0)
      primes <- rev(esieve(n)) # All primes below n
      k <- length(primes)
      g <- 0
      for (i in 1:k) {
        for (j in i:k) {
          if((primes[i] + primes[j]) == n) {
            # print(paste(n, "=", primes[i], "+", primes[j]))
            g <- g + 1
          }
        }
      }
      return(g)
    }

    library(ggplot2)
    n <- seq(from = 2, by = 2, length.out = 1000)
    A002375 <- data.frame(n,
                          g = sapply(n, goldbach))
    ggplot(A002375, aes(n, g)) +
      geom_point(col = "red", size = .5) +
      theme_minimal(base_size = 10) +
      labs(title = "Goldbach's Expressions",
           subtitle = "Number of ways to write an even number as the sum of two primes",
           x = "Even number", y = "Number of prime sums")
    ggsave("images/problem-010.png", width = 6, height = 4)

/images/project-euler/problem-010.png

Number of ways to write an even number \(n\) as the sum of two primes \((2 \leq n \leq 1000)\), (sequence A002375 in the OEIS).

Share this content

You might also enjoy reading these articles

Project Euler 35: Circular Primes below One Million

Project Euler 144: Laser Beams and Elliptical Billiards

Project Euler 33: Digit Cancelling Fractions