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

[mathpath]

Бесконечные цепочки из простых палиндромов существуют ровно так же, как и просто бесконечные цепочки из простых
Генерируются они тем же нестрогим алгоритмом (гризли), описанным выше
Пример:
1. Берем простое число 5
2. Прибавляем семерки по краям и получаем 757
3. Прибавляем девятки по краям и получаем 97579
И далее, начинаем вставлять 2 одинаковых цифры зеркально, но не по краям, а внутрь
Получается такая картина: [ 2:3,2:5,2:3,2:4,2:5,2:4,3:2,6:4,6:2,7:7,9:8,10:4,10:3,9:4,3:1,5:8,6:0,6:1,6:8,7:0,11:1... ]
Здесь: 2:3 - вторая позиция, цифра 3
Т.е:
4. 9375739
5. 953757359
6. 93537573539
....
24. 94128801021542748343537573534384724512010882149
...
100. 98345142616709288014017233896030898691539951978808307669270864399321947846796893396703369323435337
65673353432396330769339869764874912399346807296670380887915993519689803069833271041088290761624154389

Я тут запустил генератор палиндромов.
Он дополз до 500 разрядов и остановился ...

[kazvadim]

Mikhail_K в сообщении #1523988 писал(а):

Внимательно прочитайте цитату, на которую Вы отвечаете. Там 11 назван "тривиальным палиндромом" и утверждается, что есть простые числа, не являющиеся нетривиальными палиндромами. Что любое натуральное число больше двух представимо в виде тривиального палиндрома, с этим никто не спорит.

А зачем тогда было нужно затевать разговор о тривиальности, если "с этим никто не спорит"? Тем более мне было трудно понять, что написано в цитируемом тексте. И нет там "11 назван "тривиальным палиндромом"", телепатией не владею. Мне нужно было всего лишь отделить простые числа, которые остались после применения алгоритма и могут быть подкреплены простым палиндромом $11$.

[kazvadim]

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

Я тут запустил генератор палиндромов.
Он дополз до 500 разрядов и остановился ...

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

[kazvadim]

mathpath
Спасибо Вам за поддержку и ценную помощь. Больше чем уверен, что своим методом цифровых приставок и вставок Вы сможете взять простых близнецов с помощью палиндромов. Моё программирование находится на ясельном уровне. Если есть время, то помогите пожалуйста.

[Someone]

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

Больше чем уверен, что своим методом цифровых приставок и вставок Вы сможете взять простых близнецов с помощью палиндромов.

А что, такие бывают? Примерчик не покажете? Пары $3$, $5$ и $5$, $7$ не предлагать. Ввиду их тривиальности. Как Вам уже писали, однозначные простые палиндромы и палиндром $11_m$, если он простой, являются тривиальными, то есть, не интересными.
Причём, предлагаемый метод "приставок и вставок" является в данном случае совершенно несостоятельным: требуется не слепой перебор в поисках неизвестно чего, а хотя бы несложное математическое рассуждение. Например, я могу для двоичной системы счисления указать (не тривиальную) пару простых близнецов-палиндромов: $101_2=5$ и $111_2=7$. Ещё какую-нибудь пару предложите?
Замечание. Для специалистов этот вопрос тривиален. Хотелось бы, чтобы kazvadim приложил некоторые усилия и попробовал разобраться в этом вопросе, не тратя тысячи часов компьютерного времени, а ограничившись несколькими минутами своего личного (ну пусть даже несколькими часами, учитывая его математическую неопытность). Это бы его кое в чём убедило и помогло избавиться от некоторых самовнушённых иллюзий.

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

Я тут запустил генератор палиндромов.
Он дополз до 500 разрядов и остановился ...

Почему остановился? Не нашёл продолжения? Его не существует, или Вы просто не дождались конца счёта? У меня Wolfram Mathematica такие числа обрабатывает достаточно быстро. Там же не надо сразу полный тест на простоту делать, для начала достаточно проверить равенство $\mathbf{Mod}[3^{p-1},p]=1$ или использовать усиленный вариант этого теста (Миллера–Рабина), а полное тестирование с помощью специализированных программ отложить на "потом".

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

