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

Pages: 1 2

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

1. Francesco said

Probably as inefficient as it gets:

```import Data.Numbers.Primes (primes)

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