Кратные множители  

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

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

Продолжим анализ формулы Кэли, повторим ее:

    \[ 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.  \]

Начнем расчеты с минимального и единственного четного множителя в разложении – простого числа 2. Рассматривая свойства функционала Куммера, мы получили формулу для кратности двоек

    \[v_2(c_n) = n - v_2((n{+}1)!).\]

Если в разложении знаменателя наберется  n  двоек, то  c_n  – нечетное число.

Числа Каталана и числа Мерсенна

Четных чисел Каталана значительно больше, чем нечетных. Нечетные числа имеют индексы, совпадающие с числами Мерсенна: 1, 3, 7, 15, 31, и т.д. Это не случайное совпадение, поскольку для индексов  n {=} 2^k{-}1  функционал Куммера дает следующий результат:

    \[v_2((n{+}1)!) = v_2(2^k!) = 2^k{-}1.\]

Таким образом, налицо необходимое условие нечетности чисел Каталана, возможно, это условие и достаточное.

Теорема о нечетных числах Каталана. Числа Каталана с индексами Мерсенна нечетные, остальные числа Каталана четные.

Доказательство проведем, отталкиваясь от формулы Кэли. Пусть n  – k-ое число Мерсенна, или  n \!\!+\!\! 1 \!=\! 2^k  (– натуральное число). Каждый второй множитель в знаменателе четный, а всех чисел  2^k, поэтому от четных чисел можно «отщипнуть» в разложение знаменателя  2^k\!/2 \!=\! 2^{k-1}  двоек. Каждое четвертое число в знаменателе может добавить еще одну двойку в разложение, и таких чисел  2^k /4 {=} 2^{k-2}. Процесс «сбора» двоек можно продолжать и далее, на последних этапах мы отбираем последовательно четыре, две и одну двойку.

В результате, количество двоек в разложении  факториала  2^k!  равно

    \[ 2^{k-1} +  2^{k-2} +  2^{k-3} + \ldots + 4 + 2 + 1 =  2^k - 1 = n. \]

Можно вспомнить двоичную арифметику, когда двоичный код из k единиц дает в итоге десятичное число  2^k \!-\! 1.

Следующее число Каталана с индексом  2^k уже будет четным, в разложении появится двойка, поскольку в формуле факторизации степень двойки увеличится на 1, в то время как знаменатель дроби дополнится нечетным множителем  2^k \!\!+\!\!1. Четными будут и последующие числа Каталана с индексами  n \!< 2^{k +1} \!\!-\!\! 1. По мере увеличения индекса количество двоек в разложении растет скачкообразно. Максимум  k  двоек окажется для  n \!=\! 2^{k +1} \!\!-\!\! 2. И следующее число Каталана с индексом  2^{k +1} \!\!-\!\! 1  будет нечетным. Теорема доказана.

Отбор двоек

Рассмотрим итерационный алгоритм, который сводится к следующим двум операциям: а) последовательному делению пополам величины  n\!\!+\!\!1  с отбрасыванием дробей и б) вычитанию промежуточных значений из  n. Процесс продолжается, пока вычитаемое не обнулится.

Пример 2. Найдем кратность двойки в разложении числа Каталана с индексом 1000000 (один миллион). Длина этого числа составляет примерно 600000 (шестьсот тысяч) десятичных знаков. Факторизовать такое число мы пока не можем, но определить количество двоек в разложении миллионного числа Каталана очень легко.
Мы получим количество двоек, если вычесть из 1000000 те числа, которые получаются при последовательном делении пополам первоначальной величины 1000001 и последующих промежуточных значений (половинки отбрасываются). Распишем операции построчно:
1000000 – (1000001/2=500000) – (500000/2=250000) = 250000,
250000 – (250000/2=125000) – (125000/2=62500) = 62500,
62500 – (62500/2=31250) – (31250/2=15625) = 15625,
15625 – (15625/2=7812) – (7812/2=3906) = 3907,
3907 – (3906/2=1953) – (1953/2=976) – (976/2=488) = 490,
490  – (488/2=244) – (244/2=122) – (122/2=61) = 63,
63 – (61/2=30) – (30/2=15) – (15/2=7) – (7/2=3) – (3/2=1) = 7.
Таким образом, в разложении миллионного числа Каталана 7 двоек.

В примере в расчетных строках мы выделили нечетные промежуточные числа больше 1, которые возникают при дихотомическом делении, включая исходное нечетное число 1000001. Таких чисел оказалось ровно семь: 1000001, 15625, 1953, 61, 15, 7, 3. Кратность двойки в разложении числа Каталана с индексом 106 также равна 7, и очевидно, это не простое совпадение. Предлагаем читателю доказать этот феномен.

Таким образом, алгоритм вычисления кратности двойки в разложении числа Каталана с индексом  n  можно значительно упростить. Достаточно подсчитать количество нечетных промежуточных чисел больше 1, возникающих при дихотомическом делении величины  n{+}1. При этом учитывается и начальное значение (в случае четного  n).

Алгоритм вычисления кратности  v  множителя 2 в разложении  n-ого числа Каталана.
Шаг 1.  v := 0;  r := n+1.
Шаг 2.  v := v + ⌈r % 2⌉.    /* Операция % вычисляет остаток от деления двух чисел */
Шаг 3.  r := ⌊r/2⌋.
Шаг 4. Если  r > 1, перейти на шаг 2.
Шаг 5. Опубликовать  v.

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

