## Sum Of Four Primes

### January 27, 2015

Goldbach’s Conjecture states that any even integer greater than three can be written as the sum of two primes; the conjecture is known to be true to 4 · 10^{17} and is widely believed to be true for all *n*, though it remains unproved. It is easy to reduce today’s problem to the Goldbach conjecture; if *n* is even, the first two primes are 2 and 2, and if *n* is odd, the first two primes are 2 and 3. The remainder must be even, so Goldbach’s conjecture says there are two more primes, giving a total of four. We write the program simply as follows:

`(define (prime? n)`

(if (even? n) (= n 2)

(let loop ((d 3))

(if (< n (* d d)) #t

(if (zero? (modulo n d)) #f

(loop (+ d 2)))))))

`(define (goldbach n)`

(let loop ((i 2) (j (- n 2)))

(if (and (prime? i) (prime? j))

(list i j)

(loop (+ i 1) (- j 1)))))

`(define (four-primes n)`

(if (< n 8) "impossible"

(if (even? n)

(append (list 2 2) (goldbach (- n 4)))

(append (list 2 3) (goldbach (- n 5))))))

That’s not the fastest primality test, but *n* is small enough that it doesn’t matter. The `goldbach`

function nearly always finds a suitable pair without much work. Thus, despite its simplicity, this solution works well. Here are some examples:

`> (four-primes 46)`

(2 2 5 37)

> (four-primes 12343209)

(2 3 197 12343007)

You can run the program at http://programmingpraxis.codepad.org/q0xT09ee. We gave a somewhat different solution to the Goldbach Conjecture at a previous exercise.

Probably as inefficient as it gets:

Wikipedea says that the Strong Goldbach conjecture has been shown to hold up to at least 4 * 10^18 , which is sufficient to solve this problem.

1. Find a prime p1 such that p1 < n – 7. Preferably, p1 is close to n.

2. if n – p1 is odd, then p2 = 3 else p2 = 2

3. find a pair of primes, p3 and p4, that sum to n – p1 – p2. If p1 is large, then n – p1 – p2 is small and it will be easy to find p3 and p4

A Python solution:

from math_utils import is_prime, prev_prime, primes

def fourprimes(n):

p1 = prev_prime(n – 7)

n -= p1

p2 = 3 if n&1 else 2

n -= p2

for p3 in primes():

p4 = n – p3

if is_prime(p4):

return p1, p2, p3, p4

# examples:

>>> fourprimes(46)

(37, 3, 3, 3)

>>> fourprimes(4600000)

(4599989, 3, 3, 5)

>>>

With formatting:

In Rust: http://xojoc.pw/programming-praxis/sum-of-four-primes.html

SML:

fun isPrime n =

if n < 2 then false

else if n mod 2 = 0 then n = 2

else

let fun noDivisorsAbove m =

if n mod m = 0 then false

else if m*m >= n then true

else noDivisorsAbove(m + 1)

in

noDivisorsAbove 2

end

fun goldbach n =

let fun loop(i, j) =

if isPrime(i) andalso isPrime(j) then [i, j]

else loop(i+1, j-1)

in

loop(2, n-2)

end

fun fourPrimes n =

if n < 8 then raise Domain

else if n mod 2 = 0 then 2 :: 2 :: goldbach(n-4)

else 2 :: 3 :: goldbach(n-5)

Formatting didn’t work for some reason:

Here is my inefficient solution in Python.

This is very slow.

Sample output for 46: