最近趣味としてやっているProject Eulerの自分なりの解答です。問題 50までは結構解答あったので51からやります。コード読みづらくてすいません…
問題 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つの素数が得られる最小の素数を求めよ. (注:連続した桁でなくても良い)
解答
今回の使ったポイントは次の3つです。
1. □の数は3の倍数個である必要がある。
2. 条件を満たす素数は4桁以上である必要がある。
3. 素数が8個出るには□が0,1,2のいづれかであるとき素数である必要がある。
1について少し解説します。
なぜ３の倍数個でなければいけないのか？
結論から言ってしまうと、３の倍数個でないときでは置き換えによって現れる10個の数字のうち3つ以上が素数ではなく(具体的には3の倍数)になってしまうからだ。
3の倍数になるかどうかの判定として各桁を足して３の倍数となるかどうかというものがある。
ここで置き換えにによって現れる数字の各桁をを足すと次のようになる。
$$b \cdot n+c$$
ただし、$b$は□の値、$n$は□の個数、$c$は□以外の桁の和
ここで$n$(□の個数)を３の倍数でないとすると次の２パターンのどちらかになる。
\begin{align}
b \cdot n+c &= b \cdot (3k+1)+c \\
&= 3bk+b+c
\end{align}
\begin{align}
b \cdot n+c &= b \cdot (3k+2)+c \\
&= 3bk+2b+c
\end{align}
$3bk+b+c$も$3bk+2b+c$も3つごとに３の倍数になるので置き換えによって３の倍数が３個または４個現れることになる。よって□の個数は3の倍数である。
話は戻って1,2,3を取り入れコードを書く。
import sympy as sym
from itertools import combinations
def make_num(n,star_pos,star_num):
n_list = list(n)
for i in star_pos:
n_list[i] = star_num
return int(''.join(n_list))
def make_star_pos(n_list,x,star_tpl):
x_num = 0
star_pos = list()
for pos in range(len(n_list)):
if n_list[pos] == str(x):
if x_num in star_tpl:
star_pos.append(pos)
x_num += 1
return star_pos
def main(number):
n_max = 8
for k in range(4,n_max):
prime = [i for i in sym.primerange(10**(k-1), 10**k)] # k桁の素数
for n in prime:
n_str = str(n)
n_list = list(n_str)
for x in range(3): # 0,1,2が3つ以上必要
a = n_str.count(str(x))
if a >= 3:
for i in range(3, a+1, 3): # i:*の数
for star_tpl in combinations(( j for j in range(a)), i):
star_pos = make_star_pos(n_list,x,star_tpl)
num_sum = 0
for star_num in '0123456789':
if star_pos[0] == 0 and star_num == '0':
continue
made_num = make_num(n_list,star_pos,star_num)
if made_num in prime:
num_sum += 1
if num_sum == number:
return n
print(main(8))
各桁数の素数のリストを作り、それを下から調べて行った。
15.353 seconds
1桁目は□にならない
ということに注意するともうちょっと速くなるはずなのですが書いているときは気づきませんでした。
ちなみに□の位置を先に決めて残りの数字埋めるアルゴリズムも考えたけど条件に合う数字が出た瞬間に最小性が確定しないのでやめた。
