Реферат: Египетские дроби

1.12. Докажите, что число 1 нельзя, а число 1/2 можно предста­вить в виде египетской суммы со знаменателями, являющимися точ­ными квадратами.

Способы разложения на египетские дроби

В этом разделе мы рассматриваем различные способы получить представление рационального числа в виде египетской суммы.

Определение 1. Жадный алгоритм. Выберем наибольшую дробь вида , которая не превосходит . Потом возьмем наи­большую дробь вида, n ₂ > n ₁ для которой . По­том возьмем наибольшую дробь вида , n ₃ > n ­₂ , для которой

и т.д.

Если на каждом шаге мы выбираем нечетные n i , то полученный метод будем называть нечетным жадным алгоритмом.

Определение 2. Разрешение конфликтов. Пусть < 1. Поло­жим

Когда несколько слагаемых в разложении совпадают, будем исправлять эту "неправильную" ситуацию. Каж­дый шаг алгоритма состоит в замене каких-то слагаемых другими. Будем рассматривать следующие разновидности этого метода.

• Метод парных замен .

• Метод подразбиения . Если какое-либо слагаемое встречается больше одного раза, выполним одну замену,

Определение 3 . Метод двоичного разложения. Пусть < 1. Разложим число в бесконечную двоичную дробь. Она будет сме­шанной периодической. Пусть период имеет длину n. Можно счи­тать, что начальная непериодическая часть имеет длину больше n. Каждой единице, предшествующей первому периоду, соответствует дробь вида . Каждой единице из периода соответствует египет­ская дробь .

Аналогичный метод работает и в системах с другими основания­ми, например, в шестиричной. Проблемы и решаются просто: , . В десятичной системе счисления этот метод не­посредственно на работает, поскольку не удается представить числа 4, 7, 8, 9 в виде суммы различных делителей числа 10. Назовем чис­ло N практичным, если все натуральные числа, не превосходящие N (в случае нечетного N — все кроме 2), можно представить в виде суммы нескольких (быть может, одного) различных делителей чис­ла N. Пример четного практичного числа — 6, пример нечетного практичного числа — 945. Благодаря разложению из задачи 1.8, мы можем с минимальными изменениями распространить метод двоич­ного разложения на случай, когда основание системы счисления — практичное число.

Определение 4 Метод двоичного остатка. Для разложения числа а / b, ( b¹ 2ⁿ ) в египетскую сумму выберем число p = 2 ^k > b. Разделим аp на b с остатком: ар = sb + г. Разложим r/p, s/p в