2020.10.17記
ラメの定理
(1) は の連分数展開が となることを表している。これを逆に辿る形で,, という漸化式で を求めると, に収束する有理数列が得られる.
(2) は黄金比の連分数展開が となることを表している.ついでに
となる.
(3) は有理数の連分数展開が有限回で終ることを示している.
(1) であり, から となるので,
となる.
(2) は以上なので0ではない.
()とすると,その逆数は1より大きく3以下となるので、 は または のいずれかで、
から,
から となる.
(ここまで文系)
(3) が有理数 (分子と分母が互いに素)のとき, は分母が「 を で割った余りを分母とする有理数となる.但し,ユークリッドの互除法により,割った余りが最大公約数になったときは整数となる.
分母は単調減少なので、またはそれ以前で最大公約数が求まり,整数となって,その次の項は0となっているので, となり,それ以降は 0 である.
ユークリッドの互除法で最大公約数を求める回数で0になるので, よりはずっと少ない回数で終る(一回目の割算で次の分母が最初の分子以下となるので、 よりも の方が意味がある).
一番計算回数が多いのはフィボナッチ数列の隣り合う項の場合だから, が 以下なら 回以下で終了することがわかり,は大体 であるから,最初の分子が の場合, 回以下で終ることになる.
と数値的に評価することによって, 回以下で終ることが導かれる(ラメの定理).
ではラメの定理の等号が成立する場合であるが, と となる場合に 15 回で終わる.この例は
プログラミングの背景:数論 ユークリッドの互除法
に書いてあった.
www.tbasic.org
から辿れる.
2023.09.16記
本問と関連して,
2019年(平成31年)大阪大学-数学(理系)[4] - [別館]球面倶楽部零八式markIISR
のカルキン・ウィルフツリーも参照しておくと良い.