https://spherical-harmonics.hateblo.jp/entry/Todai/2011/Rika

問題：2011年(平成23年)東京大学前期-数学(理科) - [別館]球面倶楽部零八式markIISR

2020.10.17記

本問のテーマ

(1) は $\sqrt{2}$ の連分数展開が $\sqrt{2}-1=\dfrac{1}{2+\dfrac{1}{2+\dfrac{1}{2+\cdots}}}$ となることを表している。これを逆に辿る形で， $b_{n+1}=1+\dfrac{1}{1+b_n}$ ， $b_1=1$ という漸化式で $b_n$ を求めると， $\sqrt{2}$ に収束する有理数列が得られる．

(2) は黄金比の連分数展開が $\dfrac{\sqrt{5}-1}{2}=\dfrac{1}{1+\dfrac{1}{1+\dfrac{1}{1+\cdots}}}$ となることを表している．ついでに
$\dfrac{\sqrt{n^2+4}-n}{2}=\dfrac{1}{n+\dfrac{1}{n+\dfrac{1}{n+\cdots}}}$ となる．

(3) は有理数の連分数展開が有限回で終ることを示している．

[解答]

(1) $a_1=\sqrt{2}-1$ であり， $\dfrac{1}{a_1}=\sqrt{2}+1$ から $a_2=\sqrt{2}-1=a_1$ となるので，
$a_n=\sqrt{2}-1$ となる．

(2) $a$ は $\dfrac{1}{3}$ 以上なので0ではない．

$a_1=a$ （ $\dfrac{1}{3}\leqq a\lt 1$ ）とすると，その逆数は1より大きく3以下となるので、 $a_2$ は $\dfrac{1}{a}-1$ または $\dfrac{1}{a}-2$ のいずれかで、
$a=\dfrac{1}{a}-1$ から $a=\dfrac{\sqrt{5}-1}{2}$ ，
$a=\dfrac{1}{a}-2$ から $a=\sqrt{2}-1$ となる．

(ここまで文系)

(3) $a_k$ が有理数 $\dfrac{p_k}{q_k}$ （分子と分母が互いに素）のとき， $a_{k+1}$ は分母が「 $p_k$ を $q_k$ で割った余りを分母とする有理数となる．但し，ユークリッドの互除法により，割った余りが最大公約数になったときは整数となる．

分母は単調減少なので、 $a_{q-1}$ またはそれ以前で最大公約数が求まり，整数となって，その次の項は0となっているので， $a_q=0$ となり，それ以降は 0 である．

ユークリッドの互除法で最大公約数を求める回数 $+1$ で0になるので， $q$ よりはずっと少ない回数で終る（一回目の割算で次の分母が最初の分子以下となるので、 $q$ よりも $p$ の方が意味がある）．

ラメの定理

一番計算回数が多いのはフィボナッチ数列 $\{F_n\}$ の隣り合う項の場合だから， $p$ が $F_k$ 以下なら $k-1$ 回以下で終了することがわかり， $F_k$ は大体 $\dfrac{1}{\sqrt{5}}\Bigl(\dfrac{1+\sqrt{5}}{2}\Bigr)^k \lt \Bigl(\dfrac{1+\sqrt{5}}{2}\Bigr)^{k-1}$ であるから，最初の分子が $p$ の場合， $\dfrac{\log_{10} p}{\log_{10}\dfrac{1+\sqrt{5}}{2}}$ 回以下で終ることになる．
$\log_{10}\dfrac{1+\sqrt{5}}{2}\gt \dfrac{1}{5}$ と数値的に評価することによって， $5\log_{10} p$ 回以下で終ることが導かれる（ラメの定理）．

ではラメの定理の等号が成立する場合であるが， $F_{17}=1597$ と $F_{16}=987$ となる場合に 15 回で終わる．この例は
プログラミングの背景：数論　ユークリッドの互除法
に書いてあった．
www.tbasic.org
から辿れる．

2023.09.16記
本問と関連して，
2019年(平成31年)大阪大学-数学(理系)[4] - [別館]球面倶楽部零八式markIISR
のカルキン・ウィルフツリーも参照しておくと良い．