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

[lel0lel]

Интересно было бы взглянуть как изменяется среднее число продолжений (ветвлений) по всем рассмотренным простым по мере роста подпоследовательности простых чисел. Стартовать можно с пятизначных простых.

Dmitriy40 в сообщении #1523030 писал(а):

Их будет точно не выше чем $6+7(n-1)+4$, а в среднем даже ещё на 1 меньше

Похоже это не сильно повлияет на предельное значение среднего числа ветвлений. Так как число вставок изменяется примерно в $2/3$ раза, а плотность числа простых увеличивается примерно в $3/2$ раза.

Предельное среднее число ветвлений должно быть меньше 10, иначе нарушается закон распределения простых.

[Someone]

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

Дальше вероятность появления еще одного такого числа будет стремиться к нулю

Вы плохо читали мой анализ. Из него следует, что не будет. Наоборот, с вероятностью $1$ обрывается каждая конкретная цепочка простых чисел, построенная по такому правилу (то есть, начинаем с какого-нибудь простого числа, пытаемся вставить в него одну цифру, чтобы получить более длинное простое число, если удалось — так же пытаемся вставить ещё одну цифру, чтобы ещё "удлинить" наше простое число, и так далее). Вероятность того, что наудачу взятое большое простое число (больше $\sim 700$ цифр в десятичной записи) окажется таким "нерасширяемым", больше $\approx 1{,}9\cdot 10^{-5}$. Отсюда следует, что цепочки будут обрываться в среднем примерно за $53\,000$ шагов.

Dmitriy40 в сообщении #1523030 писал(а):

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

Ну, я за ограничениями не гнался. Тем более, что априорное отбрасывание части кандидатов пропорционально увеличивает плотность простых среди оставшихся, и получается "то же на то же".

Dmitriy40 в сообщении #1523030 писал(а):

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

Ну, я не о примерах, а об обрыве цепей. Пример, на который я наткнулся, оказался неожиданно (для меня) маленьким.

lel0lel в сообщении #1523036 писал(а):

Интересно было бы взглянуть как изменяется среднее число продолжений (ветвлений) по всем рассмотренным простым по мере роста подпоследовательности простых чисел.

lel0lel в сообщении #1522438 писал(а):

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

Но это относится к большим числам. Для "маленьких" простых чисел среднее число удачных вставок несколько больше, а плотность "нерасширяемых" несколько меньше, что демонстрирует и таблица, на которую сослался Dmitriy40, в которой из $242\,276\,981$ простых чисел "нерасширяемыми" являются $3\,000$, то есть, в среднем одно из $80\,759$.

[lel0lel]

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

Но это относится к большим числам

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

[mathpath]

Dmitriy40 в сообщении #1523030 писал(а):

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

И похоже, цепочка бесконечная
Я правильно понимаю, что у них запрещается вставлять ноль ?
Это довольно странно

[lel0lel]

Цитата:

369293 is a member because all of 1369293, 2369293, 3369293, ..., 3069293, 3169293, ..., 3692930, ..., 3692939 are composite.

не запрещено

[mathpath]

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

Dmitriy40 в сообщении #1523030 писал(а):

A125001

Там же приводится ссылка на диссер, в которой рассматривается проблема :

Существует ли какое-либо простое число, такое, что если какая-либо цифра будет изменена на любую другую цифру, то итоговое число всегда будет составным ?

Оказывается, такие числа есть, и похоже, их тоже сильно много:
294001,505447,584141,604171,971767,1062599,1282529,1524181,2017963,2474431,2690201,3085553....
Это т.н. слабые простые числа: https://oeis.org/A050249

[lel0lel]

Численные результаты в формате: число знаков в числах, количество простых в выборке, среднее число продолжений, корень из дисперсии для числа продолжений.
$\{20, 10000, 10.039, 2.956\}$
$\{40, 100000, 10.162, 3.103\}$
$\{100, 10000, 10.168, 3.154\}$
$\{200, 1000, 10.130, 3.131\}$
$\{400, 1000, 10.135, 3.08\}$

lel0lel в сообщении #1523036 писал(а):

Предельное среднее число ветвлений должно быть меньше 10, иначе нарушается закон распределения простых.

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

[kazvadim]

Очень интересно! Значит метод цифровых вставок имеет смысл. Гипотетически есть бесконечные цепочки простых, начинающиеся с некоторого натурального числа. Интересно, а существуют ли такие деревья, которые начинают свой рост с палиндрома? Дело в том, что палиндромы можно хранить в базе данных без $0.5$ или $0.5+1$ знаков в зависимости от чётности количества знаков.

[kotenok gav]

kazvadim в сообщении #1523519 писал(а):

палиндромы можно хранить в базе данных

Можно, но зачем?

[kazvadim]

kotenok gav в сообщении #1523520 писал(а):

