Простые числа и палиндромы

[mathpath]

grizzly в сообщении #1522274 писал(а):

Даже если разрешить всякий раз вставлять цифру (или не более фиксированного числа цифр) на любые позиции, процесс получения новых простых очень быстро закончится :)

Позволю не согласиться с вами
По-моему, каждый раз при увеличении разрядности число вариантов вставки возрастает как минимум на два порядка
Ваш алгоритм не строгий, я не пробовал его реализовать, но мне кажется, он даст гораздо более длинные последовательности
Дело в том, что не имеет особого значения, на какую позицию вставлять
Например , если взять исходное простое число 75972593 и начинать вставлять в конец, между 9 и 3, то получается последовательность
7597259 + 32724230162366361339669 + 3, или :
759725933,
7597259323,
...

[grizzly]

mathpath в сообщении #1522317 писал(а):

По-моему, каждый раз при увеличении разрядности число вариантов вставки возрастает как минимум на два порядка

Любопытно оно выглядит по-Вашему. Но, боюсь, Вы ошиблись на пару порядков :)

mathpath в сообщении #1522317 писал(а):

Ваш алгоритм не строгий

В каком смысле?

mathpath в сообщении #1522317 писал(а):

мне кажется, он даст гораздо более длинные последовательности

Чуть более длинные, конечно. Я не спорю.

[Someone]

mathpath, разумеется, при увеличении количества вариантов вставки шанс на построение длинной последовательности простых чисел растёт. Например, если мы будем вставлять одну цифру ($1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ или $9$) впереди записи числа и одну цифру ($1$, $3$, $7$ или $9$) позади, то, начиная с простого числа $2$, можно добраться до $89$-значного числа
$28\,653\,986\,512\,599\,224\,126\,837\,727\,956\,373\,223\,223\,982\,112\,239\,771\,911\,791\,731\,191\,911\,919\,173\,971\,137\,913\\913\,799\,377,$
а если начать с последовательности $02$ (что выглядит, конечно, весьма искусственно), то сможем дойти до $94$-значного числа
$7\,736\,891\,492\,553\,529\,192\,988\,698\,484\,137\,788\,839\,531\,856\,154\,027\,199\,117\,313\,777\,997\,997\,739\,137\,139\,119\\713\,771\,397\,793\,773.$

[mathpath]

Алгоритм grizzly, если я правильно его понял, заключается в том, что мы проверяем ВСЕ разряды в исходном числе,
и если при вставке на один из этих разрядов одной из 10 цифр получается простое число, то итерация продолжается
Пример:
Имеется исходное простое число 7949
Имеется массив : ["2:3", "4:3", "5:6", "6:5", "7:1", "8:2", "9:6", "10:6", "11:7", "12:3", "13:9", "12:9", "13:2", "16:1", "16:8", "17:9", "19:4", "18:3", "14:2", "21:7", "15:2", "20:0", "23:1", "21:0", "21:5", "28:1", "27:9", "24:5", "31:3", "31:4", "31:2", "34:3", "31:6", "29:1", "28:3", "38:3", "28:5", "40:0", "40:6", "41:1", "39:2", "35:1", "45:8", "41:1", "44:5", "47:7", "43:8", "44:1", "47:0", "44:5", "45:0", "52:4", "53:3", "52:9", "50:5", "34:9", "53:3", "59:6", "53:4", "52:5", "57:7", "61:8", "61:4", "52:2", "59:3", "67:9", "62:0", "67:4", "68:2", "69:4", "71:0", "56:6", "74:0", "68:2", "68:3", "69:6", "75:6", "78:7", "73:9", "73:3", "83:0", "84:6", "67:2", "61:0", "86:9", "70:7", "84:3", "90:8", "73:9", "47:6", "92:9", "93:4", "93:6", "91:8", "97:0", "83:1", "97:5", "92:3", "86:4", "94:2"]
Первая итерация: берем первый элемент массива - "2:3", это значит , что на позицию 2 ставим 3, получаем 79349 - простое
Вторая итерация: 79349 -> 793439 - простое
И т.д.
Я привел только первые сто элементов этого массива, а он практически бесконечен ...

Где-то через минут пять после старта я добираюсь до 1000-значного простого числа

[grizzly]

mathpath в сообщении #1522375 писал(а):

Я привел только первые сто элементов этого массива, а он практически бесконечен

Да, всё верно, вероятность на Вашей стороне. Это я про что-то не то думал, сорри.

Теперь любопытно, доказуемо ли, что по таким правилам можно построить хоть одну бесконечную последовательность простых.

[mathpath]

grizzly в сообщении #1522382 писал(а):

Теперь любопытно, доказуемо ли, что по таким правилам можно построить хоть одну бесконечную последовательность простых.

