Сервис on-line  

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

На этой странице рассматривается  небольшой программный комплекс, который позволяет проверить результаты, связанные с факторизацией чисел Каталана. Факторизация – это разложение в произведение простых чисел. Для анализа и тестирования получаемых данных необходима таблица простых чисел, и в сети много таких таблиц. Но, во-первых, неплохо иметь простые числа, что называется, под рукой и, во-вторых, на этом сайте можно получить достаточно большие простые числа, которые часто недоступны.

Простые числа можно получить в интервале 104. Начало интервала (не более 1010) указывается при запуске программы. По умолчанию выдаются простые числа, начиная с 106.

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

Факторизация числа Каталана, вариант 1. Выводятся ядро и шлейф числа Каталана (главный сегмент выдается в укороченной форме), а также легкое число и обычное число Каталана в натуральном виде. В этом варианте можно указывать индексы не более 10000. По умолчанию обрабатывается 100-ое число Каталана. В программе встроен внешний цикл, который позволяет за одно обращение получить информацию для нескольких чисел Каталана.

Факторизация числа Каталана вариант 2. В этом варианте в отличие от рассмотренного выше опускается вывод натурального числа Каталана, поэтому допустимы индексы до 105. Легкие числа, по-прежнему, выдаются.

Рассчитать число Каталана и получить его в натуральном виде могут те, кого не удовлетворяет короткий список на сайте OEIS. В этой программе пользователь не получит множество факторов. Программа не рассчитывает числа с индексами более 20000, ввиду продолжительных расчетов. Например, число Каталана с индексом 15000 (длина 9025 десятичных знаков) мною было получено за 3 минуты.

Список легких чисел Каталана можно  получить в натуральном виде для индексов не более 10000. Длина списка варьируется от 20 до 100 в зависимости от величины индекса.

Ниже описаны программы, в которых разложение выполняется с помощью формулы факторизации. В программах не выдаются числа Каталана в натуральном виде (легкие числа могут выводиться). Поэтому здесь значительно расширен диапазон индексов – от 107 и выше.

Кратность двоек в разложении произвольного числа Каталана позволяет рассчитать небольшая программа. Величина индекса не ограничивается. Программа обрабатывает небольшую группу чисел Каталана, начиная с указанного индекса. По умолчанию начальный индекс равен числу Мерсенна 1048575 (индекс нечетного числа Каталана).

Факторизация большого числа Каталана выполняется без выдачи числа в натуральном виде (не выводится и легкое число). В этой программе можно за приемлемое время  получить разложение достаточно больших чисел с индексами 107 и более. Множество факторов числа Каталана с индексом 108 (сто миллионов) было получено на стареньком ноутбуке за минуту. Программа отдельно выводит множители ядра и множители шлейфа. Ядро выводится полностью, также полностью выдается и приграничная зона размером в десять порогов кратности. Остальные множители шлейфа группируются по сегментам.

Для каждого сегмента выше приграничной зоны указываются границы и выдается список простых чисел, попавших в сегмент. Если список невелик, выводятся все числа сегмента. В противном случае выдаются первые 10–12 множителей и последнее число сегмента. Программа подсчитывает общее количество множителей в разложении числа Каталана, за исключением случаев, когда протяженность сегментов на числовой прямой превышает 2⋅106. Сегменты-гиганты размещаются в верхней части шлейфа. Но и для таких сегментов также выводятся начальные элементы и последнее простое число. Сегменты-гиганты проявляются при разложении чисел Каталана с индексами более 2⋅106.

Факторизация большого легкого числа Каталана выполняется с выводом легкого числа в натуральном виде. Легкие числа намного порядков короче своих прародителей-тяжеловесов, поэтому расчеты таких чисел непродолжительны. Легкое число Каталана с индексом 108 (6927 десятичных знаков) и соответствующее ядро (1927 множителей) можно получить за несколько минут на среднем компьютере. Программа выводит и подсчитывает только множители ядра.

Ядро числа Каталана можно получить достаточно быстро практически для любого индекса. Например, для числа Каталана с индексом 1012 (один триллион) за считанные секунды вычисляется ядро, включающее 119496 множителей с учетом кратности. Ограничение связано лишь с разрядной сеткой компьютера.

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

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

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