A Solution to Google Treasure Hunt 2008 Problem 4

From Google Treasure Hunt 2008:

Find the smallest number that can be expressed as
the sum of 3 consecutive prime numbers,
the sum of 5 consecutive prime numbers,
the sum of 517 consecutive prime numbers,
the sum of 551 consecutive prime numbers,
and is itself a prime number.

For example, 41 is the smallest prime number that can be expressed as
the sum of 3 consecutive primes (11 + 13 + 17 = 41) and
the sum of 6 consecutive primes (2 + 3 + 5 + 7 + 11 + 13 = 41).

I wrote my solution to this problem in ~60 lines of python. In a nutshell:

1. Get a precomputed list of (1,000,000) primes.

2. Find all possible summations of 551 consecutive prime numbers. If the sum is prime, store this in a list of ‘candidates’.

3. Find all possible summations of 517 consecutive prime numbers. If the sum is in the candidate list from step 2, store it in a new candidate list.

4. Repeat step 3 using this new candidate list for summations of 5 and 3 consecutive prime numbers.

5. The smallest number in the final candidates list is the answer.

The script ran pretty quickly on my machine (3.00 GHz P4), taking about 1-2 minutes to find the answer.

This entry was posted on Wednesday, April 15th, 2009 at 10:28 am and is filed under General. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses

  1. Larry Engholm says

    Here’s my solution. It’s about 2/3 the lines, it computes primes (rather than reading a precomputed list), it doesn’t have an artificial 700,000 prime limit, and runs faster. It’s more of a lazy evaluation solution, where it uses generators rather than precomputing values that won’t be needed.

    def eratosthenes():
    # From the web
    ”’Yields the sequence of prime numbers via the Sieve of Eratosthenes.”’
    D = {} # map composite integers to primes witnessing their compositeness
    q = 2 # first integer to test for primality
    while 1:
    if q not in D:
    yield q # not marked composite, must be prime
    D[q*q] = [q] # first multiple of q not already marked
    else:
    for p in D[q]: # move each witness to its next multiple
    D.setdefault(p+q,[]).append(p)
    del D[q] # no longer need D[q], free memory
    q += 1

    def consecutive(n):
    ”’ Generator returning next sum of n consecutive primes. ”’
    primes = eratosthenes()
    primelist = [primes.next() for i in range(n)]
    s = sum(primelist)
    while 1:
    yield s
    prime = primes.next()
    s = s – primelist[0] + prime
    primelist = primelist[1:] + [prime]

    def equal(consecgen, val):
    # Advance until greater than or equal to val. Return true if equal.
    while 1:
    next = consecgen.next()
    if next == val: return True
    if next > val: return False

    c723 = consecutive(723)
    c19 = consecutive(19)
    c17 = consecutive(17)
    c3 = consecutive(3)
    while 1:
    attempt = c723.next()
    if equal(c19, attempt) and equal(c17, attempt) and equal(c3, attempt):
    print ‘And the winner is’, attempt
    break

    April 17th, 2009 at 11:10 am

  2. Larry Engholm says

    Unfortunately tabs aren’t preserved here.

    In the code above, start “def” statements at the beginning of the line, indent lines following a line ending with a colon (of course), and unindent starting at the following four lines:

    else:
    del D[q]
    q += 1
    c723 = consecutive(723)

    April 17th, 2009 at 11:18 am

  3. Simmoril says

    Larry,

    Thanks for showing me your solution to the problem, it’s definitely much more elegant than the one I hacked together ;-) It’s also a good reminder to strengthen my functional-programming-fu, as I definitely don’t (ab)use generators as much as I probably should in my python code.

    April 18th, 2009 at 4:32 pm

Leave a Reply