Чисто интуитивно - да, конечно
Я смотрю, как в соответствии с моим алгоритмом ищется подходящий разряд для вставки
Алгоритм построен на том, что проверка идет от самых младших разрядов к старшим
И по статистике я вижу, что при росте разрядности искомый разряд лежит практически всегда в правой половине числа и никогда не добирается даже до середины числа

Жаль,я программист, а не математик

[Dmitriy40]

Скорее можно попытаться доказать что нет такого простого, которое нельзя расширить до большего простого.
Рассмотрим простое число из миллиона цифр. Для него существует (примерно) 10млн вариантов расширения. И чтобы все эти 10млн чисел были составными желательно чтобы средняя плотность простых в этом диапазоне была сильно менее одной десятимиллионной, а это явно не так, $1/\ln(10^{1000000}) \approx 1/2.3\cdot10^{6}>1/10^7$.

[Someone]

mathpath в сообщении #1522375 писал(а):

Алгоритм grizzly, если я правильно его понял, заключается в том, что мы проверяем ВСЕ разряды в исходном числе,
и если при вставке на один из этих разрядов одной из 10 цифр получается простое число, то итерация продолжается

Да, разумеется. Я разницу вижу. Я пока рассматривал случай, когда количество вариантов вставок ограничено некоторой величиной. Но можно рассмотреть и алгоритм grizzly.

Заранее предупреждаю, что последующее рассуждение не использует аккуратных оценок и основано только на асимптотике, поэтому рассматривать его как строгое доказательство не следует.

