エジプト式分数

同義語：単位分数の和Egyptian fraction

概要

前提知識: ガウス記号と整数の個数, 数学的帰納法と整列性

高校での出発点：分数を単位分数に分ける

分子が $1$ の分数 $\dfrac12,\dfrac13,\dfrac14,\ldots$ を 単位分数 という。$\dfrac34=\dfrac12+\dfrac14$ のように、分数を「互いに異なる単位分数の和」に分けることを考える。$\dfrac23=\dfrac13+\dfrac13$ のように同じ単位分数を並べてよいなら、$\dfrac mn$ は $\dfrac1n$ を $m$ 個並べればよいので、異なる単位分数に限る。

小さい分数を分ける

$\dfrac34$：$\dfrac34$ 以下で最も大きい単位分数は $\dfrac12$ で、$\dfrac34-\dfrac12=\dfrac14$ は単位分数である。よって $\dfrac34=\dfrac12+\dfrac14$ である。
$\dfrac25$：$\dfrac12>\dfrac25$ なので $\dfrac12$ は使えない。$\dfrac13\le\dfrac25$ なので、$\dfrac25$ 以下で最も大きい単位分数は $\dfrac13$ である。$\dfrac25-\dfrac13=\dfrac{6-5}{15}=\dfrac1{15}$ なので、$\dfrac25=\dfrac13+\dfrac1{15}$ である。
$\dfrac23$：$\dfrac23-\dfrac12=\dfrac{4-3}6=\dfrac16$ なので、$\dfrac23=\dfrac12+\dfrac16$ である。

ex-egf-start では、「残りの分数以下で最も大きい単位分数を引く」ことを繰り返した。1 回で終わらない例で、同じことを続けてみる。

$\dfrac4{13}$ を分ける

$\dfrac14\le\dfrac4{13}<\dfrac13$ である（$13\le16$ と $12<13$ から）。$\dfrac4{13}$ 以下で最も大きい単位分数は $\dfrac14$ で、
$$ \frac4{13}-\frac14=\frac{16-13}{52}=\frac3{52} $$
が残る。
$\dfrac1{18}\le\dfrac3{52}<\dfrac1{17}$ である（$52\le54$ と $51<52$ から）。$\dfrac1{18}$ を引くと
$$ \frac3{52}-\frac1{18}=\frac{3\cdot18-52}{52\cdot18}=\frac2{936}=\frac1{468} $$
が残り、これは単位分数である。
よって
$$ \frac4{13}=\frac14+\frac1{18}+\frac1{468} $$
である。残りの分数の分子は、約分する前の形で $4\to3\to2$ と減っている。

長さ 4/13 の帯から、1/4、1/18、1/468 を順に切り取ると帯がちょうどなくなる。1/468 は細すぎるので拡大して示した
$\dfrac4{13}$ は 3 回で終わったが、いつも有限回で終わるのだろうか。この記事で答える問いは次の 3 つである。

「最も大きい単位分数を引く」ことを繰り返すと、必ず有限回で止まるか。出てくる単位分数は互いに異なるか。→ thm-egf-greedy
表し方は 1 通りか。→ thm-egf-infinite

この方法で得た表し方は、項の数が最も少ないか。→ ex-egf-not-shortest

高校の計算	この記事の言葉	大学の言葉
分子が $1$ の分数	単位分数	有理数の分解
最も大きい単位分数を引く	貪欲法	貪欲アルゴリズム
分子が減っていく	止まる理由	整列性（無限降下の不可能性）
$\dfrac1k=\dfrac1{k+1}+\dfrac1{k(k+1)}$	表し方は無数	分解の非一意性

言葉の準備：エジプト式分数と貪欲法

エジプト式分数による表し方

正の整数 $d$ について、$\dfrac1d$ の形の分数を 単位分数 という。正の有理数 $r$ を、互いに異なる有限個の単位分数の和
$$ r=\frac1{d_1}+\frac1{d_2}+\cdots+\frac1{d_k}\qquad(d_1< d_2<\cdots< d_k) $$
に書くことを、$r$ の エジプト式分数による表し方 といい、右辺を エジプト式分数 という。$k$ を表し方の項数という。

