エジプト分数の貪欲アルゴリズム

数学において、エジプト分数の貪欲アルゴリズムは、フィボナッチによって最初に説明された、有理数をエジプト分数に変換する貪欲アルゴリズムです。エジプト分数は、既約分数を異なる単位分数の合計として表現したもので、たとえば⁠5/6⁠ = ⁠1/2⁠ + ⁠1/3名前が示すように、これらの表現は古代エジプトから使われてきましたが、このような展開を構築するための最初の体系的な方法は、1202年にレオナルド・ディ・ピサの算盤（フィボナッチ）に記載されました。 ^[1]このアルゴリズムは、各ステップで残りの分数の任意の表現に使用できる 最大の単位分数を貪欲に選択するため、貪欲アルゴリズムと呼ばれます。

フィボナッチは、エジプト分数表現を構築するためのいくつかの異なる方法を実際にリストしています。^[2]彼は、いくつかのより簡単な方法が失敗した状況のための最後の手段として貪欲法を含めています。これらの方法のより詳細なリストについては、エジプト分数を参照してください。貪欲法、および無理数の近似値を求めるためのその拡張は、現代の数学者によって何度も再発見されており、 ^[3]最も早く、最も有名なのはJJ シルベスター (1880)によるものです。 ^[4]合計内のいくつかの単位分数が負になることを許容することで各ステップでより近い近似値を生成する密接に関連する展開方法は、ランバート (1770) にまで遡ります。

この方法によって生成される数の展開は、貪欲エジプト展開、シルベスター展開、またはフィボナッチ・シルベスター展開と呼ばれます。ただし、フィボナッチ展開という用語は通常、この方法ではなく、整数をフィボナッチ数列の和として表現することを指します。 ${\displaystyle x}$${\displaystyle x}$

フィボナッチのアルゴリズムは、繰り返し置換を実行することで、表現する 分数を拡大します （必要に応じて、この置換の2番目の項を簡略化します）。たとえば、 この展開では、最初の単位分数の分母3は、丸めの結果です。${\displaystyle x/y}$$${\displaystyle {\frac {x}{y}}={\frac {1}{\left\lceil {\frac {y}{x}}\right\rceil }}+{\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}}$$$${\displaystyle {\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.}$$15/7⁠最大で次の大きい整数まで、残りの分数は⁠2/15⁠ は、⁠ を単純化した結果です−15 7 の剰余/15 × 3⁠  =  ⁠6/45⁠。2番目の単位分数の分母8は、四捨五入の結果である⁠15/2⁠最大で次の大きい整数まで、残りの分数は⁠1/120⁠ は⁠から残ったものです7/15⁠両方を減算した後⁠1/3⁠と⁠1/8⁠ .

各展開ステップで残りの分数の分子が減るため、この方法は常に有限の展開で終了します。ただし、古代エジプトの展開やより現代的な方法と比較すると、この方法では分母が大きく、非常に長い展開が生成される場合があります。たとえば、この方法では、 他の方法でははるかに優れた展開が得られるのに対し、 Wagon (1991) はさらに悪い例を示しています。$${\displaystyle {\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763\,309}}+ {\frac {1}{873\,960\,180\,913}}+{\frac {1}{1\,527\,612\,795\,642\,093\,418\,846\,225}},}$$$${\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.}$$31/311⁠。貪欲法では10項の展開となり、最後の項の分母は500桁を超える。しかし、⁠31/311⁠ は非貪欲表現がはるかに短く、⁠1/12⁠ + ⁠1/63⁠ + ⁠1/2799⁠ + ⁠1/8708⁠ .

シルベスターの数列2、3、7、43、1807、...（OEIS：A000058）は、このタイプの無限貪欲展開によって数1に対して生成されると見なすことができます。各ステップで分母を選択します⌊ ⁠ええ/x⁠ ⌈の代わりに⌋ + 1 ⁠ええ/x⁠ ⌉。この数列をk項に切り捨てて対応するエジプト分数を形成すると、例えば ( k  = 4 の場合) は、任意のk項エジプト分数 による 1 の可能な限り最も近い過小評価になります。 ^[5]つまり、たとえば、開区間 ( ⁠$${\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}}$$1805/1806⁠、1) は少なくとも 5 つの項を必要とします。Curtiss (1922) は、これらの最近似値の結果を完全数の約数の数の下限に応用した例を説明しています。一方、Stong (1983) は、群論への応用について説明しています。

任意の分数⁠x/ええ⁠の貪欲展開では最大でx項しか必要としない。Mays (1987) と Freitag & Phillips (1999) は、貪欲法が⁠の展開を生成する条件を検証している。x/ええ⁠ちょうどx個の項を持ちます。これらはyの合同条件によって記述できます。

• すべての分数⁠1/ええ⁠ は貪欲展開で1つの項を必要とします。最も単純な分数は⁠です。1/1⁠ .
• すべての分数⁠2/ええ⁠ は貪欲展開においてy ≡ 1 (mod 2)のときのみ 2 つの項を必要とする。最も単純な分数は⁠2/3⁠ .
• 分数⁠3/ええ⁠ は貪欲展開において 3 つの項を必要とするのは、 y ≡ 1 (mod 6)のときのみであり、その場合− y mod x = 2であり、⁠y ( y + 2) の/3⁠は奇数なので、貪欲展開の1ステップ後に残る分数は、最も単純な言葉で言えば、次のようになります。最も単純な分数⁠$${\displaystyle {\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}}$$3/ええ⁠ 3期にわたる拡大は⁠3/7⁠ .
• 分数⁠4/ええ⁠ は、y ≡ 1 または 17 (mod 24)の場合にのみ貪欲展開で 4 つの項を必要とします。この場合、残りの分数の分子− y mod xは 3 で、分母は1 (mod 6)です。最も単純な分数⁠4/ええ⁠ 4期にわたる拡張は⁠4/17⁠。エルデシュ・ストラウス予想は、すべての分数が4/ええ⁠ は3項以下の展開を持ちますが、y ≡ 1 または 17 (mod 24)の場合、そのような展開は貪欲アルゴリズム以外の方法で見つける必要があり、17 (mod 24)の場合は合同関係2 (mod 3)によってカバーされます。

より一般的には分数の列⁠x/ええ⁠ x項貪欲展開を持ち、各xに対して可能な限り最小の分母y を持つものは

${\displaystyle 1,{\frac {2}{3}},{\frac {3}{7}},{\frac {4}{17}},{\frac {5}{31}},{\frac {6}{109}},{\frac {7}{253}},{\frac {8}{97}},{\frac {9}{271}},\dots }$（OEISの配列A048860）。

Stratemeyer (1930) と Salzer (1947) は、貪欲法に基づいて多項式の根の正確な近似値を求める方法を説明しています。彼らのアルゴリズムは根の貪欲展開を計算します。この展開の各ステップで、展開する残りの分数を根として持つ補助多項式が維持されます。例として、この方法を多項式方程式P ₀ ( x ) = x ² − x − 1 = 0の 2 つの解の 1 つである黄金比の貪欲展開に適用する場合を考えてみましょう。Stratemeyer と Salzer のアルゴリズムは、次の一連のステップを実行します。

1. P ₀ ( x ) < 0はx = 1のとき 、P ₀ ( x ) > 0はx ≥ 2 のときすべてであるので、 1 と 2 の間にはP ₀ ( x )の根が存在するはずである。つまり、黄金比の貪欲展開の最初の項は⁠1/1⁠。貪欲展開の最初のステップの後の残りの分数がx _{1である場合、方程式}P ₀ ( x ₁ + 1) = 0を満たし、これはP ₁ ( x ₁ ) = xとして展開できます。²
   ₁+ x ₁ − 1 = 0 です。
2. P ₁ ( x ) < 0なので、x  =  ⁠1/2⁠、そしてすべてのx > 1に対してP ₁ ( x ) > 0 であり、 P ₁の根は⁠の間にあります。1/2⁠と 1 であり、その貪欲展開の最初の項（黄金比の貪欲展開の 2 番目の項）は⁠1/2⁠ 。貪欲展開のこのステップの後の残りの分数がx ₂である場合、方程式P ₁ ( x ₂ + ⁠1/2⁠ ) = 0 であり、これはP ₂ ( x ₂ ) = 4 xと展開できる。²
   ₂+ 8 x ₂ − 1 = 0 です。
3. P ₂ ( x ) < 0なので、x  =  ⁠1/9⁠、そしてすべてのx > ⁠に対してP ₂ ( x ) > 0 である。1/8⁠、貪欲展開の次の項は⁠1/9⁠ 。貪欲展開のこのステップの後の残りの分数がx ₃である場合、方程式P ₂ ( x ₃ + ⁠1/9⁠ ) = 0 であり、これは再び整数係数の多項式として展開することができ、 P ₃ ( x ₃ ) = 324 x²
   ₃+ 720 x ₃ − 5 = 0 .

この近似プロセスを続けると、最終的に黄金比の貪欲な拡張が生まれます。

${\displaystyle \varphi ={\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots }$（OEISの配列A117116）。

分子と分母が小さいすべての分数の貪欲展開の長さ、最小分母、最大分母は、それぞれ、整数列のオンライン百科事典で、 OEIS : A050205、OEIS : A050206、OEIS : A050210として見つけることができます。さらに、無理数の貪欲展開は、無限に増加する整数列につながり、OEIS にはいくつかのよく知られた定数の展開が含まれています。OEIS のいくつかの追加のエントリは、貪欲アルゴリズムによって生成されたとはラベル付けされていませんが、同じタイプであるように見えます。

一般に、分母が何らかの方法で制約されるエジプト分数展開が必要な場合、各ステップで展開 を選択する貪欲アルゴリズムを定義することができます。ここで、 は、制約を満たすすべての可能な値の中から、 が可能な限り小さく、が以前に選択されたすべての分母とは異なるものになるように選択されます。このように定義される方法の例には、後続の各分母が前の分母の倍数でなければならないエンゲル展開や、すべての分母が奇数になるように制約される奇数貪欲展開などがあります。 $${\displaystyle {\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}},}$$${\displaystyle d}$${\displaystyle xd>y}$${\displaystyle d}$

ただし、このタイプのアルゴリズムが常に有限展開を見つけられるかどうかを判断するのは難しい場合があります。特に、が奇数であるすべての分数に対して、奇数の貪欲展開が有限展開で終了するかどうかは不明ですが、非貪欲な方法でこれらの分数の有限奇数展開を見つけることは可能です。 ${\displaystyle x/y}$${\displaystyle y}$