Египетские (аликвотные) дроби

 

  

Не будем в этой статье, повторять всеми продублированные  и растиражированные истины, откуда эти дроби появились и почему в Древнем Египте не могли додуматься до обычных дробей.

Аликвотная дробь, дробь  которая имеет в числителе единицу. Например

\(\cfrac{1}{44}\),\(\cfrac{1}{121981}\),\(\cfrac{1}{3}\) 

Так как их начали применять в Древнем Египте, то их и назвали египетскими.

Любую дробь, можно представить множеством вариантов сумм аликвотных дробей.

Например

Есть также много разных алгоритмов разложения произвольной дроби в сумму египетских.

Мы остановимся на алгоритме, который описал/открыл  Голомб

Но прежде чем начнем давайте определимся как например решать дробь вида \(\cfrac{2}{p}\)

Тривиальное решение как  \(\cfrac{1}{p}+\cfrac{1}{p}=\cfrac{2}{p}\) не рассматриваем.

Считаем, что каждое слагаемое в сумме должно быть уникальным.

В Древнем Египте, под эту дробь был исписан пергамент, то есть достаточно дорогой материал потратили на запись дробей  вида \(\cfrac{2}{p}\), что влечет подозрения, что это была важная веха в математике тех времен, и наверняка египтяне потратили немало времени, что бы  разложить подобные дроби.

С сожалению, они бы сэкономили, если бы знали что такую дробь, всегда можно разложить на сумму трех аликвотных дробей.

\(\cfrac{2}{p}=\cfrac{1}{p}+\cfrac{1}{(p+1)}+\cfrac{1}{p(p+1)}\)

И даже двух аликвотных дробей, если \( p \) нечетное число

\(\cfrac{2}{p}=\cfrac{(1+\cfrac{1}{p})}{\cfrac{p+1}{2}}\)

\(\cfrac{2}{17}=\cfrac{(1+\cfrac{1}{17})}{9}\)

 Не долго думая, можно легко догадаться что дробь  \(\cfrac{3}{p}\) можно получить как

\(\cfrac{3}{p}=\cfrac{1}{p}+\cfrac{2}{(p+1)}+\cfrac{2}{p(p+1)}\)

и в общем случае

\(\cfrac{n}{p}=\cfrac{1}{p}+\cfrac{n-1}{(p+1)}+\cfrac{n-1}{p(p+1)}\)

 Конечно, скажете Вы, какие же тут аликвотные дроби, если в числителе не единицы!

Совершенно верно, но данная формула показывает, когда заданную дробь, абсолютно точно можно разложить на три аликвотных дроби.

Если \(\cfrac{p+1}{n-1}\) делится нацело без остатка, то данная дробь раскладывается на сумму трех египетских дробей.

Поэтому, когда Вам на уроке зададут задачу разложить дробь \cfrac{17}{303} то, посчитав,  что \(\cfrac{303+1}{17-1}=19\), кричите и поднимайте руку, утверждая что  её можно разложить на три аликвотные дроби

 \(\cfrac{17}{303}=\cfrac{1}{303}+\cfrac{1}{19}+\cfrac{1}{19*303}\)

Оптимальное ли такое разложение? Нет конечно. Её можно представить в виде суммы двух дробей, но для этого надо нам надо погрузится в рассмотрение различных алгоритмов. И мы это сделаем позже.

Теперь что касается формулы

 \(\cfrac{2}{p}=\cfrac{(1+\cfrac{1}{p})}{\cfrac{p+1}{2}}\)

Её тоже можно обобщить и написать что

\(\cfrac{n}{p}=\cfrac{(1+\cfrac{1}{p})}{\cfrac{p+1}{n}}\)

Вывод: дробь раскладывается на сумму двух аликвотных дробей  если  \(\cfrac{p+1}{n}\) делится без остатка.

Является ли это обязательным условием? Нет конечно. Например вышеупомянутая дробь  \(\cfrac{17}{303}\) под это условие не попадает но тем не менее

 \(\cfrac{17}{303}=\cfrac{1}{18}+\cfrac{1}{1818}\)

 Теперь новый раздел, давайте анализировать

Считаем, что дробь всегда можно разложить на вид \(\cfrac{n}{p}=(b+\cfrac{c}{p})\cfrac{1}{a}\)

Какие же есть зависимости между переменными? Для этого нам надо использовать понятие Сравнения 1 степени. Теория чисел.

Бездоказательно, утверждаю что

\((b*p\:)mod \:n = -c\)

\((a*n\:)mod \:p = c\)

 Можно конечно расписать, как они получились, но не в этом материале.

Что же дают эти формулы?

Ну например то, что если число \(p\) составное,  и имеет делители \(d_1,d_2,d_3....d_n\)

То мы можем попытаться найти такое \(d_i\) что бы \(({p\:} mod {n})=(-1)*d_i\: mod{\:n}\)

И если такое число нашлось, то  у нас получается вот так

\(\cfrac{n}{p}=(1+\cfrac{d_i}{p})\cfrac{1}{a}\)

После сокращения  получаем сумму двух египетских дробей

Рассмотрим дробь \(\cfrac{13}{78125}\)

число 78125 имеет следующие делители 1, 5, 25, 125, 625, 3125, 15625, 78125

Остаток от деления 13 равен 8.

Среди делителей есть такое же число что дает остаток 5 (так как 13-8=5)?

Да есть  это число 3125 и это будет параметром \(c\)

Тогда узнаем оставшийся параметр \((a*13)mod 78125 = 3125\)

\(a=6250\)

и следовательно наше разложение вот такое

\(\cfrac{13}{78125}=(1+\cfrac{3125}{78125})\cfrac{1}{6250}=\cfrac{1}{6250}+\cfrac{1}{25*6250}\)

Закрепим материал. Новая дробь  \(\cfrac{41}{27368747340080916343}\)

Все алгоритмы, которые реализованы на сайтах сети Интернет, как минимум дают больше 3-х слагаемых. 

Попробуем обойтись всего двумя

Остаток от деления 27368747340080916343 на 41 равно 26.

Делители числа 27368747340080916343 есть числа  кратные 7-ми так \(7^23=27368747340080916343\)

Кто при делении на 41 имеет остаток 15-ть? (41-26)

Конечно же это число 343

Тогда узнаем оставшийся параметр \((a*41)mod 27368747340080916343 = 343\)

\(a=667530422928802846\) (Свои калькуляторы с такими большими числами не справились, пришлось прибегнуть к https://www.wolframalpha.com/)

и тогда наша дробь  опять превращается в сумму двух слагаемых

\(\cfrac{41}{27368747340080916343}=\cfrac{1}{667530422928802846}+\cfrac{1}{79792266297612001*667530422928802846}\)

с помощью вышеуказанного ресурса и проверим истинность.

 

Вообще, тема, где знаменатель есть число  в какой либо степени - очень интересна.

Чем больше степень знаменателя - тем выше вероятность того что эту дробь можно представить в виде двух аликвотных дробей.

Обязательно расскажу об этом во второй части.

А сейчас вернемся к алгоритму. Голомб в начале 20 века описал алгоритм который в рамках выше написанного в этой статье выглядит вот так:

На каждом этапе дробь делим на сумму двух  дробей  \(\cfrac{n}{p}=(b+\cfrac{c}{p})\cfrac{1}{a}\)

где \(b=1\)

Тогда наши формулы

\((b*p\:)mod \:n = -c\)

\((a*n\:)mod \:p = c\)

Превращаются в 

\((p\:)mod \:n = -c\)

\((a*n\:)mod \:p = c\)

Узнаем сначала \( c\) потом \( a \)

Получаем, одну аликвотную дробь и дробь вида \(\cfrac{c}{ap}\)

Повторяем все снова, пока не придем к дроби где числитель равен 1 и тогда дробь построена.

Система всегда сходится, но дробь не всегда короткая.

Но алгоритм иногда лучше чем классический алгоритм Фибоначчи.

Наш калькулятор, показывает каждый шаг разбиения, что позволит в ручном режиме найти следующий оптимальный шаг и пойти своим путем.

 

 

\(\cfrac{4}{2141}=\cfrac{1}{536}+\cfrac{1}{382526}+\cfrac{1}{1147576*191263}\)

\(\cfrac{4}{2777}=\cfrac{1}{695}+\cfrac{1}{643340}+\cfrac{1}{386003*643340}\)

 

 

Поиск по сайту