分母を小さい順に並べて書くことにすれば、「互いに異なる」は $d_1< d_2<\cdots< d_k$ と同じである。

エジプト式分数の例

$\dfrac56=\dfrac12+\dfrac13$（項数 2）。
$1=\dfrac12+\dfrac13+\dfrac16$（項数 3）。項数 3 で $1$ を表す単位分数の組を、同じ分数を許して探すと $\left(\dfrac12,\dfrac13,\dfrac16\right)$、$\left(\dfrac12,\dfrac14,\dfrac14\right)$、$\left(\dfrac13,\dfrac13,\dfrac13\right)$ の 3 組がある（不定方程式の解法の命題「$\dfrac1x+\dfrac1y+\dfrac1z=1$ の正の整数解」）。このうち 3 つが互いに異なるのは最初の組だけである。
$\dfrac34=\dfrac12+\dfrac14=\dfrac12+\dfrac15+\dfrac1{20}$。1 つの数に項数の違う表し方がある。

ex-egf-start と ex-egf-start2 で使った手順に名前を付ける。

貪欲法

$0< r<1$ の有理数 $r$ に対して、次の手順を 貪欲法 という。
(R1) $\dfrac1d\le r$ を満たす最小の正の整数 $d$（$r$ 以下で最も大きい単位分数の分母）を選び、$\dfrac1d$ を書き出す。
(R2) $r$ を $r-\dfrac1d$ に置きかえる。
(R3) $r=0$ になったら止める。そうでなければ条件 (i) にもどる。

$r=\dfrac mn$ のとき、$\dfrac1d\le\dfrac mn$ は $d\ge\dfrac nm$ と同じなので、選ぶ $d$ は $\dfrac nm$ 以上の最小の整数（$\dfrac nm$ の切り上げ）である。つまり $d$ は
$$ d-1<\frac nm\le d $$
を満たすただ 1 つの整数である。$\dfrac nm$ が整数なら $d=\dfrac nm$、整数でなければ $d=\left[\dfrac nm\right]+1$ である（$[\ ]$ はガウス記号。ガウス記号と整数の個数）。

貪欲法で選ぶ分母

$r=\dfrac4{13}$：$\dfrac{13}4=3.25$ なので $d=4$ である。
$r=\dfrac3{52}$：$\dfrac{52}3=17.33\cdots$ なので $d=18$ である。
$r=\dfrac25$：$\dfrac52=2.5$ なので $d=3$ である。
$r=\dfrac2{10}$：$\dfrac{10}2=5$ は整数なので $d=5$ で、$\dfrac2{10}-\dfrac15=0$ となり 1 回で止まる。

1 回引いた後の分子が、もとの分子より小さくなることが鍵である。

1 回引くと分子が減る

$m$、$n$ を正の整数とし、$0<\dfrac mn<1$ とする。$d$ を $d-1<\dfrac nm\le d$ を満たす整数とすると、$d\ge2$ であり
$$ \frac mn-\frac1d=\frac{md-n}{nd},\qquad 0\le md-n< m $$
が成り立つ。さらに $md-n>0$ のとき、残り $r'=\dfrac{md-n}{nd}$ は
$$ 0< r'<\frac1{d(d-1)} $$
を満たす。

$d$ の不等式に $m$ を掛ける

$\dfrac mn<1$ より $\dfrac nm>1$ なので、$d\ge\dfrac nm>1$ から $d\ge2$ である。通分すると $\dfrac mn-\dfrac1d=\dfrac{md-n}{nd}$ である。
不等式 $d-1<\dfrac nm\le d$ の各辺に正の数 $m$ を掛けると $m(d-1)< n\le md$ である。右側の不等式から $md-n\ge0$、左側の不等式から $md-m< n$、つまり $md-n< m$ が得られる。
後半。$\dfrac nm>d-1$ から $\dfrac mn<\dfrac1{d-1}$（$d-1\ge1$ なので両辺の逆数をとれる）なので
$$ r'=\frac mn-\frac1d<\frac1{d-1}-\frac1d=\frac{d-(d-1)}{d(d-1)}=\frac1{d(d-1)} $$
である。$r'>0$ は $md-n>0$ から従う。

