遊び tokidoki 仕事

数学と音楽と教育と遊び

| おしごと - きょういく - がくせい - ゼミ - イベント | すうがく - おんがく - 数理音楽 - DTM - かがく - scratch
| Art - photo - おきにー - Tips - ものもう - あれこれ | About - Top

連分数likeなエジプト分数分解

大学院向け某夜間授業で出された話題で,\dfrac{1}{n}をエジプト分数に分解するアルゴリズムの紹介がされた.
すぐに互いに素なm,nに対する\dfrac{m}{n}では如何?となるわけだが,連分数likeな展開方法を幾何学的意味と共に考えたので備忘録.
そういえば,連分数展開の力学系的意味を2年近く前のエントリーで書いていたっけ.
tokidoki.hatenablog.jp

互いに素な自然数a>bについて\dfrac{b}{a}を分子が1の単位分数の和に分解するときに,Greedy Algorithmを使う.
つまり,\dfrac{b}{a}を超えない,できるだけ分母の小さな単位分数\dfrac{1}{n}を探すと,それは
\begin{equation}
\frac{1}{n}<\frac{b}{a}<\frac{1}{n-1}
\end{equation}となるものだから, b(n-1) < a < bn である.すると  bn-a < b であり,また,
\begin{equation}
\frac{b}{a}-\frac{1}{n}=\frac{bn-a}{an} < \frac{b}{an}
\end{equation}と分子がもとより小さくなった分数 \dfrac{b_1}{a_1}=\dfrac{bn-a}{an} が得られる.以下同様な操作を続けると
\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}といった表示ができる.そして  b_1 > b_2 > \cdots > b_k となっていくので,やがて  b_k=1 となり,このアルゴリズムは止まる.もちろん, a_k,b_k が互いに素である関係は変わらない.

単位分数  \dfrac{1}{n} を求めて差を取ることは,幾何学的には \dfrac{b}{a}=\tan\theta_0 から \dfrac{b_1}{a_1}=\dfrac{bn-a}{an}=\tan\theta_1 を求める作業であり,下図でいけば黄色の三角形の傾きから赤い三角形の傾きを求めていることになる.
f:id:okiraku894:20190528110013p:plain

もちろん,この手順は無理数に対しても行えるわけで,それが楽しいかどうか分からないが,たとえば
\[
\pi=3+\frac{1}{8}+\frac{1}{61}+\frac{1}{5020}+\cdots
\]
だとか
\[
\sqrt{2}=1+\frac{1}{3}+\frac{1}{13}+\frac{1}{253}+\cdots
\]
とか現れる.う~ん,いまのところ楽しくないなぁ...