古埃及分數

维基百科，自由的百科全书

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

[编辑] 構造方法

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

[编辑] 貪婪演算法

參看貪婪演算法。

找出僅小於 $r = \frac{a}{b}$ 的最大單位分數。這個分數的分母的計法是：即用b除以a，捨去餘數，再加1。（如果沒有餘數，則r已是單位分數。）
把r減去單位分數，以這個新的、更小的r重覆步驟1。

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

$20 \div 19 = 1$ 和一個餘數，所以第1個單位分數是 $\frac{1}{2}$ ；
$\frac{19}{20} - \frac{1}{2} = \frac{9}{20}$ ；
$20 \div 9 = 2$ ，所以第2個單位分數是 $\frac{1}{3}$ ；
$\frac{9}{20} - \frac{1}{3} = \frac{7}{60}$ ；
$60 \div 7 = 8$ ，所以第3個單位分數是 $\frac{1}{9}$ ；
$\frac{7}{60} - \frac{1}{9} = \frac{1}{180}$ 已是單位分數。

所以結果是：

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

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

[编辑] Golomb算法

這個算法是基於貝祖等式的：當a,b互質， $a x - b y = 1$ 有無窮多對正整數解(x,y)。

選取最小的正整數解 $(m, n)$ 。取單位分數分母為 $b m$ ，重覆步驟。

以 $\frac{7}{10}$ 為例：

$7 \times 3- 10 \times 2 = 1$ ，所以第1個單位分數是 $\frac{1}{30}$ ；
$2 \times 2 - 3 \times 1 = 1$ ，所以第2個單位分數是 $\frac{1}{6}$ ；
第3個單位分數是 $\frac{1}{2}$ 。

[编辑] 二進制

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

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

這個方法的效率很低。

一個改善之道是選取正整數 $n$ 使得 $(2^n \times x) \bmod y < 2^{n+1}$ 。選取適當的正整數 $r, s$ （ $r < y$ ）使得 $2^n \times x=sy+r$ 。 $\frac{x}{y} = \frac{s}{2^n} + \frac{r}{2^n \times y}$ 。將 $\frac{s}{2^n} , \frac{r}{2^n}$ 寫成二進制數。

例如： $\frac{18}{23}$ ：

$(4 \times 18) \bmod 23 < 8$ ， $4 \times 18 = 23 \times 3 + 3$
$\frac{18}{23} = \frac{3}{4} + \frac{3}{4 \times 23}$
$\frac{3}{4} = 0.11 = 1/2+1/4$
$\frac{18}{23} = \frac{1}{2} + \frac{1}{4} + \frac{1}{2 \times 23} + \frac{1}{4 \times 23}$

[编辑] 分拆

將一個分數表示成未必相異的單位分數之和。若有兩個單位分數相同，可以用以下其中一種處理方式：

若它們的分母是雙數，便用它們的和取代；若它們的分母是單數，設它們的分母為 $2 k - 1$ ，用 $\frac{1}{k}+\frac{1}{(2k-1)k}$ 取代。
設它們的分母為 $p$ ，用 $\frac{1}{p}+\frac{1}{p+1}+\frac{1}{(p+1)p}$ 取代。

或是 $\frac{1}{n}=\frac{1}{n+1}+\frac{1}{n(n+1)}$ ←n可等於任意正整數

[编辑] Engel展開式

參看Engel展開式。方法類同於貪心法

[编辑] 歷史

數學史家有時論述代數的發展分為三個基本階段：

文字代數：其問題以古代數學家所用的文字表述；
省文代數：簡化問題中一些字詞，以幫助理解；
符號代數：以符號代表運算符和運算元，使更容易理解。

未知數以符號形式通常記為。我們從古代埃及文稿得知，埃及祭司和書記採用文字代數的方式，以一個解為「堆」或「集」的字「阿哈」來表示未知數。

這是現存在倫敦的大英博物館的萊因德數學紙草書（第二中間期）所載，其中一個阿哈問題的翻譯：

「問題24：一個數量和它的 $\frac{1}{7}$ 加起來是19。這數量是什麼？」

「假設是7。7和7的 $\frac{1}{7}$ 是8。8要乘上多少倍以得到19，7也要乘上這樣多倍以得到所要的數量。」

以現在的符號形式， $x + \frac{x}{7} = \frac{8x}{7} = 19$ ，故此 $= \frac{133}{8}$ 。檢查： $\frac{133}{8} + \frac{133}{7 \times 8} = \frac{133}{8} + \frac{19}{8} = \frac{152}{8} = 19$ 。