主定理 1：貪欲法は有限回で止まる

貪欲法は止まる

$0<\dfrac mn<1$（$m$、$n$ は正の整数）に貪欲法を行うと、高々 $m$ 回で止まる。書き出した単位分数を $\dfrac1{d_1},\dfrac1{d_2},\ldots,\dfrac1{d_k}$ とすると
$$ \frac mn=\frac1{d_1}+\frac1{d_2}+\cdots+\frac1{d_k},\qquad d_{i+1}>d_i(d_i-1)\ge d_i\quad(i=1,\ldots,k-1) $$
であり、分母は真に増える。とくに、$0< r<1$ のすべての有理数 $r$ は、エジプト式分数で表せる。

分子の列が減り続けることを使う

方針：各回の残りを、約分しない分数 $\dfrac{m_i}{n_i}$ で追いかける。分子 $m_i$ が回ごとに真に減ることを示し、正の整数は限りなく減り続けられないことを使う。
段 1（残りの分数を約分せずに書く）。$m_0=m$、$n_0=n$ とする。$i$ 回目の残り $\dfrac{m_i}{n_i}$ が $0<\dfrac{m_i}{n_i}<1$ のとき、$d_{i+1}-1<\dfrac{n_i}{m_i}\le d_{i+1}$ を満たす整数 $d_{i+1}$ を選び（これが貪欲法の選び方である）、
$$ m_{i+1}=m_id_{i+1}-n_i,\qquad n_{i+1}=n_id_{i+1} $$
とおく。lem-egf-step より $\dfrac{m_i}{n_i}-\dfrac1{d_{i+1}}=\dfrac{m_{i+1}}{n_{i+1}}$ で、$0\le m_{i+1}< m_i$ である。$m_{i+1}>0$ なら、残りは $0<\dfrac{m_{i+1}}{n_{i+1}}<\dfrac1{d_{i+1}(d_{i+1}-1)}\le\dfrac12<1$ なので、次の回にも同じことができる。
段 2（高々 $m$ 回で止まる）。段 1 より、分子は $m=m_0>m_1>m_2>\cdots\ge0$ と、1 回ごとに $1$ 以上減る。$m_i\le m-i$ なので、$m$ 回までに分子は $0$ になり、そこで貪欲法は止まる（$0$ 以上の整数が限りなく減り続けることはない。数学的帰納法と整列性の系「無限降下の不可能性」）。分子が $0$ になった回を $k$ 回目とすると $k\le m$ で、
$$ \frac mn=\frac1{d_1}+\frac{m_1}{n_1}=\frac1{d_1}+\frac1{d_2}+\frac{m_2}{n_2}=\cdots=\frac1{d_1}+\cdots+\frac1{d_k}+\frac{m_k}{n_k} $$
と $m_k=0$ から、主張の等式が得られる。
段 3（分母は真に増える）。$i< k$ のとき $m_i>0$ なので、lem-egf-step の後半より、$i$ 回目の残り $r_i=\dfrac{m_i}{n_i}$ は $r_i<\dfrac1{d_i(d_i-1)}$ を満たす。次に選ぶ $d_{i+1}$ は $\dfrac1{d_{i+1}}\le r_i<\dfrac1{d_i(d_i-1)}$ を満たすので $d_{i+1}>d_i(d_i-1)$ である。$d_i\ge2$ より $d_i-1\ge1$ なので $d_i(d_i-1)\ge d_i$ となり、$d_{i+1}>d_i$ である。よって書き出した単位分数は互いに異なり、右辺はエジプト式分数である。

主定理の証明で大切なのは、分子を約分しないで追いかけても、1 回ごとに必ず $1$ 以上減ることである。約分すれば分子はもっと小さくなるので、止まるまでの回数はさらに少ないかもしれない。

