Google Treasure Hunt: Last problem

The last and fourth problem from Google Treasure Hunt deals with consecutive prime numbers. Its basic form is:

Find the smallest number that can be expressed as
the sum of m consecutive prime numbers,
the sum of n consecutive prime numbers,
the sum of o consecutive prime numbers,
the sum of p 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).

In the case of m, n, o, and p, there are four conditions, although there can be more. The example of 41 has only two conditions, for instance.

Again, my solution was written in Python and is designed to scale to a variable amount of conditions, as seen in the primes.py I wrote:

primes = get_primes()
conds = [3, 5, 143, 865, 1089]
consecutives = []

def intersection(*lists):
  def i(list1, list2):
    i = {}; l = {}
    for e in list1: l[e] = 1
    for e in list2:
      if l.has_key(e): i[e] = 1
    return i.keys()
  return reduce(i, lists)

for cond in conds:
  sums = [sum(primes[cond])]
  left = 1; right = cond + 1
  while right != len(primes) + 1:
    last = sums[left - 1]
    now = last - primes[left - 1] + primes[right - 1]
    sums.append(now)
    left += 1; right += 1
  consecutives.append(sums)

results = intersection(*consecutives)
results.sort()
print results

It doesn't worry about calculating consecutive primes; this Python recipe can generate primes fairly well. What it does do is that it takes a huge list of integers that should all be consecutive primes, starting from 2. Then it swallows all of them for processing n times, n being the number of conditions. Each time, it builds a list of sums of k consecutive primes using a sliding window method, with k being the number specified in the condition.
Finally, the intersection of all the built lists of sums is found and then sorted, leaving the first number in the intersection result list as the answer to the problem.

The intersection algorithm uses dictionaries to speed up the operation vastly, and then performs reduce (also formally known as fold or known as inject in Ruby) to get a set of elements that occur in all lists given.

Performance-wise, this is fairly fast; it can obtain the answer with conditions like [3, 5, 143, 865, 1089] within 9 seconds.

I took a different approach:

I took a different approach: I wrote a Drupal module to do this :). It was tricky because PHP is not particularly speedy, so I was forced to optimize the script quite a bit (and I had the misfortune of being given some quite big numbers).

An interesting little

An interesting little nugget: I found out that I could eliminate the whole intersection function if I convert the Python lists to Python sets, but that has a 0.5 second performance penalty.

Hi nice code, Thanks for

Hi nice code, Thanks for sharing it.

>Again, my solution was written in Python and is designed to scale to a variable amount of conditions, as seen in the primes.py I wrote:

If the primes.py code is any good, can you please share that too? Otherwise there's not much point in referencing it since you have referenced a python recipe to generate primes.

Thanks

Hal