大学院向け某夜間授業で出された話題で,をエジプト分数に分解するアルゴリズムの紹介がされた.
すぐに互いに素なに対するでは如何?となるわけだが,連分数likeな展開方法を幾何学的意味と共に考えたので備忘録.
そういえば,連分数展開の力学系的意味を2年近く前のエントリーで書いていたっけ.
tokidoki.hatenablog.jp
互いに素な自然数についてを分子が1の単位分数の和に分解するときに,Greedy Algorithmを使う.
つまり,を超えない,できるだけ分母の小さな単位分数を探すと,それは
\begin{equation}
\frac{1}{n}<\frac{b}{a}<\frac{1}{n-1}
\end{equation}となるものだから, である.すると であり,また,
\begin{equation}
\frac{b}{a}-\frac{1}{n}=\frac{bn-a}{an} < \frac{b}{an}
\end{equation}と分子がもとより小さくなった分数 が得られる.以下同様な操作を続けると
\begin{equation}
n_{k+1}=\left\lceil\frac{a_k}{b_k}\right\rceil,\quad a_{k+1}=a_kn_{k+1},\quad b_{k+1}=b_kn_{k+1}-a_k,
\end{equation}あるいは,連分数エントリーの真似をすると
\begin{equation}
n_{k+1}=\left\lceil\frac{a_k}{b_k}\right\rceil,\quad \begin{pmatrix} a_{k+1} \\ b_{k+1} \end{pmatrix}=\begin{pmatrix}n_{k+1} & 0\\ -1 & n_{k+1}\end{pmatrix}\begin{pmatrix}a_k\\ b_k\end{pmatrix}
\end{equation}といった表示ができる.そして となっていくので,やがて となり,このアルゴリズムは止まる.もちろん, が互いに素である関係は変わらない.
単位分数 を求めて差を取ることは,幾何学的には から を求める作業であり,下図でいけば黄色の三角形の傾きから赤い三角形の傾きを求めていることになる.
もちろん,この手順は無理数に対しても行えるわけで,それが楽しいかどうか分からないが,たとえば
\begin{equation}
\pi=3+\frac{1}{8}+\frac{1}{61}+\frac{1}{5020}+\cdots
\end{equation}
だとか
\begin{equation}
\sqrt{2}=1+\frac{1}{3}+\frac{1}{13}+\frac{1}{253}+\cdots
\end{equation}
とか現れる.う~ん,いまのところ楽しくないなぁ...