分子の減り方を確かめる

$\dfrac37$：$d_1=3$（$\dfrac73=2.33\cdots$）、$\dfrac37-\dfrac13=\dfrac{9-7}{21}=\dfrac2{21}$。$d_2=11$（$\dfrac{21}2=10.5$）、$\dfrac2{21}-\dfrac1{11}=\dfrac{22-21}{231}=\dfrac1{231}$。$d_3=231$ で止まる。
$$ \frac37=\frac13+\frac1{11}+\frac1{231} $$
分子は $3\to2\to1\to0$ で、ちょうど $m=3$ 回かかった。$d_2=11>d_1(d_1-1)=6$、$d_3=231>11\cdot10=110$ である。
$\dfrac7{15}$：$d_1=3$、$\dfrac7{15}-\dfrac13=\dfrac{21-15}{45}=\dfrac6{45}$。約分しないと分子は $6$、約分すると $\dfrac2{15}$ である。$d_2=8$（$\dfrac{45}6=7.5$）、$\dfrac6{45}-\dfrac18=\dfrac{48-45}{360}=\dfrac3{360}=\dfrac1{120}$。$d_3=120$ で止まる。
$$ \frac7{15}=\frac13+\frac18+\frac1{120} $$
約分しない分子は $7\to6\to3\to0$ で、$m=7$ 回よりずっと早く止まった。

主定理 2：表し方は無数にある

ex-egf-def の (3) では、$\dfrac14$ を $\dfrac15+\dfrac1{20}$ に分けて、項数の違う表し方を作った。これはいつでもできる。

単位分数を 2 つに分ける

正の整数 $k$ について
$$ \frac1k=\frac1{k+1}+\frac1{k(k+1)} $$
である。

右辺を通分する

右辺を分母 $k(k+1)$ で通分すると
$$ \frac1{k+1}+\frac1{k(k+1)}=\frac{k}{k(k+1)}+\frac1{k(k+1)}=\frac{k+1}{k(k+1)}=\frac1k $$
である。

表し方は無数にある

エジプト式分数で表せる正の有理数 $r$ は、項数のすべて異なる無数の表し方をもつ。とくに、$0< r<1$ の有理数はどれも無数の表し方をもつ。

最も大きい分母を分け続ける

$r=\dfrac1{d_1}+\cdots+\dfrac1{d_k}$（$d_1<\cdots< d_k$）を 1 つの表し方とする。最も大きい分母 $d_k$ の項に lem-egf-split を使うと
$$ r=\frac1{d_1}+\cdots+\frac1{d_{k-1}}+\frac1{d_k+1}+\frac1{d_k(d_k+1)} $$
となる。新しい分母 $d_k+1$ は $d_k+1>d_k>d_{k-1}$ を満たす。$d_k\ge2$ なら、$d_k(d_k+1)-(d_k+1)=(d_k-1)(d_k+1)>0$ なので $d_k(d_k+1)>d_k+1$ でもある（$d_k=1$ の場合は最後に扱う）。したがって $d_k\ge2$ なら、分母は $d_1<\cdots< d_{k-1}< d_k+1< d_k(d_k+1)$ と真に増え、項数 $k+1$ の表し方が得られる。
この表し方の最も大きい分母 $d_k(d_k+1)$ は $2$ 以上なので、同じ操作を何度でも続けられ、項数 $k+1,k+2,k+3,\ldots$ の表し方が次々に得られる。項数が違うので、これらはすべて異なる表し方である。
最初の表し方で $d_k=1$ となるのは $r=1$ かつ $k=1$（表し方 $1=\dfrac11$）のときだけである。このときは、まず $1=\dfrac12+\dfrac13+\dfrac16$ に置きかえてから、上の操作を続ければよい。
後半は、thm-egf-greedy より $0< r<1$ の有理数がエジプト式分数で表せることから従う。

$\dfrac23$ の表し方を増やす