Как известно, плотность множества простых чисел в окрестности большого натурального числа $x$ имеет асимптотику $\frac 1{\ln x}$.
Если десятичная запись простого числа $x$ содержит $n$ цифр, то $10^{n-1}<x<10^n$, а число $x'$, полученное расширением числа $x$ одной цифрой (неважно, куда вставленной), удовлетворяет неравенству $10^n<x'<10^{n+1}$, поэтому $\frac 1{\ln x'}<\frac 1{n\ln 10}$.
Для вставки перед первой цифрой имеется $9$ вариантов (первая цифра не должна быть $0$), для вставки после последней цифры разумными являются только $4$ варианта ($1$, $3$, $7$, $9$), так как в остальных случаях получается составное число, которое делится на $2$ или на $5$. Так как таким образом отсекаются все числа, делящиеся на $2$ или на $5$, то плотность простых чисел среди оставшихся увеличивается в $\frac 21\cdot\frac 54=2{,}5$ раза и оценивается теперь величиной $\frac{2{,}5}{n\ln 10}$ ("асимптотически сверху").
По этой причине вероятность того, что конкретная вставка даст составное число, можно оценить ("асимптотически снизу") величиной $1-\frac{2{,}5}{n\ln 10}$.
Число возможных вставок в методе grizzly равно $9+10(n-1)+4=10n+3$, поэтому можно ожидать, что вероятность того, что все вставки дадут составное число, "асимптотически больше", чем

$$f(n)=\left(1-\frac{2{,}5}{n\ln 10}\right)^{10n+3}.$$

Можно проверить, что функция $f(n)$ возрастает при $n\geqslant 2$, и что

$$\lim_{n\to\infty}f(n)=\exp\left(-\frac{25}{\ln 10}\right)=1{,}9262\ldots\cdot 10^{-5}.$$

(24/VI-2021 исправил опечатку в этой формуле.)
В частности, при $n\geqslant 669$ будет $f(n)>1{,}9\cdot 10^{-5}$, а вероятность того, что хотя бы одна вставка из $10n+3$ возможных даст простое число, будет "асимптотически меньше" $1-1{,}9\cdot 10^{-5}$. Соответственно, вероятность того, что, начиная с не менее чем $n\geqslant 669$-значного простого числа, нам удастся продлить цепочку простых чисел не менее чем на $k$ шагов, будет "асимптотически меньше"

$$(1-1{,}9\cdot 10^{-5})^k\xrightarrow[k\to\infty]{}0.$$

Таким образом, каждая конкретная цепочка вставок обрывается с вероятностью $1$. Это, однако, не доказывает невозможность бесконечной цепочки вставок, дающих простые числа, а также не доказывает, что, начав с некоторого простого (или составного) числа, невозможно найти сколь угодно длинные цепочки вставок, дающих простые числа.

Я далеко не специалист в теории чисел, поэтому подробнее вдаваться в это дело не буду.

mathpath в сообщении #1522375 писал(а):

Где-то через минут пять после старта я добираюсь до 1000-значного простого числа

Судя по полученной оценке вероятности существования успешной вставки, Вам следует продлить свой эксперимент до чисел, содержащих хотя бы сотню тысяч цифр, а может быть и больше. Но тут уже, вероятно, придётся использовать не математические пакеты, а специализированные программы, умеющие эффективно выполнять тест с помощью теоремы Ферма. Например, OpenPFGW. И придётся написать для неё скрипт, автоматизирующий поиск вставок и сохраняющий некоторые промежуточные результаты, достаточные для возобновления расчётов в случае прерывания вычислений. Но даже и здесь вычисления могут потребовать чрезвычайно много времени.

[mathpath]

Someone в сообщении #1522418 писал(а):

mathpath в сообщении #1522375 писал(а):

Где-то через минут пять после старта я добираюсь до 1000-значного простого числа

Судя по полученной оценке вероятности существования успешной вставки, Вам следует продлить свой эксперимент до чисел, содержащих хотя бы сотню тысяч цифр, а может быть и больше. Но тут уже, вероятно, придётся использовать не математические пакеты, а специализированные программы, умеющие эффективно выполнять тест с помощью теоремы Ферма. Например, OpenPFGW. И придётся написать для неё скрипт, автоматизирующий поиск вставок и сохраняющий некоторые промежуточные результаты, достаточные для возобновления расчётов в случае прерывания вычислений. Но даже и здесь вычисления могут потребовать чрезвычайно много времени.

Да, суровый у вас анализ, и я не знаю, к чему можно придраться

Я бы гипотезу, сформулированную выше grizzly, сформулировал бы так:
Существует бесконечно много простых чисел, с помощью которых можно сформировать бесконечно длинные последовательности

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

Вместо этого имеет смысл поискать простые числа, с помощью которых нельзя сформировать бесконечно длинные последовательности,
и если они есть в начале числовой прямой, определить их число, может, их вообще нет

Если рассмотреть алгоритм формирования данной последовательности, то можно сказать, что он линейно не детерминирован
Что это значит ?
В начале алгоритма, когда мы начинаем вставлять число в какую-то позицию, может оказаться, что мы получим более одного варианта
И уже в самом начале на свет появляется дерево вариантов
Это дерево обладает бесконечной глубиной
Написать разумный алгоритм прохода по этому дереву не представляется возможным в силу ограниченности ресурсов
Мы просто случайным образом выбираем один из вариантов и двигаемся по нему вниз, игнорируя бесконечное количество других вариантов

[lel0lel]

Поскольку на каждом шаге в среднем имеется $25/\ln{10}$ "простых продолжений". То дерево разрастается экспоненциально и пусть даже на некотором шаге часть ветвей не будет иметь "простых продолжений", таких ветвей будет меньшая часть, так как вероятность гибели ветви, как показал Someone невелика. Таким образом, если дерево начало расти, то почти наверняка оно не погибнет.

[Someone]

mathpath в сообщении #1522425 писал(а):

Да, суровый у вас анализ, и я не знаю, к чему можно придраться

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

mathpath в сообщении #1522425 писал(а):

Я бы гипотезу, сформулированную выше grizzly, сформулировал бы так:
Существует бесконечно много простых чисел, с помощью которых можно сформировать бесконечно длинные последовательности

Я продолжу свой комментарий.

Как мы видели, вероятность того, что число $x'$, полученное из $x$ вставкой одной цифры, окажется простым, лежит примерно между $\frac{2{,}5}{(n+1)\ln 10}$ и $\frac{2{,}5}{n\ln 10}$. Вариантов вставок у нас $10n+3$, поэтому среднее число удачных вставок, дающих простые числа, "асимптотически равно"

$$\frac{2{,}5(10n+3)}{n\ln 10}\xrightarrow[n\to\infty]{}\frac{25}{\ln10}=10{,}857362\ldots,$$

то есть, дерево вставок должно сильно ветвиться. Из-за этого вероятность обрыва всех цепей с ростом высоты дерева очень быстро стремится к нулю (грубо говоря, как $\left(1{,}9\cdot 10^{-5}\right)^{10^k}$, где $k$ — номер уровня в дереве, считая исходное число нулевым уровнем). Поэтому вымирание всех ветвей должно быть большой редкостью, и мало шансов обнаружить такое дерево, содержащее больше одного-двух-трёх уровней, считая и нулевой уровень (это чисто эмоциональное суждение). Вот и lel0lel о том же пишет.

С другой стороны, как мы видели, каждая конкретная цепь обрывается с вероятностью $1$. Тем не менее, бесконечные цепи обязательно должны существовать: бесконечное дерево, у которого все уровни конечные, обязано иметь хотя бы одну бесконечную цепь. А у нас число элементов на $k$-м уровне можно оценить сверху величиной

$$\prod_{j=0}^{k-1}(10(n+j)+3).$$

Но бесконечные цепи в совокупности образуют множество нулевой вероятности. И я не представляю, как можно было бы указать конкретную бесконечную цепь.

mathpath в сообщении #1522425 писал(а):

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

Ну, есть стандартные библиотеки для работы с больши́ми числами: GMP, NTL и другие. GMP позиционируется как одна из наиболее быстрых из широко доступных библиотек, а NTL, как мне показалось, имеет более удобный интерфейс, но считает существенно медленнее. Однако её можно откомпилировать так, чтобы она для вычислений использовала GMP, и тогда вычисления сильно ускоряются (насколько я помню, я с этим однажды экспериментировал, и получил ускорение в несколько раз). NTL я компилировал просто в C++Builder, а для компиляции GMP пришлось установить MSYS/MinGW. При этом сначала долго тестировались возможности процессора, и только потом пошла собственно компиляция, которая заняла массу времени.
Что касается упомянутой прошлый раз программы OpenPFGW, то она предназначена для поиска очень больших простых чисел специальных видов, и для умножения длинных чисел в тестах использует какой-то особо эффективный вариант БПФ (быстрое преобразование Фурье).

Советую посмотреть список "5000 самых больших известных простых чисел" вот здесь: https://primes.utm.edu/. Самое большое моё простое число равно $4\,294\,967\,295\cdot 2^{1\,002\,700}-1$, оно уже слишком маленькое, чтобы находиться в этом списке. Найдено оно было на домашнем компьютере с помощью программы OpenPFGW.

[mathpath]

Сейчас все, так или иначе, пользуются методом Миллера-Рабина - он же метод Ферма - проверки числа на простоту, независимо от используемого математического пакета или языка программирования
Время работы метода Миллера-Рабина пропорционально логарифму в кубе от самого числа, т.е. полиномиально
Его можно использовать для проверки одного очень большого числа
Но его нельзя использовать для массовой работы с большими числами

[Someone]

Проделал некоторый численный эксперимент с алгоритмом grizzly (начальное число простое; на каждом шаге в простое число вставляется одна цифра в любую позицию так, чтобы получилось снова простое число). Именно, проверил первые $100\,000$ простых чисел ($p_{100\,000}=1\,299\,709$). Результаты следующие.

1) Нашлось ровно одно число, все вставки в которое дают составное число, то есть, на этом числе цепочка простых чисел обрывается: $p_{31\,478}=369293$. От однозначных простых чисел к этому числу ведут $6$ цепочек, начинающихся с однозначного простого числа.