Мы имеем возможность при переводе простых чисел чётно-значных из 10-ой п.с.с. в другую, например, в 2-ую, получая при этом простые палиндромы в 2-ой п.с.с. Тогда вероятность получения большого простого числа неминуемо возрастёт. Ошибаюсь?

Ошибаетесь. У меня такое впечатление, что Вы просто не понимаете, о чём Вам пишут.

Также я давно пытаюсь донести до Вас одну мысль, которую Вы никак не воспринимаете, и потому постоянно пишете невпопад. Попробую объяснить ещё раз.

Для математики важны арифметические свойства натуральных чисел: свойства арифметических операций и свойства чисел, выражающиеся с помощью арифметических операций. К таким относится, например, свойство быть чётным числом. Или свойство быть простым числом. Эти свойства не зависят от используемого способа записи чисел. Какие бы способы записи чисел ни придумали, число $17$ будет простым, а число $147$ — составным. Хоть в десятичной системе их запишите, хоть в семеричной, хоть римскими цифрами, хоть в славянской системе, хоть соответствующим количеством палочек изобразите.

Вы явно чересчур увлеклись палиндромами, и почему-то верите в то, что с помощью палиндромов можно решить какие-то важные математические проблемы. Между тем свойство числа быть палиндромом зависит не от арифметических свойств числа, а от выбранного способа записи чисел, поэтому это свойство, хотя и содержит некоторую информацию о числе, но является случайным по отношению к этому числу. Вы можете сформулировать какую-нибудь задачу, в формулировке которой отсутствовал бы термин "палиндром" (или что-то равнозначное ему), но для решения было бы необходимо использовать числа-палиндромы?
Вдобавок, количество "длинных" палиндромов очень мало по сравнению с количеством всех чисел такой же длины: в системе счисления с основанием $m$ количество $n$-значных чисел равно $(m-1)\cdot m^{n-1}\sim m^n$, а количество $n$-значных палиндромов — всего лишь $(m-1)\cdot m^{[\frac{n-1}2]}\sim m^{[\frac{n+1}2]}$ (квадратные скобки обозначают функцию "целая часть"). То есть, второе число, грубо говоря, имеет порядок квадратного корня из первого. По этой причине, ограничиваясь палиндромами, мы теряем практически все натуральные числа. Если меня интересуют числа с каким-то "арифметическим" свойством, то с какой стати я должен заранее считать их палиндромами? Пусть я ищу большие простые числа. Почему я должен проверять специально палиндромы? Простые палиндромы — очень малая часть всех простых чисел данной разрядности. Более того, простых палиндромов чётной разрядности вообще нет, за исключением единственного числа $11$. Что я там буду искать? Да, в моих подсчётах получилось, что среди палиндромов с нечётным числом цифр от $5$ до $17$ доля простых чисел чуть-чуть больше, чем среди всех чисел такой же разрядности. Но разница очень мала, и Dmitriy40 совершенно прав:

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

Я из таблицы вижу несколько другое, не что плотность простых палиндромов чуть-чуть выше плотности простых, а что они практически равны. И соответственно палиндромность не даёт заметного выигрыша при поиске/построении больших простых. В принципе похожую оценку я уже делал выше и результат был аналогичен (вероятности вдвое ниже, но всё равно почти одинаковы).

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

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

А зачем тогда было нужно затевать разговор о тривиальности, если "с этим никто не спорит"? Тем более мне было трудно понять, что написано в цитируемом тексте. И нет там "11 назван "тривиальным палиндромом"", телепатией не владею. Мне нужно было всего лишь отделить простые числа, которые остались после применения алгоритма и могут быть подкреплены простым палиндромом $11$.

Потому что никто, кроме Вас,не хочет тратить время на неинтересные (= тривиальные) банальности. Любое натуральное число $n>2$ может быть записано в виде палиндрома $n=11_m$ в системе счисления с основанием $m=n-1$. Это не даёт абсолютно никакой информации об арифметических свойствах числа $n$. В частности, искать простые числа среди таких "палиндромов" — то же самое, что искать их среди всех натуральных чисел. Не сложнее, но и не легче, поскольку это просто одно и то же, только сбоку прицеплен бантик "палиндром".

[mathpath]

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