$\dfrac23=\dfrac12+\dfrac16$ の最も大きい分母 $6$ に lem-egf-split を使うと、$\dfrac16=\dfrac17+\dfrac1{42}$ より
$$ \frac23=\frac12+\frac17+\frac1{42} $$
である。さらに $\dfrac1{42}=\dfrac1{43}+\dfrac1{1806}$ を使うと
$$ \frac23=\frac12+\frac17+\frac1{43}+\frac1{1806} $$
で、項数 4 の表し方になる。確かめると $\dfrac12+\dfrac17+\dfrac1{43}+\dfrac1{1806}=\dfrac{903+258+42+1}{1806}=\dfrac{1204}{1806}=\dfrac23$ である。

貪欲法は最短とは限らない

thm-egf-greedy は、貪欲法が止まることを保証するが、項数が最も少ない表し方を与えるとは言っていない。実際、そうでない例がある。

貪欲法より短い表し方

$\dfrac9{20}$：貪欲法では $d_1=3$（$\dfrac{20}9=2.2\cdots$）、$\dfrac9{20}-\dfrac13=\dfrac{27-20}{60}=\dfrac7{60}$、$d_2=9$（$\dfrac{60}7=8.57\cdots$）、$\dfrac7{60}-\dfrac19=\dfrac{63-60}{540}=\dfrac1{180}$ で
$$ \frac9{20}=\frac13+\frac19+\frac1{180} $$
の項数 3 になる。しかし
$$ \frac14+\frac15=\frac{5+4}{20}=\frac9{20} $$
なので、項数 2 で書ける。
$\dfrac4{17}$：貪欲法では $\dfrac15+\dfrac1{29}+\dfrac1{1233}+\dfrac1{3039345}$ の項数 4 になるが、$\dfrac15+\dfrac1{30}+\dfrac1{510}=\dfrac{102+17+1}{510}=\dfrac{120}{510}=\dfrac4{17}$ の項数 3 でも書ける。
$\dfrac5{121}$：貪欲法では項数 5 になり、最後の分母は 25 桁の数になる。しかし $\dfrac1{33}+\dfrac1{121}+\dfrac1{363}=\dfrac{11+3+1}{363}=\dfrac{15}{363}=\dfrac5{121}$ の項数 3 でも書ける。
$\dfrac5{121}$ の貪欲法の 5 つの分母を開く
$25$、$757$、$763309$、$873960180913$、$1527612795642093418846225$ である（計算機で求めた）。どの段でも次の分母は $d_{i+1}>d_i(d_i-1)$ を満たし、ほぼ前の分母の 2 乗の大きさになる。

と (3) は、項数 2 では書けないことも確かめられる。たとえば $\dfrac4{17}=\dfrac1x+\dfrac1y$（$x< y$）なら $\dfrac1x<\dfrac4{17}<\dfrac2x$ から $5\le x\le8$ で、$x=5,6,7,8$ のどれでも $\dfrac4{17}-\dfrac1x$ は単位分数にならない（それぞれ $\dfrac3{85}$、$\dfrac7{102}$、$\dfrac{11}{119}$、$\dfrac{15}{136}$）。(3) も同じように $25\le x\le48$ の 24 通りを調べると、どれも単位分数にならない（計算機で確かめた）。
いくつかの分数について、貪欲法の結果を表にする。

分数	貪欲法の結果	項数	最後の分母の桁数
$\dfrac23$	$\dfrac12+\dfrac16$	$2$	$1$
$\dfrac45$	$\dfrac12+\dfrac14+\dfrac1{20}$	$3$	$2$
$\dfrac37$	$\dfrac13+\dfrac1{11}+\dfrac1{231}$	$3$	$3$
$\dfrac4{13}$	$\dfrac14+\dfrac1{18}+\dfrac1{468}$	$3$	$3$
$\dfrac7{15}$	$\dfrac13+\dfrac18+\dfrac1{120}$	$3$	$3$
$\dfrac9{20}$	$\dfrac13+\dfrac19+\dfrac1{180}$	$3$	$3$
$\dfrac4{17}$	$\dfrac15+\dfrac1{29}+\dfrac1{1233}+\dfrac1{3039345}$	$4$	$7$
$\dfrac5{121}$	$\dfrac1{25}+\dfrac1{757}+\dfrac1{763309}+\cdots$	$5$	$25$

