Project Euler 10: Summation of Primes

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

The sieve of Eratosthenes function from Project Euler 3 generates the prime numbers between two and two million, which can then easily be summed.

ProjectEuler

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

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

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.

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)