日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。
問１１１「重複桁を持つ素数」
重複した桁を含む 4 桁の素数を考える.
全てが同じにならないのは明らかである:
1111 は 11 で割り切れ, 2222 は 22 で割り切れ, 以下同様だからである.
しかし 3 個の 1 を含む 4 桁の素数は 9 つある:
1117, 1151, 1171, 1181, 1511, 1811, 2111, 4111, 8111
n 桁の素数に対する重複した桁の最大個数を M(n, d) と表すことにしよう.
ここで d は重複した桁とする.
またそのような素数の個数を N(n, d) と表し, これらの素数の和を S(n, d) と表す.
よって M(4, 1) = 3 は, 重複した桁を 1 としたときの,
4 桁の素数に対する重複した桁の最大個数である.
そのような素数は N(4, 1) = 9 個あり, これらの素数の和は S(4, 1) = 22275 である.
d = 0 に対しては, 重複した桁は M(4, 0) = 2 個だけ可能であることが分かるが,そのような場合は N(4, 0) = 13 個ある.
同じようにして 4 桁の素数に対して次の結果を得る.
| Digit, d | M(4, d) | N(4, d) | S(4, d) |
| 0 | 2 | 13 | 67061 |
| 1 | 3 | 9 | 22275 |
| 2 | 3 | 1 | 2221 |
| 3 | 3 | 12 | 46214 |
| 4 | 3 | 2 | 8888 |
| 5 | 3 | 1 | 5557 |
| 6 | 3 | 1 | 6661 |
| 7 | 3 | 9 | 57863 |
| 8 | 3 | 1 | 8887 |
| 9 | 3 | 7 | 48073 |
d = 0 から 9 に対して, S(4, d) の総和は 273700 である.
S(10, d) の総和を求めよ.
注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。
私の回答例は以下の通りです。
def h(n):
import itertools
if n==2: return True
if n<2 or (not n%2): return 0
for i in itertools.islice(itertools.count(3, 2), None):
if i*i>n: break
if not n%i: return 0
return n
def g(M, w):
L = []
for s in M:
if s[0]=="0":
for t in w:
L.append(t+s)
else:
for i in xrange(len(s)+1):
for t in w:
if i==0 and t=="0": continue
L.append(s[:i]+t+s[i:])
return L
def f(n):
SS = 0
for d in xrange(10):
w = [str(i) for i in xrange(10) if i!=d]
S, M = 0, n
while S==0:
M -= 1
L = [str(d)*M]
for i in xrange(n-M): L = g(L, w)
L = set(L)
for t in L: S += h(int("".join(t)))
SS += S
return SS
n=10
s = f(n)
print s
素数を発生させて重複桁があるかチェックする方式でやってみたところ、チェック以前に10桁分の素数の発生がとても1分で終わらないことが判明しました。
そこで、やり方を逆にして、まず重複桁の値を決め、その他の値を重複桁の間や両側に付加して候補値を作り、素数チェックをするようにしました。
１．関数h(n)
・素数ならｎ、素数以外なら0を返します。
・問５８の 素数判定関数を改良しました。
・forループではxrange関数で数値を発生させていましたが、
10桁の整数の途中からオーバーフローになるので
itertoolsモジュールのislice関数を使うように改良しました。
２．関数g(M, w)
・リストMの全要素の両端や文字間に、リストwから取り出した１文字を付加した値を作りリストにまとめて返します。
但し、後で数値化したときに桁数が減ってしまうことを避けるために、
リストMの各要素の先頭が0の場合は左端にだけ付加し、
付加する文字が0の場合は左端以外にだけ付加します。
３．関数f(n)
・n桁の素数について問題文のSの合計を返します。
・ループ変数dは重複する桁の値で、0から9の値をとります。
・リストwは重複しない桁の値で、0から9のうち、dと異なる値を持ちます。
・変数Sは、dが重複するn桁の素数の和です。
・変数Mは、重複する桁dの個数です。
・while文では変数Mを１つずつ減らしながらSを計算し0以外になれば終了します。
・変数iは、全体n桁のうちd以外の値の個数です。
・リストLは、関数gでd以外の値をi個付加した候補値のリストです。
リストLの要素を１つずつ取り出し、連結して数値化し、関数hで素数判定します。
素数ならば、変数Sに累積していきます。
・whileループを抜けたら、SをSSに累積して、次のdでの処理に続きます。
解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
612407567715