図 2 は、$\dfrac5{121}$ と $\dfrac4{17}$ の貪欲法で出てくる分母の桁数を並べたものである。thm-egf-greedy の $d_{i+1}>d_i(d_i-1)$ から、分母は 1 段ごとに少なくともおよそ 2 乗の大きさになる。この 2 つの例では実際にほぼ 2 乗になり、桁数はおよそ 2 倍になっている。

5/121 と 4/17 に貪欲法を行ったときの、各段の分母の桁数。桁数は 1 段ごとにおよそ 2 倍になる

1 以上の有理数

貪欲法は $0< r<1$ の分数に使った。$1$ 以上の有理数も、異なる単位分数の和で書ける。ここでは $1+\dfrac12+\dfrac13+\cdots$ が限りなく大きくなることを使う。

1 以上の有理数の表し方

$r\ge1$ の有理数も、エジプト式分数で表せる。

調和級数の和で近づき、残りに貪欲法を使う

要点：$H_N=1+\dfrac12+\cdots+\dfrac1N$ はいくらでも大きくなる（調和級数）ので、$H_N\le r< H_{N+1}$ となる $N$ がとれる。残り $s=r-H_N$ は $0\le s<\dfrac1{N+1}$ なので、$s>0$ なら thm-egf-greedy の貪欲法で $s$ を表すと、分母はすべて $N+1$ より大きく、$1,2,\ldots,N$ と重ならない。

詳しい証明を開く

$H_N=1+\dfrac12+\cdots+\dfrac1N$ とおく。

段 1（$H_N$ は限りなく大きくなる）。$\dfrac13+\dfrac14\ge\dfrac14+\dfrac14=\dfrac12$、$\dfrac15+\cdots+\dfrac18\ge4\cdot\dfrac18=\dfrac12$ のように、$\dfrac1{2^{j}+1}+\cdots+\dfrac1{2^{j+1}}$ は $2^j$ 個の項がどれも $\dfrac1{2^{j+1}}$ 以上なので $\dfrac12$ 以上である。よって $H_{2^J}\ge1+\dfrac J2$ で、$J$ を大きくすれば $H_N$ はいくらでも大きくなる（調和級数）。

段 2（$N$ を選ぶ）。$H_1=1\le r$ で、段 1 より $H_N>r$ となる $N$ があるので、$H_N\le r$ を満たす最大の $N$ がある。このとき $H_N\le r< H_{N+1}=H_N+\dfrac1{N+1}$ なので、残り $s=r-H_N$ は $0\le s<\dfrac1{N+1}$ を満たす。

段 3（残りに貪欲法を使う）。$s=0$ なら $r=H_N$ がそのままエジプト式分数である。$s>0$ なら $0< s<1$ なので thm-egf-greedy より $s=\dfrac1{e_1}+\cdots+\dfrac1{e_j}$（$e_1<\cdots< e_j$）と書ける。貪欲法の最初の分母 $e_1$ は $\dfrac1{e_1}\le s<\dfrac1{N+1}$ を満たすので $e_1>N+1$ である。したがって$$r=1+\frac12+\cdots+\frac1N+\frac1{e_1}+\cdots+\frac1{e_j}$$の分母 $1,2,\ldots,N,e_1,\ldots,e_j$ はすべて異なる。

$2$ と $\dfrac52$

$r=2$：$H_3=1+\dfrac12+\dfrac13=\dfrac{11}6\le2< H_4=\dfrac{25}{12}$ なので $N=3$、残りは $2-\dfrac{11}6=\dfrac16$ である。よって $2=1+\dfrac12+\dfrac13+\dfrac16$ である。
$r=\dfrac52$：$H_6=\dfrac{49}{20}\le\dfrac52< H_7=\dfrac{363}{140}$ なので $N=6$、残りは $\dfrac52-\dfrac{49}{20}=\dfrac1{20}$ である。よって $\dfrac52=1+\dfrac12+\dfrac13+\dfrac14+\dfrac15+\dfrac16+\dfrac1{20}$ である。

