【Project Euler】Problem 57: ２の平方根の収束分数

• 本記事はProjectEulerの「100番以下の問題の説明は記載可能」という規定に基づいて回答のヒントが書かれていますので、自分である程度考えてみてから読まれることをお勧めします。

問題 57. ２の平方根の収束分数

原文 Problem 57: Square root convergents

問題の要約：２の平方根を1000番目まで連分数展開したものを分数に収束させたとき分子の桁数が分母より大きいものの数を求めよ

要は$\sqrt{2}$の連分数展開$[1,2,2,2,2,\dots]$を分数に変換していくということですが、よく見ると以下のような漸化式が見えてきます。

E(i) = \frac{m}{n}　のとき　E(i+1) = \frac{2n+m}{n+m}

これに従ってプログラムを書くと、

m1, n1 = 1, 1
count = 0
for i in range(1000):
  m, n = 2*n1+m1, n1+m1
  if len(str(m)) > len(str(n)): count += 1
  m1, n1 = m, n
print(f"Answer: {count})

別解として、sympyには連分数を表す数列から分数を生成するcontinued_fraction_convergentsという関数があるので使ってみます。
残念ながら循環する連分数には対応していないようなので、2が1000個続く$[1,2,2,2,2,\dots]$という配列を作って入力しました。

from sympy.ntheory.continued_fraction import continued_fraction_convergents 
from sympy import fraction

cf = [1]+[2]*1000
it = continued_fraction_convergents(cf)
print(sum([len(str(x[0]))>len(str(x[1])) for x in [fraction(next(it)) for i in range(1000)]] )) 

（開発環境：Google Colab）