什么是埃及分数?
埃及分数是指把一个正有理数表示为若干个互不相同的单位分数之和,所谓单位分数就是分子为 1 的分数,例如 \(\frac{1}{2}\)、\(\frac{1}{3}\) 或 \(\frac{1}{7}\)。古埃及人书写所有分数时都采用这种形式(仅 \(\frac{2}{3}\) 有一个专门的符号例外)。本计算器会自动把你输入的任意真分数转换成这样的求和形式。
如何使用本计算器
输入一个真分数的分子和分母(分子要小于分母)。计算器会先把分数约分为最简形式,再运用贪心算法,最后展示完整的分解结果,并告诉你其中包含多少个单位分数。
算法原理详解
这种贪心算法通常归功于斐波那契和西尔维斯特,其核心思路是不断减去尽可能大的单位分数。对于余下的分数 \(a/b\),下一个分母为 \(d = \lceil b/a \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 = \lceil 6/5 \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}. \checkmark$$
更多实例
每一步都使用贪心规则:对于当前分数 \(\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\)。
- 贪心算法(斐波那契-西尔维斯特算法)
- 一种方法:反复减去不超过当前分数的最大单位分数,即 \(\frac{1}{\lceil b/a\rceil}\),直到余数本身是一个单位分数。该算法总会结束。
- 不同分母
- 在埃及分数中,任何单位分数都不重复出现,因此每个分母都不相同。这就是为什么 \(\frac{2}{5}\) 不写成 \(\frac{1}{5}+\frac{1}{5}\)。
常见问题
埃及分数的分解结果是唯一的吗?不是。同一个分数可以有多种不同的单位分数表示方式;贪心算法只给出其中一种有效的分解。
为什么这些分数必须互不相同?按照定义,埃及分数要求各个分母都不相同,正是这一点让贪心算法变得有趣,而不是简单地把 \(\frac{1}{b}\) 重复相加。
分母会不会变得非常大?会的。即便是看起来很简单的分数,贪心算法也可能产生出奇大的分母,这正是它众所周知的一个缺点。