Project Euler 60

Problem 60
3,7,109,673という素数は極めて注目に値する。どの2つの素数を取ってどの順番で結合しても、その結果は常に素数である。例えば、7と109を取ると、7109も1097も素数である。この4つの素数の和は792で、この性質を持つ4つの素数の組で最小の和である。
どの2つの素数を結合しても他の素数になるような5つの素数の組の最小の和を求めよ。
http://projecteuler.net/index.php?section=problems&id=60

この手の問題はうまく再帰に持ち込めればいいはずです。ただ、最小というのが難しい。そこで、ある素数が最大である組でそのような性質を持つものを探索して、その素数を大きくしていきます。見つかったら、その和より小さくなるような組があるかどうか調べます。
まず、素数のペアを探します。そして、3つ組なら今対象にしている最大の素数rとします。素数のペア(p, q)に対し、(p, r)と(q, r)がペアの中にあるかどうか調べます。共にペアの中にあれば(p, q, r)もこの性質を持つことになります。
5つ組なら最大の素数tとして(p, q, r, s)に対して(p, q, r, t)と(s, t)がこの性質を持つ4つ組とペアの中にあれば、この性質を持つことになります。
一つ5つ組が求まったら、4つ組を和でソートして、求まった5つ組の最大の素数以上の素数と4つ組でこれより小さい和がないか調べます。



from itertools import ifilterfalse, ifilter, takewhile, count, islice

def all(f, a):
for e in ifilterfalse(f, a):
return False
return True

def is_prime(n):
b = all(lambda p: n % p != 0, takewhile(lambda p: p * p <= n, primes))
if b:
p = primes[-1]
while p * p < n:
p = next_prime()
if n % p == 0:
return False
return True
else:
return False

def next_prime():
for n in ifilter(is_prime, count(primes[-1] + 1)):
primes.append(n)
return n

def prime(k):
if k < len(primes):
return primes[k]
else:
return next_prime()

def cat(p, q):
n = 10
while q > n:
n *= 10
return p * n + q

def is_cat_prime(p, q):
return is_prime(cat(p, q)) and is_prime(cat(q, p))

def is_all_pair(p, g):
return (g[-1], p) in prime_groups[2] \
and g[:-1] + (p,) in prime_groups[len(g)]

# n-prime group
def calc_prime_group(n, m):
p = prime(m)
if n == 2:
for g in [ (q, p) for q in filter(lambda q: is_cat_prime(q, p),
takewhile(lambda q: q < p, primes)) ]:
prime_groups[2].add(g)
else:
calc_prime_group(n - 1, m)
for g in map(lambda g: g + (p,),
filter(lambda g: is_all_pair(p, g), prime_groups[n-1])):
prime_groups[n].add(g)

N = 5
primes = [ 2 ]
prime_groups = [ set() for k in range(N + 1) ]
for m in count(1):
calc_prime_group(N, m)
if len(prime_groups[N]):
for g in prime_groups[N]:
min_sum = sum(g)
print g, min_sum
break

b = list(prime_groups[N-1])
b.sort(key = lambda e: sum(e))
while prime(m) < min_sum:
p = primes[m]
for e in takewhile(lambda e: sum(e) < min_sum - p, b):
if all(lambda q: is_cat_prime(p, q), e):
min_sum = sum(e) + p
print e + (p,), min_sum
m += 1
print min_sum