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.
Programming Praxis 
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:
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)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[0] while True: primeList = [n for n in primeList[1:] if n % filterNum != 0] filterNum = primeList[0] 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: