| Разложение дроби в сумму аликвотных |
|
Не будем в этой статье, повторять всеми продублированные и растиражированные истины, откуда эти дроби появились и почему в Древнем Египте не могли додуматься до обычных дробей.
Аликвотная дробь, дробь которая имеет в числителе единицу. Например
\(\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}\)
