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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: