リンド・パピルスの分数

QuizKnockというユーチューブ・チャンネルをごぞんじですか？クイズ番組をユーチューブにしたチャンネルです。頻繁に更新されているので、日常的に視聴している人も多いのではないでしょか。近頃、リンド・パピルスの数学がクイズになっていました。

最後の問題で、分子が1の分数の話がでてきます。これを単位分数というそうです。

$\displaystyle\frac{5}{\;6\;}=\frac{1}{\;2\;}+\frac{1}{\;3\;}$

左辺の分数は右辺では単位分数の和になっています。古代エジプトでは、このように分数は単位分数の和で表していたそうです。ただし、その分母はすべて異なるものです。すべての分数は単位分数の和にできます。このことは、ウィキペディアの「エジプト式分数」のページに詳しく書かれています。

自分もエジプト式分数を見つける方法を考えてみました。

簡単な例

3/4を単位分数の和にしてみましょう。これは簡単で

$\displaystyle\frac{3}{\;4\;}=\frac{1}{\;2\;}+\frac{1}{\;4\;}$

さきほどの5/6でもそうですが、右辺の最初の分数の分母は元の分数の分母より小さくなっています。これが手がかりになります。

分数が単位分数の和に分解できること

もしも任意の分数が、

$\displaystyle\frac{a}{\;b\;}=(分母がbより小さい分数)+（単位分数）$

となればこの分数は単位分数に分解できます。

もしも第1項が単位分数ならば、すでに単位分数の和になっている
そうでなければ、第1項は「（より分母が小さい分数）＋（単位分数）」にすることができる。

これを繰り返すとどんどん第1項の分母が小さくなりますが、最も小さくなったとすると分母は2になります。分母が2の分数は1/2しかありませんから単位分数です。

いずれの場合も右辺は単位分数の和になることがわかります。

不定方程式

$\displaystyle\frac{a}{\;b\;}=\frac{c}{\;d\;}+\frac{1}{bd}$

となったとしましょう。ここで、文字はすべて2以上の整数で、d<bとします。すなわち、分数a/bは「より小さい分母の分数と単位分数の和」になったとします。分母を払うと

$ad-bc=1$

となります。これは不定方程式です。aとbが互いに素ならば解c、dが存在し、dをb以下にとることができます。このようにして、この問題は不定方程式に帰着させることができます。

例

具体例をあげましょう。 3/7を単位分数の和にしてみます。

$3d-7c=1$
$3d\equiv 1\equiv 15 \quad\pmod{7}$
$d=5,\;c=2$
$\displaystyle\frac{3}{\;7\;}=\frac{2}{\;5\;}+\frac{1}{35}$

ここまでで、より小さな分母の分数と単位分数の和になりました。第1項に同じことをします。

$2d-5c=1$
$2d\equiv 1\equiv 6\quad\pmod{5}$
$d=3,\;c=1$
$\displaystyle\frac{2}{\;5\;}=\frac{1}{\;3\;}+\frac{1}{15}$

これより

$\displaystyle\frac{3}{\;7\;}=\frac{1}{\;3\;}+\frac{1}{15}+\frac{1}{35}$

となります。

分解のしかたは一意でない

この方法で分解すると、答えはひとつしかでてきませんが、分解は一意ではありません。たとえば、

$\displaystyle\frac{2}{21}=\frac{1}{12}+\frac{1}{84}=\frac{1}{14}+\frac{1}{42}$

このように、2種類以上の単位分数の和が存在します。

上記のアルゴリズムが良いとはいえない。

上記の不定方程式を使ったアルゴリズムで求めた単位分数の和が良いとはいえません。例えば、5/6は

$\displaystyle\frac{5}{\;6\;}=\frac{1}{\;2\;}+\frac{1}{\;3\;}$

という簡単な分解がありますが、不定方程式のアルゴリズムを使うと

$\displaystyle\frac{5}{\;6\;}=\frac{1}{\;2\;}+\frac{1}{\;6\;}+\frac{1}{12}+\frac{1}{20}+\frac{1}{30}$

となります。このように和が長くなるのは良いとはいえないでしょう。ちなみに、右辺は高校の数列で習う部分分数分解のパターンになっています。

$\begin{align*} & \frac{1}{\;2\;}+\frac{1}{\;6\;}+\frac{1}{12}+\frac{1}{20}+\frac{1}{30}\\ &= \frac{2-1}{\;1\times 2\;}+\frac{3-2}{\;2\times 3\;}+\frac{4-3}{3\times 4}+\frac{5-4}{4\times 5}+\frac{6-5}{5\times 6}\\ &= \left(\frac{1}{\;1\;}-\frac{1}{\;2\;}\right)+\left(\frac{1}{\;2\;}-\frac{1}{\;3\;}\right)+\left(\frac{1}{\;3\;}-\frac{1}{\;4\;}\right)+\left(\frac{1}{\;4\;}-\frac{1}{\;5\;}\right)+\left(\frac{1}{\;5\;}-\frac{1}{\;6\;}\right)\\ &= 1-\frac{1}{\;6\;}\\ &= \frac{5}{\;6\;} \end{align*}$

ウィキペディアの記事には、単位分数に分解する別の方法も紹介されているので参考にしてください。

プログラム

アルゴリズムが確定しているので、これをプログラム化できます。 Rubyで作ったものをGitHubにあげました。

おもこん

おもこんは「思いつくままにコンピュターの話し」の省略形です