Problem 37
3797という数は興味深い性質を持っている。それ自身が素数で、左から順に数字を取り除いていっても素数のままである：3797,797,97,7。同様に右から順に取り除いても素数である：3797,379,37,3。
11個あるこのようにどちらからでも短くできる素数の和を求めよ。
http://projecteuler.net/index.php?section=problems&id=37
11個というのは計算を短縮できる重要なヒントですが、ここではこの情報は使わないようにしましょう。
左から順に数字を取り除いても素数となる数を求めてみます。これは逆から考えたほうがいいでしょう。すなわち、1桁の素数は、
2 3 5 7
ですが、この左に数字を加えて素数になるのは、
13 23 43 53 73 83 17 37 47 67 97
です。これにもう一つ数字を加えて素数だけ選べば、3桁で左から順に数字を取り除いていっても素数のままの数の集合ができます。
同様に、1桁の素数の右に数字を加えて素数になるのは、
23 29 31 37 53 59 71 73 79
です。そして、どちらから取り除いても素数になる数は、両方の集合の交わりで、
23 37 53 73
の4つです。これをどちらかの集合が空集合になるまで続ければよいです。
動かしてみると、右に数字を加えていく方は9桁目でなくなります。一方、左に数字を加えていく方は、9桁目がピークで、そのあと徐々に減っていくようです。15桁目まで確認しました。よく考えると、右には1,3,7,9しか加えられないのに対し、左には1〜9のどれも加えられる可能性があるので、左に加えていく方が長生きするのは当然ですね。
from itertools import takewhile, ifilter, countdef gen_prime_candidates():
yield 2
yield 3
n = 5
while True:
yield n
yield n + 2
n += 6def is_prime(n):
for p in takewhile(lambda p: p * p <= n, gen_prime_candidates()):
if n % p == 0:
return False
return Truedef add_head(n, d, k):
return n + d * 10 ** (k - 1)def add_tail(n, d, k):
return n * 10 + ddef gen_add_digit(n, add, k):
for d in range(1, 10):
yield add(n, d, k)def next_set(s, add, k):
a = [ ]
for n in s:
a.extend(list(ifilter(is_prime, gen_add_digit(n, add, k))))
return set(a)def gen_both_truncatable_prime():
a = filter(is_prime, range(2, 10))
s1 = set(a)
s2 = set(a)
for k in count(2):
s1 = next_set(s1, add_head, k)
s2 = next_set(s2, add_tail, k)
if len(s1) == 0 or len(s2) == 0:
break
for n in s1 & s2:
yield nprint sum(gen_both_truncatable_prime())