例と反例

def-egf・def-egf-greedy と thm-egf-greedy の条件を 1 つずつ変えると、結論がどう崩れるかを表にする。

外す条件	反例	成り立たなくなること
単位分数が互いに異なる	$\dfrac23=\dfrac13+\dfrac13$	問いが意味をもつ（どの分数も自明に書ける。ex-egf-cx-repeat）
貪欲法で $\dfrac1d\le r$（等号を許す）	$\dfrac12$ で「$r$ より小さい最大の単位分数」を選ぶ	有限回で止まる（ex-egf-cx-strict）
$r$ が有理数	$r=\sqrt2-1$	有限回で止まる（ex-egf-cx-irrational）
$0< r<1$	$r=2$ にそのまま貪欲法を使う	単位分数が互いに異なる（ex-egf-cx-large）

反例：同じ単位分数を許すと自明になる

同じ単位分数を何度使ってもよいなら、$\dfrac mn=\underbrace{\dfrac1n+\dfrac1n+\cdots+\dfrac1n}_{m\text{ 個}}$ といつでも書ける。$\dfrac23=\dfrac13+\dfrac13$ もその例である。これでは「どう分けるか」という問題がなくなる。def-egf で互いに異なる単位分数に限るのは、そのためである。

反例：等号を許さないと止まらない

def-egf-greedy の条件 (i) で「$\dfrac1d\le r$」の代わりに「$\dfrac1d< r$ を満たす最小の $d$」を選ぶとする。$r=\dfrac12$ から始めると
(1) $\dfrac12$ より小さい最大の単位分数は $\dfrac13$ で、残りは $\dfrac12-\dfrac13=\dfrac16$。
(2) $\dfrac16$ より小さい最大の単位分数は $\dfrac17$ で、残りは $\dfrac16-\dfrac17=\dfrac1{42}$。
(3) $\dfrac1{42}$ より小さい最大の単位分数は $\dfrac1{43}$ で、残りは $\dfrac1{42}-\dfrac1{43}=\dfrac1{1806}$。
となり、残りはいつも単位分数 $\dfrac1k$ で、次に選ぶのはその $\dfrac1{k+1}$、残りは $\dfrac1{k(k+1)}$ になる。この変えた手順では、選んだ単位分数は残りより真に小さいので、残りは決して $0$ にならず、手順は止まらない。等号を許すことで、残りがちょうど単位分数になったときにそれを取って終われる。

反例：無理数では止まらない

$r=\sqrt2-1=0.41421\cdots$ に貪欲法の手順を行う（lem-egf-step の不等式の部分は、$r$ が無理数でも同じ証明で成り立つ）。$\dfrac13\le r<\dfrac12$ なので $d_1=3$、残りは $\sqrt2-\dfrac43=0.08088\cdots$ で、$\dfrac1{13}=0.07692\cdots\le0.08088\cdots<\dfrac1{12}=0.08333\cdots$ なので $d_2=13$ である。以下、分母は $3,13,253,218201,\ldots$ と続く（計算機で求めた）。
この手順は止まらない。もし止まれば、$\sqrt2-1$ が有限個の単位分数の和、つまり有理数になるが、$\sqrt2$ は無理数である（無理数の証明）。thm-egf-greedy の証明では、分子が正の整数であることを使って止まることを示した。無理数には「分子」がないので、この議論が使えない。

反例：$1$ 以上の数にそのまま使うと同じ分数が出る

