- 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。
問題 51. 数字の置き換え素数
原文 Problem 51: Prime digit replacements
問題の要約：数字の部分を0,1,2,3,...,9で置き換えたときに8個が素数になるときその最小の素数を求めよ
5桁の例 \\
"56**3"の"*"を0,1,2,3, \dots 9で置き換える \\
56003, 56113, 56333, 56443, 56663, 56773, 56993の7個が素数
問題51になって急に難しくなりましたね。以下のような順番に考える必要があると思われます。数字の桁数をN, "*"の数をMとします。
１． "*"以外のN-M桁の数字を生成する。あとで順列を取るのでここは「重複ありの組み合わせ」でitertoolsのcombinations_with_replacementを使います。
２． １．で生成した数字にM個の"*"を連結した文字列の「重複ありの順列」を生成します。このプログラムは意外に難しいのですが、幸いにもmore_itertoolsのdistinct_permutationsというものを見つけたのでこれを使います。試してみると以下のように思ったように動きました。
from more_itertools import distinct_permutations
for p in distinct_permutations('**2'):
print(''.join(p))
# **2
# *2*
# 2**
３．生成した"*"入りの文字列の"*"を0,1,2,3で置き換えて素数の数を数える。これをprmsDigRepで行っています。例題の”5603”を入力すると7つの素数が出来ることが分かります。
ps = prmsDigRep("56**3")
print(ps)
# [56003, 56113, 56333, 56443, 56663, 56773, 56993]
これらを組み合わせ出来たプログラムです。
from more_itertools import distinct_permutations
from itertools import combinations_with_replacement
from sympy import isprime
digs = [str(d) for d in range(10)] # "1","2",..."9"
def repask(num,d): # replace "*"s of num with d
ret = num.replace("*",d)
return "0" if ret[0] == "0" else ret # if leading zero, return 0
def prmsDigRep(dps): # List up all primes, when dsp's "*" are replaced all digits
return [p for p in [int(repask(dps,d)) for d in digs] if isprime(p)]
def minPrimeDigRep(N, M, nPr):
for nnn in combinations_with_replacement(digs, N - M):
for dp in distinct_permutations(list("".join(nnn) + "*"*M)):
prms = prmsDigRep(''.join(dp))
if len(prms) >= nPr:
return prms[0]
return None
N, M, nPr = 5, 3, 8 # N: digits, Msk: num of masks, nPr: num of prime value
for N in range(6,10):
ans = minPrimeDigRep(N, M, nPr)
if ans != None:
print(f"Answer: {ans}, N={N},M={3}")
break
（開発環境：Google Colab）