Sum Of Four Primes
January 27, 2015
Today’s exercise comes from one of those competitive programming websites. I never participate in the coding frenzy at those sites, because the competitiveness at extracting every last millisecond from the run time or deleting every unneeded character from the program text ruins the pleasure, but some of the problems are fun:
Given a positive integer 7 < n ≤ 10000000, find four prime numbers with sum n. For instance, 46 = 11 + 11 + 17 + 7.
Your task is to write a program to find four primes that sum to n. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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: