Легкие числа Каталана и их факторизация  

Известно, что в последовательности OEIS A000108 каждое n-ое число Каталана делится на простые числа из открытого интервала  (n+1, 2n), назовем такой интервал главный или первый сегмент Чебышева. Это легко увидеть по аналитической формуле числа Каталана

Cat (n) = (2n!) / (n! (n+1)!),  n ≥ 0.

В главном сегменте собрано большинство простых делителей, которые к тому же максимальны по величине. Если в разло­жении произвольного числа Каталана удалить делители такого сегмента, то мы получим очень короткое число. Например, число Каталана с индексом 10 000 содержит более 6000 десятичных знаков, и показать такое число проблематично. Тогда как соответствующее короткое число разместится в одной строке Вашего монитора. Среди коротких чисел появляются двойники, но вернуться к прародителю "тяжеловесу" легко, зная индекс.

Главный сегмент Чебышева не единственный в разложении числа Каталана, следующий второй сегмент для n-ого числа имеет вид  ((n+1)/2, 2n/3). Все простые числа из второго интервала также попадают в разложение и тоже в единственном экземпляре. Сегменты Чебышева описаны автором здесьздесь), покажем общий вид k-го сегмента:

( (n + 1) / k,  2n / (2k − 1) ),  k ≥ 1.

По мере роста k сегменты, во-первых, приближаются к началу числовой оси и, во-вторых, сокращаются размеры сегментов. Поэтому неизбежны пустые сегменты, т.е. бесполезные интервалы, не содержащие простых чисел. Естественно предпо­ложить, что должен существовать последний сегмент Чебышева, после которого теряется смысл подобных интервалов. И действи­тельно, на числовой оси вблизи двойки существует сегмент, после которого интервалы инвертируются, т.е. левая (обычно нижняя) граница становится больше правой (верхней).

Мы получим последний сегмент Чебышева, если приравняем границы в формуле общего вида. В результате получаем макси­мально возможный номер сегмента  kmax = |(n+1)/2|. Легко проверить, для нечетного n последний сегмент представляет собой пустой интервал  (2, 2). А в случае четного индекса двойка находится на стыке последнего сегмента Чебышева и после­дующего инвертированного интервала. Отсюда вытекает очевидный факт – единственное четное простое число 2 не выбирается сегментами Чебышева. Сформулируем еще одно утверждение (читатель может проверить самостоятельно или посмотреть здесь): наименьшее нечетное простое число 3 не отбирается такими сегментами Чебышева.

Нам первую очередь интересны некратные (неповторяющиеся) делители числа Каталана, поскольку таких делителей подав­ляющее большинство и они максимальны по величине. Нетрудно видеть, в интервале  ((2n)½, 2n)  находятся только неповто­ряющиеся простые делители n-го числа Каталана. Сравнительно несложно отобрать и удалить из разложения простые делители числа Каталана, превышающие квадратный корень из 2n. Оставшиеся делители составляют легкое число Каталана. Легкие числа Каталана позволяют заглянуть "вглубь" последовательности A000108.

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

(0)  1,  1,  2

Небольшое сравнение: последнее 69-ое легкое число в этом списке 29700 вполне доступно для анализа, а вот и оригинал (39 десятичных знаков):   Cat (69)  =  337 485 502 510 215 975 556 783 793 455 058 624 700.

В завершение выведем первые 200 легких чисел Каталана без множителей разложения.

(0)  1,  1,  2

 

www.000webhost.com