Легкие числа Каталана

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

Каждое число Каталана, как и любое другое натуральное число, однозначно разлагается на простые множители. Все простые множители разложения числа Каталана с индексом  n  выбираются из факторной базы – открытого простого интервала  {_\mathrm p} (1, 2n). Порог кратности  g_n {=} \sqrt {2n}  разделяет факторную базу на две области: нижнюю и верхнюю.

Кратные множители разложения  n-го числа Каталана выбираются только из нижней области факторной базы  {_\mathrm p} (1, g_n). Каждый такой множитель уникален и рассчитывается отдельно. Уникальность множителей нижней области заключается в том, что нельзя заранее определить по косвенным признакам, например, по индексу числа Каталана попадает ли такой множитель в разложение и какова его кратность.

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

Множители разложения, превышающие порог кратности, выбираются из верхней области факторной базы и их можно считать производными, не уникальными. Иначе говоря, для произвольного простого натурального числа из интервала  {_\mathrm p} (g_n, 2n)  легко определить принадлежность такого множителя разложению.

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

Пример 8. Для числа Каталана с индексом 108 порог кратности равен  g100000000= 14142, поэтому множители шлейфа выбираются из простого интервала  p(14142, 200000000). Возьмем два простых числа из верхней области  p = 463219, q = 543061 и определим для них функционал Куммера. Чтобы решить этот пример достаточно сопоставить заданные числа с границами ближайших сегментов.

Выберем подходящий сегмент для первого числа, воспользуемся формулой нижней границы:  (108+1)/463219 = 215.88. Следовательно, число   размещается между нижними границами сегментов 215 и 216. Сегмент 215 не рассматриваем, поскольку его нижняя граница  ⌊(108+1)/215⌋ = 465116  больше  p. Остается сравнить  p  с верхней границей сегмента 216, и эта граница равна  ⌈2×108/(2×216–1)⌉ = 464038. Нетрудно видеть, число 463219 попадает в сегмент 216 и, следовательно, есть в разложении .

Обратим внимание, формула нижней границы могла дать нам целое значение. Случай редкий, но вполне вероятный, например, для индекса 99592084 получим  (99592084+1)/463219 = 215. Это означает, что заданное простое число совпадает с нижней границей 215-го сегмента (и одновременно с верхней границей запретной зоны между сегментами 215 и 216). В этом случае число 463219 сразу отбраковывается, поскольку не попадает в разложение.

Аналогичные расчеты показывают, что второе число  q  размещается между верхней границей 185-го сегмента и нижней границей 184-го сегмента, т.е. в одной из запретных зон факторной базы. Следовательно, число 543061 не попадает в разложение числа Каталана с индексом 108.

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

    \[p < \left\lceil \frac {2n}{2k-1} \right\rceil,  \;\;\;  k\!=\! \left\lceil \frac {n+1}{p} \right\rceil \;\; (kp \ne n{+}1) .\]

Если  p  является делителем величины  n{+}1, то такое простое число заведомо не принадлежит разложению  n-го числа Каталана. Напомним, мы рассматриваем простые числа только из верхней области факторной базы. В противном случае, например, для  p\!=\! 2  нечетным было бы каждое число Каталана с нечетным индексом.

Разрядность чисел Каталана определяется множителями шлейфа. С учетом сказанного можно отметить следующее: число Каталана можно хранить в «облегченном» натуральном виде, если в разложении удалить шлейф. Натурализованное ядро назовем легкое число Каталана  и обозначим  c^{\circ}_n. Легкое число достаточно просто преобразовать в исходное «тяжелое» число Каталана, поскольку, зная индекс, несложно ядро дополнить шлейфом.

Ниже в таблице приведены начальные легкие числа последовательности Каталана.

таблица

Первые три числа с индексами 0-2 мы опустили, поскольку они не вписываются в нашу схему, и с каждым таким числом надо разбираться отдельно. В разложении числа Каталана с индексом 3 ядро пустое, и логично натурализованное ядро принять равным 1. Наверное, следует принять равными 1 и первые три легких числа Каталана.

Выпишем первые 100 легких чисел Каталана:
0-9:  1, 1, 1, 1, 2, 6, 12, 3, 2, 2;
10-19: 4, 2, 4, 100, 360, 45, 90, 30, 300, 30;
20-29: 60, 60, 120, 450, 36, 1764, 392, 28, 280, 56;
30-39: 112, 7, 294, 1470, 84, 14, 28, 28, 1400, 490;
40-49: 980, 3780, 7560, 18900, 2520, 2520, 35280, 4410, 900, 36;
50-59: 216, 108, 216, 840, 336, 12, 24, 24, 240, 72;
60-69: 1008, 121968, 11616, 45375, 18150, 1650, 3300, 11550, 1039500, 29700;
70-79: 59400, 4950, 108900, 544500, 2134440, 1067220, 27720, 83160, 831600, 20790;
80-89: 1540, 10780, 21560, 84700, 33880, 5725720, 34354320, 780780, 273273000, 18218200;
90-99: 400400, 200200, 400400, 2002000, 8808800, 34684650, 69369300, 1415700, 5577000, 111540.

Каждому числу Каталана соответствует определенное легкое число, но обратное неверно, поскольку среди легких чисел, как видим, много «двойников». Легкие числа значительно короче своих прародителей «тяжеловесов». И эта разница довольно ощутима на больших индексах, например, 170-ое легкое число Каталана равно 4080, в то время как в соответствующем прародителе 99 разрядов:

c170 = 566 348 408 726 522 751 148 449 775 858 720 556 691 622 190 005 859 389 137 334 807 741 187 245 136 563 759 042 704 144 561 379 440.

Конечно, и легкие числа на больших индексах выглядят внушительно. Легкое число Каталана с индексом 50000 имеет длину 163 знака:

 c^{\circ}_{50000} =  1 029 142 440 334 210 758 480 708 051 574 203 810 960 548 889 204 183 685 792 756 307 454 455 534 384 071 475 346 148 063 228 602 598 951 202 112 317 923 378 920 856 767 137 362 573 866 245 850 058 506 779 182 608 960.

Но тяжеловес с индексом 50000 показать проблематично, поскольку «весит» более 30000 десятичных разрядов. Иначе говоря, такой тяжеловес превышает легкое число более, чем в  10180  раз .

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

С ростом индекса доля ядра в разложении числа Каталана стремительно снижается. Например, для индекса 104 из 1563 множителей разложения в ядре содержится 51 множитель, что превышает 3%. В то время как для числа Каталана с индексом 107 доля ядра меньше 0.1% (из 867821 множителей в ядро попадает лишь 738). Дополнительно следует учитывать, что ядро состоит из младших множителей.

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

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

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

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