Monday, November 2, 2009

A simple solution for Google Hunt 2008 warmup

#!/usr/bin/env python

# Find the smallest number that can be expressed as
# the sum of 3 consecutive prime numbers,
# the sum of 9 consecutive prime numbers,
# the sum of 27 consecutive prime numbers,
# the sum of 31 consecutive prime numbers,
# the sum of 1119 consecutive prime numbers,
# and is itself a prime number.

import gmpy

k = 1
seq = []

def add(n):
    q = 0
    global k
    for _ in xrange(n):
        k = gmpy.next_prime(k)
        seq.append(k)

def isprime(n):
    return gmpy.is_prime(n)

def plus(site, amount):
    sum_of_prime = 0
    if len(seq) < site + amount:
        add(site + amount - len(seq))
    for prime in seq[site:site + amount]:
        sum_of_prime += prime
    return sum_of_prime

def isequal(amount, num):
    site = 0
    s = 0
    while True:
        s = plus(site, amount)
        if s == num:
            return site
        elif s > num:
            return -1
        site += 1

block = 0
length = []

while True:
    ipt = raw_input("amount" + str(block + 1) + ":")
    if ipt == "":
        break
    else:
        length.append(int(ipt))
        block += 1

length.sort(reverse=True)
c = True
position = [0] * block

while c:
    num = plus(position[0], length[0])
    if isprime(num):
        for i in range(1, block):
            site = isequal(length[i], num)
            if site > -1:
                position[i] = site
                if i == block - 1:
                    c = False
            else:
                position[0] += 1
                break
    else:
        position[0] += 1

print "\n", "Hunt:", num, "\n"

for i in range(block - 1, -1, -1):
    print "position" + str(length[i]) + ":" + str(position[i])