Последовательность Пиллаи - Pillai sequence

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

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

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

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

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

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

Рекомендации

1. Пиллаи, С. С. (1930), "Арифметическая функция относительно простых чисел", Журнал Аннамалайского университета: 159–167. Как цитирует Лука и Тангадураи (2009).
2. Лука, Флориан; Тангадурай, Равиндранатан (2009), «Об арифметической функции, рассмотренной Пиллаи», Журнал де Теори де Номбр де Бордо, 21 (3): 693–699, МИСТЕР  2605540
3. Слоан, Н. Дж. А. (ред.). «Последовательность A066352 (последовательность Пиллаи)». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.