Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

Project Euler 51をPythonでやってみる

More than 1 year has passed since last update.

最近趣味としてやっている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について少し解説します。
なぜ3の倍数個でなければいけないのか?
結論から言ってしまうと、3の倍数個でないときでは置き換えによって現れる10個の数字のうち3つ以上が素数ではなく(具体的には3の倍数)になってしまうからだ。
3の倍数になるかどうかの判定として各桁を足して3の倍数となるかどうかというものがある。
ここで置き換えにによって現れる数字の各桁をを足すと次のようになる。
$$b \cdot n+c$$
ただし、$b$は□の値、$n$は□の個数、$c$は□以外の桁の和
ここで$n$(□の個数)を3の倍数でないとすると次の2パターンのどちらかになる。

\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の倍数になるので置き換えによって3の倍数が3個または4個現れることになる。よって□の個数は3の倍数である。

話は戻って1,2,3を取り入れコードを書く。

ProjectEuler51.py
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桁目は□にならない
ということに注意するともうちょっと速くなるはずなのですが書いているときは気づきませんでした。

ちなみに□の位置を先に決めて残りの数字埋めるアルゴリズムも考えたけど条件に合う数字が出た瞬間に最小性が確定しないのでやめた。

you1111
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away