エジプト式分数
エジプト式分数(エジプトしきぶんすう、単にエジプト分数とも、Egyptian fraction)とは、いくつかの異なる単位分数(分子が 1 の分数)の和、あるいは分数をそのように表す方式を意味する。例えば、通常 5 で表す分数を 1 + 1 などと表す。任意の正の有理数はこの形式で表すことができるが、表し方は一意ではない。この形式で分数を扱う方法は、古くは古代エジプトのリンド・パピルスに見られ、ヨーロッパでは中世まで広く用いられた。現代でも数論の分野において、エジプト式分数に端を発する数学上の未解決問題が多く残されている。
以下、特に断らない限り、単に「分数」といった場合、正の真分数、すなわち 0 より大きく 1 より小さな分数のみを考えているものとする。
例えば 2 は単位分数の和として 1 + 1 と表せるが、エジプト式分数では同じ単位分数を繰り返し用いることはせず、2 = 1 + 1 のように表す。いかなる分数に対してもこのような単位分数展開が必ず存在することは自明ではないが、後述するように今日ではあらゆる分数が無数に多くの単位分数展開を持つことが証明されている(#強欲算法の節参照)。さらに例を挙げると、3 = 1 + 1 + 1 = 1 + 1 + 1 + 1 であって、前者の展開は項数が最小であり、後者の展開は最大分母の値が最小である。このように、どのような単位分数展開が最も「単純」であるか、は明らかではない。
エジプト中王国では、ホルスの目を用いたそれ以前の不完全な分数体系(1 (k = 1, 2, …, 6) の和で表す)に替わって、エジプト式分数による方法が発達した。エジプト式分数が見られる古い文献としては、エジプト数学革巻き、モスクワ・パピルス、レイズナー・パピルス、カフン・パピルス、アクミム木刻版がある。特に有名なリンド・パピルスは、紀元前1650年頃に書かれたものであり、5 以上 101 以下の奇数 n に対して 2 を単位分数の和で表している(#リンド・パピルスの展開一覧の節参照)。
古代エジプト人が、いちいちこのように単位分数の和で表した理由については、よく分かっていない。ただ、リンド・パピルスにはパンを分け合う問題がいくつもあって、実際にパンを分け合うにはエジプト式の表示が理に適っている場合がある。例えば、リンド・パピルスの問題3は、6斤のパンを10人で分け合うとき、1人分は 1 + 1 であることを答とする。6斤のパンをそれぞれ5等分するよりも、5斤を1斤づつ2等分して1片ずつ取り、残りの1斤を10等分する方が簡単である。一方では、合理的とは思えない表示を選ぶ場合もある。リンド・パピルスの問題4は、7斤のパンを10人で分け合う問題であるが、1 + 1 ではなく、2 + 1 を答としている。2 は単位分数ではないから、この表示は狭い意味でエジプト式ではないが、古代エジプト人にとって 2 は特別な数であったらしい。2 = 1 + 1 であることを知っていたにもかかわらず、好んでこの数を用いている。
リンド・パピルスにおける 2 の表を参照すれば、分母が 100 以下の奇数である多くの分数が、機械的に単位分数の和で表せる。例えば、表より 2 = 1 + 1 であるから、
と計算できる。リンド・パピルスにおいて、2 に特に注意が払われているのは、古代エジプトの乗法アルゴリズムが2倍を基礎においているためであろう、とも考えられている。
古代エジプト人たちは、2 を唯一の例外として、単位分数のみを表記した。単位分数 1 を表すために、神官文字では点を、神聖文字では
<hiero>D21</hiero>
を n を表す記号の上に置いた。例えば
といった具合である。1 と 2 のみ、特別なグリフ
を持つ。2 のグリフは、正確には右の縦線が若干長い。長い方が 1 を、短い方が 1 を表し、全体としてはその和 3 の逆数を意味している。
現代の数学史家は、リンド・パピルスなどの古文書を調べ、古代エジプト人のエジプト式分数による計算方法がどのようなものであったかを研究した。特に、リンド・パピルスに書かれた 2 の表現がどのように得られたのかに注目し、様々な説を立てている。古代エジプト人が、分数を単位分数の和に表す系統的な方法を知っていたかどうかは不明であるが、少なくとも単一の方法のみを用いたのではなさそうである。恒等式 2 = 1 + 1 を用いれば、単一の方法で2つの単位分数の和に表せるにもかかわらず、分母が大きくなるのを嫌ってか、リンド・パピルスでは3項あるいは4項の和に表しているものもある。数学史家たちの分析によれば、分母が素数の場合と合成数の場合で、リンド・パピルスの著者は異なる方法を用いており、それぞれの場合においても複数の方法を用いている。
小さな奇素数 p = 2m + 1 (3, 5, 7, 11, 23) に対しては、恒等式 2 = 1 + 1 が用いられている。この方法は奇素数に限らず、任意の奇数に対して使用できる。
大きめの奇素数 p (13, 17, 19, 29, …) に対しては、恒等式 2 = 1 + 2A − p が用いられている。ここで、A は p < A < p を満たし、約数を多く持つ数が選ばれる。2A − p について、分子が A のいくつかの約数の和に表すことができれば、約分して単位分数の和を得る。例えば、p = 37 に対して A = 24 とすると、2A − p = 11 = 3 + 8 で 3 と 8 は 24 の約数であるから、リンド・パピルスの展開 2 = 1 + 1 + 1 を得る。A を取り替えたり、約数の和に分解する方法を変えたりすると別の展開を得る。
分母が2つの奇素数の積として pq であるとき、a = p + 1 として恒等式 2 = 1 + 1 を用いることができる。例えば、p = 3, q = 7 のとき、a = 2 より 2 = 1 + 1 を得る。この方法で、リンド・パピルスの単位分数展開のうち、分母が半素数であるものの多くは説明が付く。
分母が半素数の場合、r = p + q として恒等式 2 = 1 + 1 を用いることもできる。例えば、p = 5, q = 7 とすると、リンド・パピルスの表示 2 = 1 + 1 を得る。2 についても同様である。
その他の合成数 n については、n の約数 m に対する 1 の単位分数展開から得られる。例えば、2 = 1 + 1 + 1 を 5 で割ることにより、2 = 1 + 1 + 1 を得る。実際は、1 + 1 = 1 であるから、より簡単な展開を得るが、リンド・パピルスでは簡約化されていないものが記されている。3つ以上の素数の積、27, 45, 63, 75, 81, 99 に対してもこの方法で説明が付く。
リンド・パピルスの最後の単位分数展開 2 = 1 + 1 + 1 + 1 は、以上のどれにも当てはまらないが、恒等式 2 = 1 + 1 + 1 + 1 に p = 101 を代入して得られる。これと同等の等式は『エジプト数学羊皮紙巻子本』でも用いられている。
中国やインドでは、古くから分子に任意の自然数を許す今日の分数表現を用いたが、ヨーロッパでは17世紀頃までエジプト式が用いられていた。エジプト式分数は実用的な計算には向いておらず、これに固執したことが数学の発展を遅らせたと主張する歴史家もいる。一方で六十進法で数字を表記したバビロニアでは、早い段階から1未満の数を表すのに小数を導入していた。古代ローマの天文学者プトレマイオスは、著書『アルマゲスト』において「複雑な計算にはエジプト式分数ではなく六十進法を用いる」という趣旨の言を残している。これはプトレマイオスに限った話ではなく、多くの学者が天文計算に六十進法を用いており、角度を度数法で表す際の1度未満の度数単位や、1時間未満の時間の単位が六十進法であるのは、これに由来する。ロナルド・グラハムによると、20世紀を代表する数学者の一人アンドレ・ヴェイユは、古代エジプト人がエジプト式分数を用いたことについて「間違った方向へ進んだのだ」と語った。
1202年、フィボナッチは『算盤の書』において、任意の分数を単位分数の和に表すアルゴリズムをいくつか発表した。まず、分母 n が性質「n 未満の任意の自然数は、いくつかの n の約数の和で表せる」を持つとき、分子を n の約数の和で表して約分することにより、単位分数の和に表せる。そのような性質を持つ n は
1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, …(A5153)
と続くが、『算盤の書』では例として分母が 6, 8, 12, 20, 24, 60, 100 であるものについて、単位分数展開のリストを与えている。例えば、5 の分子 5 は、分母 12 の約数の和として 4 + 1 と表せるので、5 = 1 + 1 である。
分母がそのような性質を持たない場合について、フィボナッチは次のような方法を提示している。a に対して、b < c < b を満たし、多くの約数を持つ c を取る。ac の分子を bc の約数の和に表すことができれば、約分して単位分数の和となる。この方法は、リンド・パピルスの表に対して現代数学史家が推測した方法の一つと似ている。
のような恒等式を用いる。フィボナッチは、例として 8 を挙げた。まず、分母に 1 を加えた 12 を分子が割るように、2 + 6 と分解し、それから恒等式を適用して
を導いている。
以上のいずれの方法の通用しない場合に対して、フィボナッチは強欲算法(greedy algorithm) と呼ばれる方法を提案した。単位分数の和に展開しようとする分数に対して、それ以下の最大の単位分数を取る。それを引いた残りに対しても、繰り返し最大の単位分数を取る。式で書けば、分数 x を
\frac{x}{y}=\frac{1}{\lceil y/x\rceil}+\frac{x-(y\,\bmod\, x)}{y\lceil y/x\rceil}
と、次々に置き換える方法である。ここに、括弧は天井関数である。例えば、4 に強欲算法を適用すると、
となる。
フィボナッチは、強欲算法の手続きが有限回で終了することの証明を与えてはいない。後にシルベスターはこの方法を再発見し、有限回で終了することの証明も与え、1880年に発表した。実際、一度の手続きで分子は少なくとも 1 小さくなるので、a は多くとも a 個の単位分数の和で表せる。2人の名を取って、強欲算法は「フィボナッチ=シルベスターのアルゴリズム」とも呼ばれる。
フィボナッチ自身も注意したように、強欲算法はときに複雑な単位分数展開を与える。例えば、5 に強欲算法を適用すると、
となるが、ずっと簡潔な単位分数展開
を持つ。強欲算法は単純で分かりやすく、任意の分数が異なる単位分数の和で表せることの易しい証明も与えるが、このように複雑な展開になる場合もあるため、フィボナッチ自身は、最初の分解の後は他の方法を適用することを勧めている。
単位分数 1 に強欲算法を適用すると、恒等式
を得る。これより、単位分数は2つの単位分数の和に表せるので、任意の分数は無数に多くの単位分数展開を持つ。
現代の数論の研究者は、エジプト式分数に関する多くの問題について研究している。例えば、単位分数展開の項数や分母の大きさを評価すること、ある性質を持った単位分数に限った展開を与えること、単位分数展開のアルゴリズムを与えること、などである。リチャード・ガイの本『数論未解決問題の事典』第3版 D11 に、これまでの研究成果と未解決問題の概略がある。
任意に与えられた分数 x は、単位分数展開として、その最大分母が高々
O \left( \frac{y\log^2 y}{\log\log y} \right)
であるものを持つ。また、項数が高々
O \left( \sqrt{\log y} \right)
であるものを持つ。ここに、O はランダウの記号である。
グラハムは、2以上の任意の自然数 n に対し、分母を n 乗数に限った場合にエジプト式分数として表せるような有理数を特徴付けた。例えば、有理数 q がいくつかの平方数(1 を含める)の逆数の和として表せるための必要十分条件は、q が2つの半開区間の和集合
\left[ 0,\frac{\pi^2}{6}-1 \right) \cup \left[ 1,\frac{\pi^2}{6} \right)
に含まれることである。ここに現れる \frac{\pi^2}{6} は、リーマンゼータ関数 ζ の特殊値 ζ(2) である。
エルデシュとグラハムは、2 以上の整数の集合を有限個の集合に分割した場合、それがどのような分割であっても、そのうちの一つの集合の有限部分集合 S を取って
\sum_{n\in S} \frac{1}{n} =1
とできると予想した。予想の内容は、よく次のように言い換えられる。「単位分数を有限個の色でどのように色分けしても、そのうちの単色のみを用いて 1 の単位分数展開が得られる。」この予想は2003年に証明された。
エジプト式分数に関するオープンプロブレムを以下に挙げる。
任意の分数に対し、項数や最大分母が最小の単位分数展開を総当たり法で見つけることはできるが、この問題が計算複雑性理論においてどの複雑性クラスに属するのか、例えば多項式時間で見つけられるかは知られていない。
エルデシュ=シュトラウス予想は、すべての整数 n ≥ 2 に対し
\frac{4}{n} =
\frac{1}{x}
+ \frac{1}{y}
+ \frac{1}{z}
は正の整数解を持つ、という予想である。エルデシュ=シュトラウス予想が成り立つことは n < 1014 まで確かめられている。また、n が 840 を法として 12, 112, 132, 172, 192, 232 に合同な場合を除き、予想が成り立つことが示されている。
ヴァツワフ・シェルピニスキは、2以上の任意の整数 n に対し、
は正の整数解を持つと予想した。さらに「任意の整数 k に対し、n が十分大きければ、真分数 k は3つ以下の単位分数の和で表せる」とも予想した。
分母が奇数である単位分数に限れば、その和も分母が奇数になる。逆に、分母が奇数である分数は、分母が奇数である単位分数展開が可能であることが知られている。しかし、分母を奇数に限った場合に、強欲算法が有限回で終了するかどうかは知られていない。
単位分数展開は、しばしば数学パズルの題材にもなる。特に人気があるのは、1 の単位分数展開である。1 に対して強欲算法を用いると、有名な表示
1 = 1 + 1 + 1
を得る。
用いることができる単位分数に制限をかけると、より深みのある類似の問題が多く考えられる。例えば、分母を奇数に限ると、強欲算法によって 1 は13個の単位分数の和に表され、最後の項の分母は
となる。項数が最小なのは9項のものであり、そのようなものは全部で5通りあることが知られている。その中でも、最大分母が最小であるものは
1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
である。項数を度外視した場合、最大分母が最小であるものは、11項の和
1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
である。
1 の単位分数展開で分母の和が 50 および 100 となるものは、それぞれ
1 = 1 + 1 + 1 + 1 + 1,
1 = 1 + 1 + 1 + 1 + 1 + 1.
1 = 1 + 1 + 1 + 1 + 1 + 1,
1 = 1 + 1 + 1 + 1 + 1 + 1 + 1,
1 = 1 + 1 + 1 + 1 + 1 + 1 + 1.
である。
なお、正整数の逆数の和である調和級数は無限大に発散するから、(真分数に限らず)任意の正の有理数は単位分数の和で表すことができる。ただし、調和級数の発散は非常にゆっくりであるため、比較的小さな有理数であっても多くの単位分数が必要になる。例えば 10 を単位分数の和で表すには、2万個を超える項が必要である。
\frac{a}{\;n\;} = \frac{1}{\;x\;} + \frac{1}{\;y\;} + \frac{1}{\;z\;}
に対して,次の計算法が報告されている。
x=\bigg\lfloor \frac{\;n\;}{a} \bigg\rfloor + b,
y= \frac{\;2\,c\,n\,x\;}{d},
z= \frac{\;2\,c\,n\,x\;}{\;2\,c\,(a\,x-n)-d\;\;},
b=1,2,3,\cdots. \; \; \; \; c=1,2,3,\cdots. \; \; \; \; d=1,2,3,\cdots, c\,(a\,x-n).
上記の記号で,\lfloor \star \rfloor は,床関数である。
y の右辺 2cnx および,
z の右辺 2cnx が整除されれば解を得る。