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

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: