埃及分数：从阿赫梅斯纸草书到现代算法思维

背景

古埃及数学文献中，最古老且现存的文献之一便是《阿赫梅斯纸草书》（Ahmes papyrus）。这份写于约 3800 年前的文献，其核心部分包含了一个表格，列出了形式为 $\frac{2}{n}$（其中 $n$ 为奇数整数）的分数值。

在当时的埃及，人们并没有通用的分数表示法。他们只使用单位分数（即分子为 1 的分数，形式为 $\frac{1}{n}$），并且允许将这些单位分数相加来表示其他数值。然而，根据当时的惯例，同一个单位分数在表示中不能重复出现。例如，要表示 $\frac{3}{5}$，埃及人需要将其写成 $\frac{1}{2} + \frac{1}{10}$，为了简化书写，下文将这种表示法缩写为 $[2, 10]$。虽然埃及人也有表示 $\frac{2}{3}$ 的特殊符号，但在本文的讨论中暂且忽略这一特例。

将任意分数转换为这种“埃及分数”形式并非易事。尽管存在简单的算法，但往往并非最优解。作者 Mark Dominus 通过探讨这一古老数学问题，揭示了一个困扰他多年的谜题：为什么阿赫梅斯只提供了 $\frac{2}{n}$ 的表格，而没有提供所有可能商值的表格（例如 $\frac{3}{n}$ 或 $\frac{4}{n}$）？

核心内容

贪婪算法及其局限性

计算埃及分数表示的一种简单算法是“贪婪算法”（Greedy Algorithm）。其步骤如下：

1. 对于分数 $\frac{n}{d}$，找到小于它的最大单位分数 $\frac{1}{a}$。
2. 计算 $\frac{n}{d} - \frac{1}{a}$ 的埃及分数表示。
3. 将 $\frac{1}{a}$ 追加到结果中。

虽然该算法总是有效，但往往不是最优的，产生的分母可能非常大，计算不便。

案例 1：$\frac{2}{9}$

• 贪婪算法结果：小于 $\frac{2}{9}$ 的最大单位分数是 $\frac{1}{5}$。剩余部分为 $\frac{2}{9} - \frac{1}{5} = \frac{1}{45}$。因此，$\frac{2}{9} = \frac{1}{5} + \frac{1}{45} = [5, 45]$。
• 更优解：$\frac{2}{9} = [6, 18]$。显然，分母更小的表示法更便于计算。

案例 2：$\frac{19}{20}$

• 贪婪算法结果： $$ \frac{19}{20} = [2] + \frac{9}{20} = [2, 3] + \frac{7}{60} = [2, 3, 9, 180] $$
• 更优解：$\frac{7}{60}$ 可以表示为 $[10, 60]$、$[12, 30]$ 或最优的 $[15, 20]$。因此，$\frac{19}{20}$ 有更简洁的表达。

案例 3：$\frac{3}{7}$

• 贪婪算法结果：$\frac{3}{7} = \frac{1}{3} + \frac{2}{21}$。对 $\frac{2}{21}$ 使用贪婪算法得到 $[11, 231]$，故 $\frac{3}{7} = [3, 11, 231]$。
• 更优解：$\frac{2}{21}$ 有更好的展开式，如 $[15, 35]$，使得 $\frac{3}{7} = [3, 15, 35]$。而最优解实际上是 $\frac{3}{7} = [4, 7, 28]$。

为什么只需要 $\frac{2}{n}$ 的表格？

作者通过逻辑推导解释了阿赫梅斯纸草书为何只包含 $\frac{2}{n}$ 的表格，因为这是构建任意有理数埃及分数表示的基础。

假设我们需要表示 $\frac{3}{7}$：

1. 我们知道 $\frac{3}{7} = \frac{2}{7} + \frac{1}{7}$。
2. 查阅 $\frac{2}{n}$ 表格，找到 $\frac{2}{7} = [4, 28]$。
3. 因此，$\frac{3}{7} = [4, 7, 28]$。

假设我们需要表示 $\frac{4}{7}$：

1. $\frac{4}{7} = \frac{2}{7} + \frac{2}{7}$。
2. 查表得 $\frac{2}{7} = [4, 28]$。
3. 初步合并为 $[4, 4, 28, 28]$。由于存在重复项，需利用规则 $\frac{1}{2n} + \frac{1}{2n} = \frac{1}{n}$ 进行简化。
4. 简化后得到 $\frac{4}{7} = [2, 14]$。

同理，$\frac{5}{7} = [2, 7, 14]$。

对于 $\frac{6}{7}$：

1. 先计算 $\frac{3}{7} = [4, 7, 28]$。
2. 将其加倍：$\frac{6}{7} = \frac{1}{2} + \frac{2}{7} + \frac{1}{14}$。
3. 查表替换 $\frac{2}{7}$，得到 $\frac{6}{7} = [2, 4, 14, 28]$。虽然这可能不是最优解（例如 $[2, 3, 42]$ 项数更少，但分母更大），但这证明了通过 $\frac{2}{n}$ 表格可以推导出任意分数。

通用算法流程

一旦拥有 $\frac{2}{n}$ 的表格，就可以通过以下规则计算任意有理数 $\frac{a}{b}$ 的埃及分数表示：

1. 两个埃及分数相加：

   • 直接拼接两者的表示序列。
   • 如果存在重复的单位分数：
     • 若分母为偶数（即形式为 $\frac{1}{2n}$），利用 $\frac{1}{2n} + \frac{1}{2n} = \frac{1}{n}$ 消除重复项。
     • 若分母为奇数，则查 $\frac{2}{n}$ 表格，用查表结果替换重复项对。
   • 重复上述过程直到没有重复项。

2. 加倍一个埃及分数：

   • 将其与自身相加，遵循上述“相加”规则。

3. 计算 $\frac{a}{b}$（当 $a$ 为偶数 $2k$ 时）：

   • 先计算 $\frac{k}{b}$，然后将其加倍。

4. 计算 $\frac{a}{b}$（当 $a$ 为奇数时）：

   • 先计算 $\frac{a-1}{b}$（此时分子为偶数，按上述步骤3处理）。
   • 然后加上 $\frac{1}{b}$。

实例演示：$\frac{19}{20}$ 的推导

• $\frac{19}{20} = \frac{18}{20} + \frac{1}{20} = \frac{9}{10} + \frac{