Нечетные кратные множители

Кратность нечетных простых множителей определяется из формулы Кэли

    \[  v_p(c_n) =  v_p((2n{-}1)!!) - v_p((n{+}1)!), \;\;\; p > 2.\]

Начнем с простого множителя 3. Количество троек в разложении знаменателя дроби можно найти по аналогии с рассмотренным методом отбора двоек. Достаточно просуммировать числа, которые получаются при последовательном делении на 3 первоначальной величины  n{+}1  и всех последующих промежуточных значений (дробные части отбрасываются). Очевидно, и для остальных простых множителей процедура определения кратности в разложении знаменателя будет идентичной.

Сложнее обстоит дело с двойным факториалом. Рассмотрим на следующем примере процедуру отбора троек (и не только троек). Не исключено, что описываемая процедура не самая оптимальная.

Пример 3. Пусть  n =15, подсчитаем число троек в разложении двойного факториала 29!!. Преобразуем двойной факториал в обычный, т.е. вставим между нечетными множителями четные числа:
1⋅2⋅3⋅4⋅5⋅6⋅7⋅8⋅9⋅10⋅11⋅12⋅13⋅14⋅15⋅16⋅17⋅18⋅19⋅20⋅21⋅22⋅23⋅24⋅25⋅26⋅27⋅28⋅29
На первом шаге выявим числа, кратные трем, отметим их другим цветом и подсчитаем количество  ⌊29/3⌋=9.  Здесь мы отбросили дробную часть, т.е. избавились от последних двух чисел, не кратных 3. Но среди отмеченных цветом чисел есть и четные 6, 12, 18, 24. Как избавиться и от них? Очень просто, делим 9 пополам и округим результат до ближайшего целого сверху ⌈9/2⌉=5. В итоге, на первой итерации мы выяснили, что в исходном двойном факториале есть 5 нечетных множителей, кратных 3. Отметим важное обстоятельство, отобранные числа 3, 9, 15, 21, 27 как таковые не нужны, нас интересует лишь их количество.
Вторую итерацию выполним, не акцентируя внимания на анализируемых числах. На первом шаге предыдущей итерации было получено 9 чисел кратных 3. На первом шаге второй итерации  разделим 9 снова на 3 и получим 3 числа кратных 9. Но среди полученных трех чисел есть одно четное, которое на втором шаге удаляется делением на 2 с округлением сверху  ⌈3/2⌉=2. В результате вторая итерация дает две дополнительные тройки в разложении исходного двойного факториала.
На последней третьей итерации получим еще одну тройку. Таким образом, в разложении двойного факториала 29!! мы насчитали  5+2+1=8 троек. Если из 8 вычтем 6 троек из разложения факториала 16!, то получим две тройки в разложении 15-го числа Каталана.

В примере 3 опробован итерационный двухшаговый алгоритм подсчета кратности простого множителя   в разложении двойного факториала  (2n{-}1)!!  На каждой итерации расчеты ведутся с виртуальным рабочим факториалом  r!. Первоначально  r\!=\!2n{-}1, и в каждой итерации на первом шаге величина  r  уменьшается в  p  раз с отбрасыванием дробной части. На втором шаге  k-ой итерации вычисляется значение  ⌈r/2⌉, которое равно числу множителей  p  с кратностью  k, и уже эта величина добавляется в «копилку кратности».

Алгоритм вычисления кратности  v  простого множителя  p > 2  в разложении  n-ого числа Каталана.
Шаг 1.  v := 0;  r1 := 2n-1;  r2 := n+1.
Шаг 2.  r1 := ⌊r1/p⌋;  r2 := ⌊r2/p⌋.
Шаг 3.  v := v + ⌈r1/2⌉ – r2.
Шаг 4. Если  r1 ≥ p, перейти на шаг 2.
Шаг 5. Опубликовать  v.

В приведенном алгоритме на шаге 4 можно не проверять рабочую переменную  r2. В заключение этого раздела приведем пример с очень большим числом Каталана.

Пример 4. Найдем кратность простого множителя 1231 в разложении числа Каталана с индексом 109 (один миллиард). Разрядность такого числа составляет порядка 600 миллионов десятичных знаков. Множитель 1231 меньше порога кратности 44721 (квадратный корень из двух миллиардов), и его кратность может доходить до трех, но не более, поскольку  12314 > 2·109.
На первой итерации получаем следующие значения:
r1 = ⌊1999999999 / 1231⌋ = 1624695,
r2 = ⌊1000000001 / 1231⌋ = 812347,
v = 0 + ⌈1624695 / 2⌉ – 812347 = 1.
Вторая итерация повышает кратность на единицу:
r1 = ⌊1624695 / 1231⌋ = 1319,
r2 = ⌊812347 / 1231⌋ = 659,
v = 1 + ⌈1319 / 2⌉ – 659 = 2.
На последней третьей итерации получаем окончательное значение кратности множителя 1231:
r1 = ⌊1319 / 1231⌋ = 1,
r2 = ⌊659/1231⌋ = 0,
v = 2+ ⌈1 / 2⌉ – 0 = 3.

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

Разбиение верхней области факторной базы числа Каталана рассмотрим далее в разделе Сегментация.

 

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

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

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