$$\xymatrix{3\ar[r]&23\ar[r]&293\ar[r]&9\,293\ar[r]&39\,293\ar[rd]\\ 2\ar[ru]\ar[r]&29\ar[ru]\ar[r]&929\ar[ru]\ar[r]&3\,929\ar[ru]\ar[r]&36\,929\ar[r]&369\,293}$$

2) В рассмотренном диапазоне наибольшее число ветвей ($23$) получается для числа $p_{89\,638}=1\,154\,603$: $11\,534\,603$, $11\,543\,603$, $11\,545\,603$, $11\,546\,033$, $11\,546\,063$, $11\,546\,083$, $11\,546\,203$, $11\,546\,503$, $11\,546\,603$, $11\,546\,803$, $11\,546\,903$, $11\,564\,603$, $11\,584\,603$, $11\,594\,603$, $11\,654\,603$, $11\,854\,603$, $11\,954\,603$, $15\,154\,603$, $16\,154\,603$, $18\,154\,603$, $21\,154\,603$, $31\,154\,603$, $51\,154\,603$ (числа отсортированы по возрастанию). К этому числу ведут $3$ цепочки.

$$\xymatrix{3\ar[r]&13\ar[r]\ar[rd]&103\ar[r]&1103\ar[r]&11503\ar[r]&115603\ar[r]&1154603\\ &&113\ar[ru]\ar[r]&1153\ar[ru]}$$

[mathpath]

Someone в сообщении #1522954 писал(а):

1) Нашлось ровно одно число, все вставки в которое дают составное число, то есть, на этом числе цепочка простых чисел обрывается: $p_{31\,478}=369293$.

Как интересно !
Я почему-то был уверен, что хотя бы одно такое число найдется
Дальше вероятность появления еще одного такого числа будет стремиться к нулю

[Dmitriy40]

Всё уже добыто до нас: A125001. 3000 примеров ...

Кстати число вставок прилично завышено:

Someone в сообщении #1522418 писал(а):

Число возможных вставок в методе grizzly равно $9+10(n-1)+4=10n+3$,

Их будет точно не выше чем $6+7(n-1)+4$, а в среднем даже ещё на 1 меньше. Потому что в каждую позицию ровно три числа вставить не получится, те что дополняют число до кратного трём. А для младшей позиции вероятность для 1 и 7 по той же причине будет 0.5. Ну и наверное ещё ограничений можно наложить.