出典： Project Euler（日本語 翻訳サイト）
ProjectEuler.net（英語サイト）
Problem 51
*3の第1桁を置き換えることで,
13, 23, 43, 53, 73, 83という6つの素数が得られる.
56**3の第3桁と第4桁を同じ数で置き換ることを考えよう.
この5桁の数は7つの素数をもつ最初の例である:
56003, 56113, 56333, 56443, 56663, 56773, 56993.
よって, この族の最初の数である56003は, このような性質を持つ最小の素数である.
桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ.
(注:連続した桁でなくても良い)
－－－－－
私の解答例は以下です。畳んでいます。
def p(n):
L = [0,0]+[1]*(n-1)
i = 2
while i*i<=n:
while not L[i]: i += 1
for j in xrange(i+i, n+1, i): L[j] = 0
i += 1
return [i for i in xrange(n+1) if L[i]]
def h(n, L):
for i in xrange(10):
t = ""
for j, k in enumerate(str(n)):
if j in L: t += str(i)
else: t += k
yield int(t)
def g(m, n):
d = {}
for i, t in enumerate(str(m)):
d[t] = d.get(t, [])+[i]
for k,v in sorted(d.items()):
if len(v)==n: yield int(k),v
def f():
for i in xrange(3, 100, 3):
for n in xrange(i+1, 100):
P = [s for s in p(10**n) if s>10**(n-1)]
for j in P:
for k,L in g(j, i):
if k>2: break
if L[-1]>=n-1: break
t = 0
for u in h(j, L):
if u not in P: t += 1
if t>2: break
if t==2: return j
print f()
候補を絞り込みます。
桁を同じ数で置き換えることで8つの素数が得られる最小の素数とのことなので、
置換後値が素数になる場合の置換数字には0～9うちの8個選ばれるので、
置換数字の最小値には0,1,2のどれかが含まれます。...(A)
素数でない数として、まず２の倍数をはずします。
置換数字には、0～9の10種類の数字のうちの8個選ばれるので、必ず偶数を含みます。
1の位に偶数がきたら２の倍数となり素数ではないので、
置換数字は1の位にきません。...(B)
つまり、置換数字は10の位よりも上の桁になるので、
全体桁数は置換数字の桁数よりも1桁以上多いです。...(C)
次に３の倍数をはずします。
置換数字が1桁の連番の場合、
３で割るとその余りは、0,1,2が繰り返しでてきます。
すると余り0,1,2が最低各３つずつあり、
３の倍数以外が８個あることはあり得ず問題に合いません。
置換数字が2桁の11,22,...の場合も同様で
余り0,1,2が最低各３つずつあり、
３の倍数以外が８個あることはあり得ず問題に合いません。
置換数字が3桁の111,222,...の場合は
置換数字そのものの各桁和が3の倍数なので、置換数字はすべて３の倍数なので、
３で割るとその余りはすべて同じで、0,1,2のどれかです。
この場合は問題に合うことがあり得ます。
置換数字が4桁以上の場合も上記と同様なので、
置換数字の桁数は３の倍数です。...(D)
上記の４条件を使って絞り込みます。
４つの関数を使っています。
１．関数p(n)
・n以下の素数リストを返します。problem37と同じです。
２．関数h(n, L):
・数値nの、位置リストLの位置を0-9に置換した数値を返します。
指定位置の桁の値を置換数字で置換した値を返します。
・for i in xrange(10):
ループ変数iは置換数字です。0～9の値を順に取ります。
・t = ""
置換後数字を1桁ずつためていく変数です。初期値は""です。
・for j, k in enumerate(str(n)):
ループ変数kは数字nを上から1文字ずつ取り出した値で、jはそのときの0からの連番です。
・if j in L: t += str(i)
else: t += k
連番jがリストLに含まれていれば現在位置が置換位置なので、置換数字iをstr関数で文字型変換した値を付け足します。
そうでなければ数字nを上から1文字ずつ取り出した値kを付け足します。
・yield int(t)
yield文で値が１つ決まるごとに処理を一旦凍結して呼び出し元に値を返却します。そして再度呼び出されたら処理を再開し続行、次の値を処理します。
yield文では返却値が1つ決まるごとに処理凍結、値返却、処理再開を繰り返します。
このようにyield文で値を返す関数を「ジェネレータ関数」と呼びます。
これに対してreturn文で値を返し処理を終了してしまう関数は「イテレータ関数」といいます。
1つの関数の中にyield文とreturn文を両方含めることはできません。
３．関数g(m, n):
・数字mにn個含まれる構成文字とその位置リストの組を返します。
置換数字を置換する位置を求めるときに使います。
・d = {}
辞書dは数字mに含まれる各桁の値をキーに、その位置のリストを値として持ちます。初期値は空です。
・for i, t in enumerate(str(m)):
d[t] = d.get(t, [])+[i]
ループ変数iはenumerate関数による0からの連番で、数字mの中での左からの位置を示します。
ループ変数tは数字mの上から1文字ずつの値です。
get関数で、辞書dに数字mの上から1文字ずつの値tがキーとして存在すればtに対応する値を返し、存在しなければ空のリスト[]を返します。
これに0からの連番iだけをを要素に持つリストを連結することで、
数字mを構成する文字をキーとする、位置リストの辞書を作成します。
・for k,v in sorted(d.items()):
items関数で辞書dのキーと値の組をループ変数k,vとして取得します。
sorted関数でキー順に並べ替えます。
これは1122のように同じ件数の構成文字が複数種類ある場合、小さい順に処理するためです。
・if len(v)==n: yield int(k),v
ループ変数vは数字mの構成文字kの位置リストなので、len関数でその個数をみて、指定個数n個と等しければ、int関数で数値にした構成文字kとその位置リストを返します。
４．f():
・主処理です。
・for i in xrange(3, 100, 3):
ループ変数iは置換文字の桁数です。
絞り込み検討(D)より、置換数字の桁数は３の倍数なので、
3から100まで3飛びの値をとります。100というのはとりあえずの終了値です。
結果的にi=3のときに求める値に到達しました。
・for n in xrange(i+1, 100):
ループ変数nは全体桁数です。
絞り込み検討(C)より、全体桁数は置換数字の桁数よりも1以上多いので、
i+1から100までの値をとります。100というのはとりあえずの終了値です。
結果的にn=6のときに求める値に到達しました。
・P = [s for s in p(10**n) if s>10**(n-1)]
Pはn桁の素数リストです。
10**nは10のn乗、つまりn桁最大値+1なので、p(10**n)はn桁以下の素数リストです。
内包表記で、for文でn桁以下の素数リストから順番に1つずつ取得してsとして、後ろのif文に送り、n桁の最小値を超える値をforの前に送り、そのまま要素にします。
なお、n桁の最小値は1000などで決して素数ではありません。
例えばn=4の場合、p(10000)は9999以下の素数で、Pはこのうち1000を超える素数です。
・for j in P:
ループ変数jはn桁の素数リストから順に１つずつ取得します。
このjが求める値の候補です。
・for k,L in g(j, i):
ループ変数kとLには、関数gで算出した、
候補jの置換数字候補とその位置リストの組をそれぞれ設定します。
・if k>2: break
絞り込み検討(A)より、置換数字の最小値には0,1,2のどれかが含まれますので、置換数字候補が2を超えたら、次の候補jに進みます。
・if L[-1]>=n-1: break
絞り込み検討(B)より、置換数字は1の位にきませんので、
置換位置リストLの最後の値が全体桁数n-1以上ならば、次の候補jに進みます。
・t = 0
候補jの置換後数値についての、素数以外カウンターです。
素数判定の処理が重いで、10個中素数8個ということを素数以外が2個ということに代えて処理を軽くします。
・for u in h(j, L):
ループ変数uは置換後数値です。
関数hを使って、候補jの、位置リストLの位置の桁の値を0-9に置換した数値を１つずつ設定します。
・if u not in P: t += 1
置換後数値uが素数でなければ、素数以外カウンターをカウントアップします。
・if t>2: break
素数以外が２個以上（素数８個未満）が判明したら、次の値に処理を進めます。
・if t==2: return j
素数以外が２個（素数８個）で問題の条件に合いますので、候補jを返し処理を終了します。
５．関数の外
関数f()を呼び出し、その戻り値を出力します。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
121313
0 件のコメント:
コメントを投稿