エジプト分数形式

はじめに

4000年前、分数は既に存在していた。
しかし当時、分子に1以外を取ることは間違いであると考えられていた。
そこでエジプトの民はエジプト分数形式を作り上げた。

的な話です。

エジプト分数形式

上述しているとおり、4000年前のエジプトでは分数に1以外を取ることは間違いであるとされてきました。
そのため、当時の分数では分子が1の分数を複数足し合わせたものをエジプト分数形式として利用していました。
e.g.)

フィボナッチの貪欲アルゴリズム

それから幾星霜、フィボナッチさんが分数をエジプト分数形式に変換するアルゴリズムを定義しました。
これは現在でも正当とされています。すごいですね。

アルゴリズム自体は簡単です。$ \eqref{eq: algorithm} $ $$ \begin{equation} \begin{split} e\bigl(\frac{x}{y}\bigr) &= \frac{1}{\lceil \frac{y}{x}\rceil} + e(r) \\ ただし r &= \frac{-y \bmod x}{y \times \lceil \frac{y}{x} \rceil} \end{split} \label{eq: algorithm} \end{equation} $$

上記をpythonにしたのが次となります。

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import math
from functools import reduce

def calc(numerator, denominator):
    return "{0}/{1} = ".format(numerator, denominator) + reduce(lambda a, b: "{0} + {1}".format(a, b), map(lambda x: "1/{0}".format(x), inner_calc(numerator, denominator)))

def inner_calc(numerator, denominator):
    denominators = []
    denominators.append(math.ceil(denominator / numerator))
    nn = -denominator % numerator
    nd = denominator * math.ceil(denominator / numerator)
    if nn > 1:
        denominators.extend(inner_calc(nn, nd))
    elif nn == 1 :
        denominators.append(nd)
    return denominators

これはcalc関数に対して第１引数に分子、第２引数に分母の値を与えることで、
それをエジプト分数形式にした文字列を返します。

print(calc(2, 5))
print(calc(3, 5))
print(calc(1023, 1024))
>>> 2/5 = 1/3 + 1/15
>>> 3/5 = 1/2 + 1/10
>>> 1023/1024 = 1/2 + 1/3 + 1/7 + 1/44 + 1/9462 + 1/373029888

おわりに

このアルゴリズムは簡単なアルゴリズムで、かつ正当であるとされていますが、
得られた解が最適であることは保証しません。

他に最適な解があったとしても、それを走査するような機能がないからです。 しかし、このエジプト分数形式はまだまだ謎が多く、効率的な算出方法は未だわかっていないんですって。