Факторная база  

Еремин Геннадий
публикация 28 Sep 2015
редакция 10 Dec 2015


В разложении числа Каталана могут быть кратные и неповторяющиеся множители. Кратные множители размещаются в начале факторной базы, в то время как простые множители из рассмотренного ранее сегмента в принципе не могут повториться. Например, функционал Куммера для 100-го числа Каталана дает такие результаты  v_2(c_{100}) {=} 3  и  v_{13}(c_{100}) {=} 2, в то время как для всех простых чисел  p \in  {_\mathrm p}  (101, 200) \;\;  v_p(c_{100}) {=} 1.

Факторную базу можно разбить на две непересекающиеся части: а) нижняя область, в которой могут размещаться и размещаются кратные множители, и б) верхняя область, в которой теоретически невозможны кратные множители. Границей между областями или порогом кратности могла быть нижняя грань сегмента, если бы этот сегмент был единственным. Но в общем случае это не так.

Порог кратности можно обнаружить и в разложении произвольного натурального числа. Напомним, для факторизации целого числа k достаточно перебрать делители от 1 до \sqrt k. Именно в этом диапазоне простой делитель теоретически может повториться, но кратных делителей, превышающих  \sqrt k,  не существует.

Посмотрим сначала, что у нас с простыми натуральными числами, которые в факторной базе непосредственно примыкают к сегменту.

Запретная зона

Распишем в формуле Кэли оба факториала

    \[ c_n = 2^n \times \frac {1 \cdot 3 \cdot 5 \cdot 7 \cdots (2n-3) (2n-1)} {1 \cdot 2 \cdot 3 \cdot 4 \cdots n(n+1)} , \;\;\; n > 0. \]

В знаменателе последний множитель  n{+}1  может оказаться простым в случае четного  n. Но такой множитель есть и в числителе и тоже в единственном экземпляре, поэтому в разложении вероятностный простой множитель  n{+}1  невозможен, т.е. для простого числа n{+}1  получим  v_{n+1}(c_n) {=} 0. Простой нечетный множитель  n  также встречается в единственном экземпляре в обоих факториалах, следовательно, и  v_n(c_n) {=} 0.

Ситуация повторится, если мы и далее будем спускаться по натуральному ряду пока не доберемся до числа  \dfrac {2n}{3}. Если это число целое, то оно четно и потому непростое, составное и также не может оказаться в разложении.

В результате определилась запретная зона в верхней области факторной базы, ни один простой множитель этой зоны не может попасть в разложение числа Каталана. Дополнительно мы снизили порог кратности до величины  \dfrac {2n}{3}.

Проверим для профилактики следующее по нисходящей число  \dfrac {2n}{3} \!-\!\!1, которое будучи целым и, следовательно, нечетным, может оказаться еще и простым. Такое целое число в знаменателе формулы Кэли по-преж­нему в единственном экземпляре, но в числителе мы получим второй экземпляр из составного нечетного числа  2n{-}3, поскольку  \dfrac{2n-3}{3} = \dfrac{2n}{3} \!-\!\!1. В результате, простое натуральное число  \dfrac{2n}{3} \!-\!\!1 обязательно окажется в разложении, причем в единственном экземпляре, и этот множитель принадлежит уже другому сегменту факторной базы.

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

Теорема о зоне запрета.  В разложении n-го числа Каталана отсутствуют простые множители простого закрытого отрезка   {_\mathrm p} [2n/3, n{+}1].

В теореме нижняя граница простого отрезка для произвольного индекса  n  в общем случае будет дробным числом, но возможно и целое натуральное четное число, поэтому закрываются обе границы отрезка.

Порог кратности

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

Пример 1. Выберем какое-нибудь простое натуральное число, например, 101. Попробуем подобрать минимальное число Каталана, в разложении которого множитель 101 станет кратным. Если у нас получится, то это будет означать, что в факторной базе найденного числа Каталана порог кратности равен 101, либо где-то очень близко. Несомненно, такой эксперимент поможет нам в дальнейшем определиться с порогом кратности для произвольного числа Каталана.
В формуле Кэли числитель дроби содержит  n  нечетных чисел, в знаменателе имеем  n+1  четных и нечетных чисел. Распишем некоторые составные числа числителя и знаменателя, в которых встречается простой множитель 101:
числитель  1, 3, 5, … , 101, … , 101×3, … , 101×5, … , 101×101, …
знаменатель  1, 2, 3, … , 101, … , 101×2, … , 101×3, … , 101×101, …
Нетрудно видеть, при значениях индекса  n ≤ 50 в обоих факториалах нет множителя 101. И только при  n = 51 в числителе дроби и, соответственно, в разложении появится простой множитель 101.
В диапазоне  51 ≤ n < 100  множитель 101 будет в единственном числе в разложении.  Можно сказать, что обнаружена зона благоприятных индексов для множителя 101. Но при значении  n=100  в знаменателе появится симметричный множитель 101, в результате число 101 исчезнет из разложения. Такая ситуация не изменится во всем диапазоне значений индекса  100 ≤ n < 152, и это будет зона запретных индексов для множителя 101.
Увеличивая индекс  n, мы обнаружим еще одну благоприятную зону в диапазоне  152 ≤ n < 201 и еще одну запретную зону в диапазоне  201 ≤ n < 253. Дальнейшее чередование благоприятных и запретных зон уже становится не интересным, поскольку в каждой благоприятной зоне индексов множитель 101 включается в разложение в единственном экземпляре, а в каждой запретной зоне множитель 101 удаляется из разложения.
Но, когда после очередной зоны запрета мы доберемся в числителе до составного числа  2n–1 = 101×101, то сразу получим два множителя 101 в разложении числа Каталана с индексом  n = (101²+1)/2 = 5101.