Можно, но зачем?

Поиск закономерности в таких палиндромах, которые рождают деревья простых чисел. Если получится найти таковую закономерность, то от палиндрома будет проще начинать дерево с ветвями больших простых чисел. А если не удастся, то этот путь будет без результата.

[mathpath]

kazvadim в сообщении #1523519 писал(а):

Гипотетически есть бесконечные цепочки простых, начинающиеся с некоторого натурального числа.

Вот кстати автору этой темы вопрос:
я не следил за всеми ее перипитиями , на чем вы остановились ?
Я имею ввиду - до какой максимально длинной цепочки палиндромов вы добрались ?

[kotenok gav]

kazvadim в сообщении #1523530 писал(а):

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

Вы думаете, она будет?

[lel0lel]

Чтобы лучше разобраться с предельным "коэффициентом размножения" ветвей дерева рассмотрим дерево, в корне которого "посажено" число $2$. Вплоть до третьего поколения дерево имеет вид:

{2}, {23, 29}, {223, 229, 233, 239, 263, 269, 283, 293, 523, 823, 829, 929}, 
{1223, 1229, 1283, 1523, 1823, 2029, 2039, 2063, 2069, 2083, 2129, 2203, 2213, 2237, 2239, 2243, 2269, 2273, 2293, 2297, 
2309, 2333, 2339, 2383, 2389, 2393, 2399, 2423, 2539, 2593, 2609, 2633, 2659, 2663, 2683, 2689, 2693, 2699, 2729, 2803, 2833, 2837, 
2843, 2903, 2939, 2953, 2963, 2969, 3229, 3823, 3929, 4229, 4283, 4523, 5023, 5231, 5233, 5237, 5273, 5323, 5623, 5923, 6229, 6263, 
6269, 6823, 6829, 7229, 7283, 7523, 7823, 7829, 8123, 8209, 8219, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8291, 8293, 8297, 8329, 
8423, 8429, 8623, 8629, 8923, 8929, 9029, 9209, 9239, 9283, 9293, 9629, 9829, 9929}

Число ветвей в зависимости от поколения: $\{1, 2, 12, 100, 679, 4859, 35772, 272069, 2126768\}$, здесь первый элемент это сам корень, а последний -- число ветвей в восьмом поколении. Первые восемь "коэффициентов размножения": $\{2, 6, 8.33, 6.79, 7.15, 7.36, 7.61, 7.81\}$. Как видно не один из них не превосходит число $10$. Это всё посчитано для начала натурального ряда, но не думаю, что в более высоких поколениях "коэффициент размножения" будет больше $9$.

Можно заметить, что иногда вставки на разные позиции приводят к одним и тем же простым числам, из-за этого "коэффициент размножения" оказывается меньше, чем среднее число продолжений для случайно выбранного простого. Пример:
$\{23\}\to\{223, 233, 239, 263, 283, 293, 523, 823\}$ и $\{29\}\to\{229, 239, 269, 293, 829, 929\}$, при этом $\{23, 29\}\to\{223, 229, 233, 239, 263, 269, 283, 293, 523, 823, 829, 929\}$. Также вставки в начальные разряды нельзя считать достаточно случайными. Может есть и другие причины.

[Someone]

kazvadim в сообщении #1523530 писал(а):

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

Я не помню, чтобы Вы продемонстрировали какую-нибудь закономерность, касающуюся простых палиндромов. Ну, не считая того, что простой палиндром не может содержать чётное количество цифр. Я что-нибудь забыл?
Можете ли Вы утверждать, что плотность простых чисел среди всех палиндромов больше, чем среди всех натуральных чисел, содержащих такое же количество цифр? А если исключить числа, делящиеся на хотя бы одно из чисел $2$ и $5$?
Можете ли Вы утверждать, что простые палиндромы порождают больше ветвей в обсуждаемом алгоритме, чем произвольные простые числа? И что в процессе палиндромы будут постоянно воспроизводиться достаточно часто, чтобы существенно влиять на весь процесс?

-- Вс июн 20, 2021 19:15:41 --

lel0lel в сообщении #1523580 писал(а):

Также вставки в начальные разряды нельзя считать достаточно случайными.

Ну, ничего удивительного. Ясно, что если начальное простое число имеет несколько цифр, то, как правило, большинство полученных простых чисел будет иметь ту же первую цифру, что и исходное число. Или Вы имели в виду какую-нибудь другую особенность?

[lel0lel]

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

Или Вы имели в виду какую-нибудь другую особенность?

Да, я хотел сказать, что вставки в начальные разряды дают близкие по величине числа, поэтому нельзя сказать, что для них вероятности оказаться простыми будут независимыми. Возможно, что от таких вставок (в младшие разряды) будет получаться в среднем меньше простых, чем от вставок в старшие. Это имеет смысл только в случае больших чисел.