## 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 · 1017 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.

Advertisements

Pages: 1 2

### 7 Responses to “Sum Of Four Primes”

1. Francesco said

Probably as inefficient as it gets:

```import Data.Numbers.Primes (primes)
import Control.Monad (replicateM)

f n = head . filter ((== n) . sum) \$ (replicateM 4 (takeWhile (< n) primes))
```
2. Mike said

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)
>>>

3. Mike said

With formatting:

```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)
>>>
```
4. Hunter said

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)

5. mcmillhj said

Formatting didn’t work for some reason:

```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)
```
6. bitchef said

Here is my inefficient solution in Python.

```'''
Given a positive integer 7  < n <= 10000000 find four prime numbers with the sum n.
For instance, 46 = 11 + 11 + 17 +  7
'''

# get a list of prime numbers less that n
# sieve out the prime numbers

import math
import itertools

def sieve(num):
'''
Returns a list of prime numbers less than n
'''
limit  = math.floor(math.sqrt(num))
primeList = range(3, num, 2)
filterNum = primeList
while True:
primeList = [n for n in primeList[1:] if n % filterNum != 0]
filterNum = primeList
if filterNum > limit:
break
primeList.insert(0,2)
return primeList

def sum_of_four(num):
'''
Returns a list of tuples of  four prime numbers that sum to num
'''
return [(i) for i in itertools.combinations_with_replacement(sieve(num),4)
if sum(i) == num]

```

This is very slow.
Sample output for 46:

```In : FourPrimes.sum_of_four(46)
Out:
[(2, 2, 11, 31),
(2, 2, 13, 29),
(2, 2, 19, 23),
(7, 7, 13, 19),
(7, 11, 11, 17),
(7, 13, 13, 13),
(11, 11, 11, 13)]
```