什麼是埃及分數?
埃及分數是把一個正有理數寫成若干個相異單位分數相加的形式——所謂單位分數,就是分子為 1 的分數,例如 \(\frac{1}{2}\)、\(\frac{1}{3}\) 或 \(\frac{1}{7}\)。古埃及人除了 \(\frac{2}{3}\) 有專屬符號外,所有分數都用這種方式來表示。本計算器能自動把你輸入的任何真分數轉換成這樣的總和。
如何使用本計算器
輸入一個真分數的分子與分母(分子需小於分母)。計算器會先把分數約分為最簡形式,接著套用貪婪演算法,並顯示完整的展開結果以及所使用的單位分數個數。
公式說明
這套貪婪法一般歸功於斐波那契(Fibonacci)與西爾維斯特(Sylvester),其做法是不斷取出「能取的最大單位分數」。對於餘數 \(\frac{a}{b}\),下一個分母為 \(d = \left\lceil \frac{b}{a} \right\rceil\)(向上取整)。減去 \(\frac{1}{d}\) 後得到新分數 \(\frac{a \cdot d - b}{b \cdot d}\),再將它約分並重複處理。由於每一步的分子都嚴格遞減,這個過程必定會結束。
$$\begin{gathered} \frac{\text{Numerator } a}{\text{Denominator } b} = \frac{1}{d_1} + \frac{1}{d_2} + \cdots + \frac{1}{d_k} \\[1.5em] \text{where}\quad \left\{ \begin{aligned} d_i &= \left\lceil \frac{b}{a} \right\rceil \\ \frac{a}{b} &\to \frac{a\,d_i - b}{b\,d_i} \quad (\text{reduced, then repeat}) \end{aligned} \right. \end{gathered}$$
實例演算
以 \(\frac{5}{6}\) 為例。此時 \(d = \left\lceil \frac{6}{5} \right\rceil = 2\),所以先取出 \(\frac{1}{2}\)。餘數為 \(\frac{5}{6} - \frac{1}{2} = \frac{2}{6} = \frac{1}{3}\),而它本身已是單位分數,因此展開結果為 \(\frac{1}{2} + \frac{1}{3}\),共用了 2 個單位分數。可驗算:$$\frac{1}{2} + \frac{1}{3} = \frac{3}{6} + \frac{2}{6} = \frac{5}{6}$$ ✓
更多實例
每一步都使用貪婪法則:對於目前的分數 \(\frac{a}{b}\),取 \(d=\lceil b/a\rceil\),減去 \(\frac{1}{d}\),將餘數化為最簡分數,然後重複此步驟,直到分子為 1。
實例 1:2/3
- \(\lceil 3/2\rceil = 2\),因此第一項為 \(\frac{1}{2}\)。
- 餘數:\(\frac{2}{3}-\frac{1}{2}=\frac{4-3}{6}=\frac{1}{6}\)。分子為 1,因此停止。
結果:\(\frac{2}{3}=\frac{1}{2}+\frac{1}{6}\)。
實例 2:4/13
- \(\lceil 13/4\rceil=\lceil 3.25\rceil=4\),因此第一項為 \(\frac{1}{4}\)。餘數:\(\frac{4}{13}-\frac{1}{4}=\frac{16-13}{52}=\frac{3}{52}\)。
- \(\lceil 52/3\rceil=\lceil 17.33\rceil=18\),因此第二項為 \(\frac{1}{18}\)。餘數:\(\frac{3}{52}-\frac{1}{18}=\frac{54-52}{936}=\frac{2}{936}=\frac{1}{468}\),約分後除以 2。
- 分子為 1,因此第三項為 \(\frac{1}{468}\)。
結果:\(\frac{4}{13}=\frac{1}{4}+\frac{1}{18}+\frac{1}{468}\)。
以公分母 468 檢查:\(\frac{117}{468}+\frac{26}{468}+\frac{1}{468}=\frac{144}{468}=\frac{4}{13}\),因為 \(468=13\times 36\),且 \(4\times 36=144\)。
實例 3:7/15
- \(\lceil 15/7\rceil=\lceil 2.14\rceil=3\),因此第一項為 \(\frac{1}{3}\)。餘數:\(\frac{7}{15}-\frac{1}{3}=\frac{7-5}{15}=\frac{2}{15}\)。
- \(\lceil 15/2\rceil=8\),因此第二項為 \(\frac{1}{8}\)。餘數:\(\frac{2}{15}-\frac{1}{8}=\frac{16-15}{120}=\frac{1}{120}\)。
- 分子為 1,因此第三項為 \(\frac{1}{120}\)。
結果:\(\frac{7}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}\)。注意 \(\frac{1}{3}+\frac{1}{5}=\frac{8}{15}\),不等於 \(\frac{7}{15}\),因此這裡兩項不夠。
以分母 120 檢查:\(\frac{40}{120}+\frac{15}{120}+\frac{1}{120}=\frac{56}{120}=\frac{7}{15}\)(除以 8)。
常見分數的貪婪展開式比較
| 分數 | 貪婪展開式 | 項數 | 最大分母 |
|---|---|---|---|
| 2/3 | 1/2 + 1/6 | 2 | 6 |
| 3/4 | 1/2 + 1/4 | 2 | 4 |
| 5/6 | 1/2 + 1/3 | 2 | 3 |
| 7/15 | 1/3 + 1/8 + 1/120 | 3 | 120 |
| 4/13 | 1/4 + 1/18 + 1/468 | 3 | 468 |
| 4/17 | 1/5 + 1/29 + 1/1233 + 1/3039345 | 4 | 3,039,345 |
| 5/121 | 1/25 + 1/757 + 1/763309 + 1/873960180913 + 最後一項約為 1.5×1024 | 5 | 約 1.5×1024(25 位數) |
貪婪法不一定是最佳的。此演算法一定會以不同的單位分數結束,但它可能產生非常大的分母,也不保證項數最少。兩個例子:
- \(\frac{4}{17}=\frac{1}{5}+\frac{1}{34}+\frac{1}{170}\),共三項,最大分母為 170;相比之下,貪婪法得到四項,最大分母為 3,039,345。檢查:\(\frac{34}{170}+\frac{5}{170}+\frac{1}{170}\) 無法直接套用;改用 \(\frac{1}{5}+\frac{6}{170}=\frac{34}{170}+\frac{6}{170}=\frac{40}{170}=\frac{4}{17}\)。
- \(\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}\),共三項,最大分母為 363。檢查:\(\frac{11}{363}+\frac{3}{363}+\frac{1}{363}=\frac{15}{363}=\frac{5}{121}\)。
埃及分數的表示法並不唯一,因此計算機的貪婪法輸出只是眾多有效答案之一,而非唯一答案。
關鍵術語
- 單位分數
- 分子為 1 的分數,例如 \(\frac{1}{7}\)。
- 真分數
- 分子小於分母的分數,因此其值介於 0 與 1 之間。埃及分數展開通常適用於此類分數。
- 最簡形式(以 GCD 約分)
- 當分子與分母除了 1 以外沒有其他公因數時,該分數為最簡形式。將兩者同除以它們的最大公因數(GCD)即可約分,例如 \(\frac{2}{936}=\frac{1}{468}\)。
- 向上取整函數
- \(\lceil x\rceil\) 是大於或等於 \(x\) 的最小整數。例如 \(\lceil 3.25\rceil=4\) 且 \(\lceil 5\rceil=5\)。
- 貪婪演算法(Fibonacci-Sylvester)
- 一種方法,反覆減去不超過目前分數的最大單位分數,即 \(\frac{1}{\lceil b/a\rceil}\),直到餘數本身是單位分數為止。此演算法一定會結束。
- 不同分母
- 在埃及分數中,任何單位分數都不重複,因此每個分母都不同。這就是為什麼 \(\frac{2}{5}\) 不寫成 \(\frac{1}{5}+\frac{1}{5}\)。
常見問題
埃及分數的展開方式是唯一的嗎? 不是。同一個分數可以有許多種拆成單位分數的寫法,貪婪演算法只是給出其中一種有效的表示法。
為什麼這些分數必須相異? 依定義,埃及分數使用的分母都不相同。正因如此,貪婪法才顯得有趣,而不只是把 \(\frac{1}{b}\) 重複加好幾次而已。
分母會不會變得非常大? 會。即使是看起來很簡單的分數,貪婪法也可能產生大得驚人的分母,這正是它廣為人知的缺點之一。