Почему остановился? Не нашёл продолжения? Его не существует, или Вы просто не дождались конца счёта? У меня Wolfram Mathematica такие числа обрабатывает достаточно быстро.

Он как бы остановился, но пополз дальше, дополз до 1000 знаков, но на это очень скучно смотреть
У меня нет никаких сомнений в том, что это никогда не закончится
Причем в качестве стартового числа можно брать любой маленький палиндром

[kazvadim]

Someone
Абсолютно согласен со всем, что Вы написали. С характеристикой, которую Вы мне дали, совершенно согласен. Дело в том, что никоим образом не замахиваюсь на все простые числа, а только пытаюсь исследовать некоторые свойства простых палиндромов (как небольшого подкласса простых). Если где-то проскользнуло, что стремлюсь к чему-то большему, то приношу свои извинения (что-то написал не корректно). Постараюсь разобраться с арифметикой, чтобы правильней рассказывать о своих находках. Интересно, что простые палиндромы дают бесконечные цепочки - результат этой работы в теме совсем не мой...

[Someone]

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

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

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

$$\exp\left(-\frac{12{,}5}{\ln 10}\right)\approx 0{,}00438888,$$

что даёт ожидаемую длину цепочки в среднем $228$ шагов. Как я уже писал, мои рассуждения недостаточно обоснованные, поэтому реальная вероятность может заметно отличаться. Однако она точно не стремится к нулю, и это означает, что каждая конкретная цепочка обрывается с вероятностью $1$.
Тем не менее, это не означает, что бесконечных цепочек нет. Однако вряд ли мы сможем указать какую-нибудь конкретную бесконечную цепочку простых палиндромов. Бесконечные цепочки, скорее всего, есть, поскольку в среднем должно быть около $5$ удачных вставок в каждый достаточно длинный палиндром, поэтому количество получаемых числе на каждом уровне растёт со скоростью геометрической прогрессии (lel0lel: https://dxdy.ru/post1523580.html#p1523580, post1523622.html#p1523622).

Я провёл небольшой численный эксперимент, построив $4$ цепочки простых палиндромов, начинающихся с простых чисел $2$, $3$, $5$ и $7$. Длины этих цепочек, считая и начальное число, равны, соответственно, $191$, $44$, $56$ и $142$. Правило продолжения следующее: точки вставок проверяются слева направо до средней цифры числа (вторая точка вставки располагается симметрично относительно средней цифры), в первой точке вставки пытаемся вставить цифры $1$, $3$, $7$, $9$, в последующих точках — все цифры от $0$ до $9$ в порядке возрастания. При обнаружении простого числа другими вариантами не интересуемся, а начинаем вставлять цифры в полученное число. Перебор с возвратом не осуществляется.

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

Он как бы остановился, но пополз дальше, дополз до 1000 знаков, но на это очень скучно смотреть
У меня нет никаких сомнений в том, что это никогда не закончится

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

[mathpath]

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

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

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

Я обратил внимание на то, что многие цепочки палиндромов обрываются, и довольно часто
В случае с простыми не-палиндромами таких обрывов гораздо меньше

[lel0lel]

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

Бесконечные цепочки, скорее всего, есть, поскольку в среднем должно быть около $5$ удачных вставок в каждый достаточно длинный палиндром, поэтому количество получаемых числе на каждом уровне растёт со скоростью геометрической прогрессии

Да, для палиндромов деревья вполне жизнеспособны. Если в корне $1$ (не простое, но не суть), тогда начальные уровни дерева:

{1}, {313, 919}, {30103, 35153, 38183, 93139}, {3001003, 3091903, 3181813, 3541453, 3591953, 3601063, 3781873, 3871783, 3931393, 7381837, 9231329, 9351539, 9931399}

Число ветвей в поколениях:

{1, 2, 4, 13, 45, 169, 715, 3178, 14350, 65499, 304146}

Коэффициенты размножения:

{2, 2, 3.25, 3.46, 3.75, 4.23, 4.44, 4.51, 4.56, 4.64}

Если в корне $5$, тогда начальные уровни дерева:

{5}, {151, 353, 757}, {10501, 15551, 16561, 31513, 33533, 34543, 36563, 37573, 70507, 75557, 97579}, {1035301, 1055501, 1065601, 1085801, 1335331, 1535351, 1565651, 1685861, 1695961, 1755571, 1805081, 1865681, 3065603, 3075703, 3135313, 3155513, 3245423, 3305033, 3315133, 3365633, 3425243, 3485843, 3515153, 3635363, 3765673, 7035307, 7065607, 7155517, 7365637, 9375739, 9795979}

Число ветвей в поколениях:

{1, 3, 11, 31, 109, 413, 1810, 7849, 36093, 167350, 788639}

Коэффициенты размножения:

{3, 3.66, 2.81, 3.51, 3.78, 4.38, 4.33, 4.59, 4.63, 4.71}

[kazvadim]

Ещё немного о простых близнецах и палиндромах.
$(1) (p A \overline p, \overline p A p, q A \overline q, \overline q A q)$
$(2) p q B \overline q \overline p, \overline p q B \overline q p, p \overline q B q \overline p, \overline p \overline q B q p, q p B \overline p \overline q, \overline q p B \overline p q, q \overline p B p \overline q, \overline q \overline p B p q$
$(3) p D q C \overline q D \overline p, \overline p D q C \overline q D p, p D \overline q C q D \overline p, (\overline p D \overline q C q D p, q D p C \overline p D \overline q, \overline q D p C \overline p D q, q D \overline p C p D \overline q, \overline q D \overline p C p D q)$
Где $(p,q)$ простые близнецы, верхняя черта – обозначение перевёрнутого числа, $A, B, C, D$ – цифровые вставки (один знак). $5$-ть формул (в скобках) из $(3)$ исключаются, так как не дают никаких результатов. Формулы из $(1)$ – это система для $p$ и $q$, которые должны удовлетворять хотя бы одной своей формуле в системе. Числа, которые вычислялись по формулам $(1), (2), (3)$ – простые палиндромы. Применяя последовательно эти формулы от $ (1)$ до $(3)$ в указанном порядке, получилось, что все простые близнецы до $8$-го знака с начальной цифрой $1, 3, 7, 9$ принадлежат этой группе формул. ($9$-значных и т.д. близнецов я не потянул, по детски программирую).
О $8$-значных. Можно брать любые $8$-значные простые близнецы и строить из них простые палиндромы (и цепочками тоже) по этой группе формул. Если для $8$-значных простых близнецов применять последовательно формулы только из $(3)$, то можно получать $35$-значные простые палиндромы. Есть $17$ исключений (простые близнецы, которые не поддались формулам $(3)$).

(11210987,11210989), (13459877,13459879), (13482461,13482463), (14766821,14766823), (15602987,15602989), (16464419,16464421), (34810211,34810213), (39327269,39327271), (72045557,72045559), (72316289,72316291), (91030811,91030813), (91421327,91421329), (93358091,93358093), (94714049, 94714051), (96227867,96227869), (96549569,96549571), (98187671,98187673)

[kazvadim]

Всего $8$-значных простых близнецов $381332$, по $3$-м формулам из $(3)$ быстро вычисляются $381315$ $35$-значных простых палиндромов.

[Someone]

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

Где $(p,q)$ простые близнецы

А что изменится, если $p$ и $q$ — не близнецы и вовсе не простые? Простых палиндромов не получится?

Добавлено 2/VII-2021.

Прошу прощения у lel0lel, правильная цитата должна быть такой:

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

Где $(p,q)$ простые близнецы

[kazvadim]

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

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

Где $(p,q)$ простые близнецы

А что изменится, если $p$ и $q$ — не близнецы и вовсе не простые? Простых палиндромов не получится?

Ещё как получится (гора), разгребать то как? Например, в моей узкой задачке, в приведённые формулы плохо вкладываются простые близнецы с первыми цифрами $2,4,5,6,8$ $(29,31; 41,43; 59,61;$ и так далее). Половина формул для них не работает, так как при перевороте такая цифра оказывается в конце палиндрома. А вот простые близнецы на $1,3,7,9$ до $8$-го знака уложились в формулы. Что гарантирует очень быстро получить с помощью формул $(3)$ $381315$-ть $35$-значных простых палиндромов. Весь набор формул - 'это для получения простых палиндромов от $5$-ти до $8$-ми знаков.

[Dmitriy40]

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