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[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:

    In [3]: FourPrimes.sum_of_four(46)
    Out[3]: 
    [(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)]
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: