上一页

ⓘ 古埃及分數




                                     

ⓘ 古埃及分數

古埃及的分數 是不同的單位分數的和,就是分子為1,分母為各不相同的正整數。任何正有理數都能表達成這一個形式。

                                     

1. 構造

古埃及分數的表達形式不是唯一的,還未找到一個算法總是給出最短的形式。

                                     

1.1. 構造 貪婪演算法

贪婪算法:将一项分数分解成若干项单分子分数后的项数最少,称为第一种好算法;最大的分母数值最小,称为第二种好算法。 例如:

2 7 = 1 4 + 1 28 {\displaystyle {\frac {2}{7}}={\frac {1}{4}}+{\frac {1}{28}}} 。共2项,是第一种好算法,比 2 7 = 1 5 + 1 20 + 1 28 {\displaystyle {\frac {2}{7}}={\frac {1}{5}}+{\frac {1}{20}}+{\frac {1}{28}}} 的项数要少。

又例如, 5 121 = 1 33 + 1 121 + 1 363 {\displaystyle {\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}} 比 5 121 = 1 25 + 1 759 + 1 208725 {\displaystyle {\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{759}}+{\frac {1}{208725}}} 的最大分母要小,所以是第二种好算法。

  • 找出僅小於 r = a b {\displaystyle r={\frac {a}{b}}} 的最大單位分數。這個分數的分母的計算方法是:即用 b {\displaystyle b} 除以 a {\displaystyle a} ,捨去餘數,再加1。(如果沒有餘數,則 r {\displaystyle r} 已是單位分數。)
  • 把 r {\displaystyle r} 減去單位分數,以這個新的、更小的 r {\displaystyle r} 重複步驟1。

例子:把 19 20 {\displaystyle {\frac {19}{20}}} 轉成單位分數。

  • 19 20 − 1 2 = 9 20 {\displaystyle {\frac {19}{20}}-{\frac {1}{2}}={\frac {9}{20}}} ;
  • ⌊ 20 ÷ 9 ⌋ = 2 {\displaystyle \lfloor 20\div 9\rfloor =2} ,所以第2個單位分數是 1 3 {\displaystyle {\frac {1}{3}}} ;
  • 7 60 − 1 9 = 1 180 {\displaystyle {\frac {7}{60}}-{\frac {1}{9}}={\frac {1}{180}}} 已是單位分數。
  • 9 20 − 1 3 = 7 60 {\displaystyle {\frac {9}{20}}-{\frac {1}{3}}={\frac {7}{60}}} ;
  • ⌊ 20 ÷ 19 ⌋ = 1 {\displaystyle \lfloor 20\div 19\rfloor =1} ,所以第1個單位分數是 1 2 {\displaystyle {\frac {1}{2}}} ;
  • ⌊ 60 ÷ 7 ⌋ = 8 {\displaystyle \lfloor 60\div 7\rfloor =8} ,所以第3個單位分數是 1 9 {\displaystyle {\frac {1}{9}}} ;

所以結果是:

19 20 = 1 2 + 1 3 + 1 9 + 1 180 {\displaystyle {\frac {19}{20}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{9}}+{\frac {1}{180}}} 。

詹姆斯 約瑟夫 西爾維斯特和斐波那契都提出過以上的方法。

                                     

1.2. 構造 Golomb算法

這個算法是基於貝祖等式的:當 a {\displaystyle a}, b {\displaystyle b} 互質, a x − b y = 1 {\displaystyle ax-by=1} 有無窮多對正整數解 x, y {\displaystyle x,y} 。

選取最小的正整數解 m, n {\displaystyle m,n} 。取單位分數分母為 b m {\displaystyle bm} ,重複步驟。

以 7 10 {\displaystyle {\frac {7}{10}}} 為例:

  • 第3個單位分數是 1 2 {\displaystyle {\frac {1}{2}}} 。
  • 2 × 2 − 3 × 1 = 1 {\displaystyle 2\times 2-3\times 1=1} ,所以第2個單位分數是 1 6 {\displaystyle {\frac {1}{6}}} ;
  • 7 × 3 − 10 × 2 = 1 {\displaystyle 7\times 3-10\times 2=1} ,所以第1個單位分數是 1 30 {\displaystyle {\frac {1}{30}}} ;
                                     

1.3. 構造 二進制

最基本的方法就是將分數寫成二進制數,便能將該分數寫成分母為二的冪的單位分數之和。

換個說法就是重複求最小的正整數 n {\displaystyle n} 使得 x y > 1 2 n {\displaystyle {\frac {x}{y}}> {\frac {1}{2^{n}}}} 。

這個方法的效率很低。

一個改善之道是選取正整數 n {\displaystyle n} 使得 2 n × x mod y < 2 n + 1 {\displaystyle 2^{n}\times x{\bmod {y}}