$r=2$ に貪欲法をそのまま使うと、$\dfrac1d\le2$ を満たす最小の $d$ は $d=1$ で、残りは $2-1=1$ である。次もまた $d=1$ を選び、$2=\dfrac11+\dfrac11$ となって、単位分数が互いに異ならない。lem-egf-step で $d\ge2$ が言えたのは $r<1$ だったからで、prf-egf-greedy の段 3 の「分母は真に増える」がここで崩れる。$1$ 以上の数は、prop-egf-large のように調和級数の和で近づいてから貪欲法を使う。

演習

$\dfrac67$ の貪欲法

$\dfrac67$ に貪欲法を行い、エジプト式分数で表せ。約分しない分子がどう減るかも書け。

解答を開く

$\dfrac76=1.16\cdots$ なので $d_1=2$、$\dfrac67-\dfrac12=\dfrac{12-7}{14}=\dfrac5{14}$。$\dfrac{14}5=2.8$ なので $d_2=3$、$\dfrac5{14}-\dfrac13=\dfrac{15-14}{42}=\dfrac1{42}$。$d_3=42$ で止まる。よって $\dfrac67=\dfrac12+\dfrac13+\dfrac1{42}$ で、約分しない分子は $6\to5\to1\to0$ と減る。$d_2=3>d_1(d_1-1)=2$、$d_3=42>3\cdot2=6$ である。

項数の違う表し方

$\dfrac56=\dfrac12+\dfrac13$ をもとに、$\dfrac56$ の項数 3 と項数 4 の表し方を 1 つずつ作れ。

解答を開く

lem-egf-split を最も大きい分母 $3$ に使うと $\dfrac13=\dfrac14+\dfrac1{12}$ なので、$\dfrac56=\dfrac12+\dfrac14+\dfrac1{12}$（項数 3）。さらに $\dfrac1{12}=\dfrac1{13}+\dfrac1{156}$ を使うと $\dfrac56=\dfrac12+\dfrac14+\dfrac1{13}+\dfrac1{156}$（項数 4）。確かめると $\dfrac{78+39+12+1}{156}=\dfrac{130}{156}=\dfrac56$ である。

大学数学で見る：歴史と未解決の問題

MathWorld の頁に書かれていること

Wei26 は、エジプト式分数を「正の（通常は互いに異なる）単位分数の和」と定義し、次のことを述べている。

紀元前 1650 年ごろの Rhind パピルスに、$5$ から $101$ までの奇数 $n$ について $\dfrac2n$ をエジプト式分数で書いた表がある。
どの有理数も、項数がいくらでも多い表し方をもつ（thm-egf-infinite と同じ内容）。一方、項数を決めると表し方は有限個しかない（この記事では証明しない）。
Fibonacci は、どの分数も異なる単位分数の和で書けることを示し、1202 年に表し方を作る手順を発表した。この手順はのちに Sylvester によって再発見された。
項数が最も少ない表し方や、分母が最も小さい表し方を求める手順は知られていない（ex-egf-not-shortest のように、貪欲法は最短とは限らない）。
Erdős と Straus は、不定方程式 $\dfrac4n=\dfrac1a+\dfrac1b+\dfrac1c$ がいつでも解けると予想した（Erdős–Straus の予想）。
最後の予想は、頁では予想として述べられている。この記事では扱わない。

さらに先へ

分数を「足し算の形」に展開するもう 1 つの手順が連分数である。$\dfrac{157}{68}$ を互除法の商で $2+\cfrac1{3+\cfrac1{4+\cfrac15}}$ と入れ子にする見方は連分数（高校数学）で扱う。
prop-egf-large で使った「$1+\dfrac12+\dfrac13+\cdots$ が限りなく大きくなる」ことは調和級数で扱う。分母を小さい順にすべて足すと限りなく大きくなるので、項数を増やせばどんな大きさの有理数にも届く。
連続する整数の和では整数を連続する数の和で、Frobeniusの硬貨問題では 2 つの決まった数の和で、この記事では分数を異なる単位分数の和で表した。この記事で手順が止まる理由は「$0$ 以上の整数は限りなく減り続けられない」（数学的帰納法と整列性）で、同じ考え方は不定方程式の解法の無限降下法でも使う。