В примере 1 мы получили минимально возможный индекс 5101, при котором множитель 101 стал кратным. Последнее равенство для индекса числа Каталана можно обобщить.

Утверждение 1. Пусть pпростое число (p>3),  k – натуральное число, тогда минимальный индекс числа Каталана, в разложении которого есть множитель  p^k  равен

    \[ n = \frac {p^k + 1} { 2}, \; \; \;  p>3. \]

Для  p \!=\! 3  формула дает неверный результат, и это связано с незначительными расстояниями по натуральному ряду между числами, которые кратны 3. Например, в случае  k{=}2 \;\;\; n\!=\!(3^2{+}1)/2 \!=\! 5, и тогда в числителе дроби формулы факторизации мы получим в разложении сразу две тройки. Но и в знаменателе последний множитель тоже кратен трем  n{+}1 \!=\! 6, поэтому в разложении 5-го числа Каталана множитель 3 не будет кратным.

В общем случае, если в числителе дроби последний множитель  2n{-}1 \!=\! 3^k, то в знаменателе последнее число кратно трем:

    \[ n +1 = \frac {3^k + 1} {2} + 1 = \frac {3^k + 3} {2} = 3 \times \frac {3^{k-1} + 1} {2}. \]

В итоге для всех  k  кратность множителя 3 в разложении снижается на единицу. Рассмотренный пример приводит нас к еще одной теореме.

Теорема о кратных множителях.  В разложении  n-го числа Каталана все простые множители кратности  k  меньше  \sqrt [k] {2n}.

Мы упростили в теореме подкоренное выражение (увеличив на 1), исключив при этом возможное равенство для кратных множителей. Очевидно, теорема обратна утверждению 1.

В дальнейшем нас будут интересовать, естественно, просто кратные множители разложения, т.е. с кратностью 2 и более. Итак, порогом кратности для числа Каталана с индексом  n  является значение  \sqrt {2n}. Исходя из этой величины, мы и будем относить множители разложения в ту или иную область факторной базы.

Факторизация и … рыбалка

Поясним, зачем мы так кропотливо и дотошно «возимся» с порогом кратности. Сравнительно небольшие числа Каталана факторизуются достаточно быстро, время расчета с использованием известных рекуррентных формул вполне приемлемо. На моем видавшем виды ноутбуке 5000-ое число Каталана обрабатывается практически мгновенно, число с индексом 10000 факторизуется за несколько секунд. Но на обработку 100000-го числа Каталана (60 тысяч десятичных знаков) потребовалось уже более двух минут машинного времени. Нужны быстрые алгоритмы для факторизации чисел с большими индексами, и на следующих страницах сайта мы займемся кратными и неповторяющимися множителями в разложении чисел Каталана.

В заключение отметим следующее. С каждым простым числом из нижней области факторной базы приходится работать отдельно, вычислять функционал Куммера. Другое дело сегменты верхней области, только из сегмента  {_\mathrm p} (n{+}1, 2n)  мы извлекаем более половины множителей разложения  n-го числа Каталана. И другие сегменты собирают группы множителей пусть и не такие многочисленные.

Позволим небольшую, надеюсь, уместную аллегорию. Срав­ним факторную базу числа Каталана с необъятным морем, у которого есть и небольшая  прибрежная зона – мелководье. Нижняя область – это прибрежное мелководье, верхняя область – безбрежные водные просторы. Факторизация чисел Каталана напоминает рыбную ловлю. С берега удочкой отлавливают по одной рыбке, а можно забросить сеть на глубине и сразу вытащить хороший улов. В нашем случае анализ и отбор каждого простого множителя из нижней области факторной базы – это ловля мальков удочкой с бережка на мелководье, в то время как сегмент эквивалентен забросу невода вдали от берегов, и здесь отлавливается вся «крупная рыба». Сегментами выбираются в случае больших индексов более 99% всех множителей. Но и без удочки не обойтись, чтобы подобрать остальную «мелочь».

В следующем разделе рассмотрим нижнюю область факторной базы числа Каталана, в которой размещены кратные множители.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>