Project Euler 57をPythonでやってみる

問題57

英語
https://projecteuler.net/problem=57
日本語
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2057

解答57

この問題の第$n$項目の連分数を$a_n$とすると1〜4項目は以下のようになる。

\begin{align}
a_1 &= 1+\cfrac{1}{2} = \cfrac{3}{2} \\
a_2 &= 1+\cfrac{1}{2+\cfrac{1}{2}}=\cfrac{7}{5} \\
a_3 &= 1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2}}}=\cfrac{17}{12} \\
a_4 &= 1+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2+\cfrac{1}{2}}}}=\cfrac{41}{29}
\end{align}

上の4つにおいて次の$*$の部分に注目する。

1+\cfrac{1}{*}

すると、$*$は前の項に1を足したものになっていることが分かる。
この関係を漸化式にすると次のようになる。

a_{n+1}=1+\cfrac{1}{a_n+1}

さらに$a_m$の分子を$N_m$ , 分母を$D_m$とおくと次のような関係が分かる。($N_m,D_m$は互いに素)

\begin{align}
a_{m+1} = \cfrac{N_{m+1}}{D_{m+1}} &= 1+\cfrac{1}{1+\cfrac{N_m}{D_m}} \\
&= 1+\cfrac{D_m}{N_m+D_m} \\
&= \cfrac{N_m+2 \cdot D_m}{N_m+D_m}
\end{align} \\
\therefore N_{m+1} = N_m+2 \cdot D_m \\
N_{m+1} = N_m+D_m

ここまで分かったのであとは分母と分子をそれぞれ更新して桁数をチェックしていけばいいです。
コードは次のようになります。

ProjectEuler51.py

def next(num_tpl):
    return (num_tpl[0]+2*num_tpl[1],num_tpl[0]+num_tpl[1])

count = 0
fraction = (3,2)
for i in range(1,1000):
    fraction = next(fraction)
    if len(str(fraction[0])) > len(str(fraction[1])):
        count += 1

print(count)

0.091 seconds