Что такое египетская дробь?
Египетская дробь — это способ представить положительное рациональное число в виде суммы различных аликвотных дробей, то есть дробей с единицей в числителе: \(\frac{1}{2}\), \(\frac{1}{3}\), \(\frac{1}{7}\) и так далее. В Древнем Египте все дроби записывали именно так (за исключением особого знака для \(\frac{2}{3}\)). Этот калькулятор автоматически раскладывает любую введённую вами правильную дробь в подобную сумму.
Как пользоваться калькулятором
Введите числитель и знаменатель правильной дроби (числитель меньше знаменателя). Калькулятор сначала сократит дробь до несократимого вида, затем применит жадный алгоритм и покажет полное разложение, а также количество аликвотных дробей в нём.
Как работает формула
Жадный метод, который связывают с именами Фибоначчи и Сильвестра, на каждом шаге выделяет наибольшую возможную аликвотную дробь. Для остатка \(\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{1}{b}\).
Могут ли знаменатели получаться очень большими? Да. Жадный метод способен давать неожиданно большие знаменатели даже для простых дробей — это один из его известных недостатков.
Ещё примеры
Каждый шаг использует жадное правило: для текущей дроби \(\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 цифр) |
Жадный алгоритм не всегда даёт наилучший результат. Алгоритм всегда завершается разложением на различные дроби с числителем 1,但 он может давать очень большие знаменатели и не гарантирует наименьшего числа слагаемых. Два примера:
- \(\frac{4}{17}=\frac{1}{5}+\frac{1}{34}+\frac{1}{170}\) содержит три слагаемых и наибольший знаменатель 170, тогда как жадный алгоритм даёт четыре слагаемых и 3,039,345. Проверка: \(\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. Разложение египетскими дробями обычно применяют именно к таким дробям.
- Наименьшие члены (сокращение на НОД)
- Дробь записана в наименьших членах, когда числитель и знаменатель не имеют общего делителя, кроме 1. Чтобы привести дробь к такому виду, разделите оба числа на их наибольший общий делитель (НОД), например \(\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}\).