Последовательность пиллаи

Последовательность пиллаи - это последовательность целых чисел, содержащих рекордное количество терминов. в их жадных представлениях как суммы простых чисел (и единицы). Он назван в честь Суббайи Шивасанкаранараяна Пиллаи, который впервые дал определение ему в 1930 году.

Из гипотезы Гольдбаха следует, что каждое целое число больше единицы может быть представлено как сумма не более трех простых чисел. Однако поиск такого представления может потребовать решения экземпляров задачи суммы подмножества , что является сложным в вычислительном отношении. Вместо этого Пиллаи рассмотрел следующий более простой жадный алгоритм для нахождения представления $n\; \{\backslash \; displaystyle\; n\}$в виде суммы простых чисел: выберите первое простое число в сумме, которое будет наибольшее простое число $p\; \{\backslash \; displaystyle\; p\}$, которое не превышает $n\; \{\backslash \; displaystyle\; n\}$, а затем рекурсивно построить оставшуюся сумму для $п\; -\; п\; \{\backslash \; displaystyle\; np\}$. Если этот процесс достигает нуля, он останавливается. И если он достигает единицы вместо нуля, он должен включить единицу в сумму (даже если он не является простым), а затем остановиться. Например, этот алгоритм представляет 122 как 113 + 7 + 2, хотя также возможны более короткие представления 61 + 61 или 109 + 13.

$n\; \{\backslash \; displaystyle\; n\}$-е число в последовательности Пиллаи - это наименьшее число, для жадного представления которого в виде суммы простых чисел (и единицы) требуется $n\; \{\; \backslash \; displaystyle\; n\}$термины. Эти числа:

0, 1, 4, 27, 1354, 401429925999155061,... (последовательность A066352 в OEIS )

Каждое число $a\; (n)\; \{\backslash \; displaystyle\; a\; (n)\}$в последовательности представляет собой сумму предыдущего числа $a\; (n\; -\; 1)\; \{\backslash \; displaystyle\; a\; (n-1)\}$с простым число $p\; \{\backslash \; displaystyle\; p\}$, наименьшее простое число, у которого следующий промежуток между простыми числами больше, чем $a\; (n\; -\; 1)\; \{\backslash \; displaystyle\; a\; (n-1)\}$. Например, число 27 в последовательности равно 4 + 23, где первый пробел в простом числе больше 4 - это промежуток между 23 и 29.

Поскольку простые числа становятся менее плотными по мере того, как они становятся больше (что количественно определяется теоремой о простых числах ), всегда есть пробел между простыми числами, больший, чем любой член в последовательности Пиллаи, поэтому последовательность продолжается до бесконечного числа членов. Однако количество членов в последовательности растет очень быстро. Было подсчитано, что для выражения следующего члена в последовательности потребуются «сотни миллионов цифр».