Problem 51
*3の最初の数字を置き換えて、9つの可能な値のうち6つ：13,23,43,53,73,83がすべて素数であることがわかる。
56**3の3番目と4番目を同じ数字に置き換えると、この5桁の数が10の生成される数のうち7つが素数になる最初の例である。これにより次の族が生じる：56003,56113,56333,56443,56663,56773,56993。結果的にこの族の最初の数56003はこの性質を持つ最小の素数である。
数の一部（隣の桁でなくてもよい）を同じ数字で置き換えて8つの素数の族になるその一部の最小の素数を見つけよ。
http://projecteuler.net/index.php?section=problems&id=51
小さい自然数から順に調べていきます。そして、その数の各桁が0か1か2が置き換えの候補になります。もし3を置き換えても0から2に置き換えて題意を満たすならもう調べられていることになり、満たさないなら素数は7個以下になります。
例えば、13021で考えてみましょう。置き換えのパターンは、
13*21 1302* *3021 *302* 130*1
となります。実際に置き換えるときは、元の数にそれぞれ、
100 1 10000 10001 10
を加えていくことになります（Code1）。
しかし、この差分は、例えば100ではいけないことがわかります。例えば1に100を足していくと、101,201,301,401,…901となり、9つあれば3つは3の倍数になるからです。2から始まると8つだから2つは3の倍数だから素数は6つ以下となり、やっぱりダメです。差分が3の倍数ならばこういうことはなくなります。だから、差分は3の倍数でなければなりません。同様に10の倍数でなければなりません。あわせて30の倍数でなければなりません。また、最初から同時に置き換える桁が3個以上なければなりません。
# Code1
from itertools import ifilter, takewhile, islice, 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 gen_digits(n):
while n:
yield n % 10
n /= 10def gen_comb(a, k = 0):
if k == len(a) - 1:
yield 0
yield 10 ** a[k]
else:
for n in gen_comb(a, k + 1):
yield n
yield n + 10 ** a[k]def gen_mask(digits, d):
a0 = filter(lambda k: digits[k] == d, range(len(digits)))
if len(a0):
for n in ifilter(lambda n: n != 0, gen_comb(a0)):
yield ndef gen_diff(n):
digits = list(gen_digits(n))
for d in range(3):
for m in gen_mask(digits, d):
yield m, ddef is_valid(n):
if not is_prime(n):
return False
for diff, d0 in gen_diff(n):
counter = 1
for d in range(d0 + 1, 10):
if is_prime(n + diff * (d - d0)):
counter += 1
elif counter == d - 2:
break
if counter == N:
return True
return FalseN = 8
for n in islice(ifilter(is_valid, count(2)), 1):
print n
# Code2
# これ以外は上のコードと共通
def gen_comb(a, k = 0):
if k == len(a) - 1:
yield 0, 0
yield 10 ** a[k], 1
else:
for n, l in gen_comb(a, k + 1):
yield n, l
yield n + 10 ** a[k], l + 1def gen_mask(digits, d):
def is_valid(t): return t[0] and t[0] % 30 == 0
a0 = filter(lambda k: digits[k] == d, range(len(digits)))
if len(a0):
for n, l in ifilter(is_valid, gen_comb(a0)):
yield ndef gen_diff(n):
digits = list(gen_digits(n))
for d in filter(lambda d: digits.count(d) >= 3, range(3)):
for m in gen_mask(digits, d):
yield m, d
