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

[Dmitriy40]

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

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

начальное: 9313191731353531371913139
конечное: 3379333999313191731353531371913139993339733
Все остальные восстанавливаются тривиально.

Тогда у меня не получилась 10-ка. Чья программа шалит, моя или Ваша? Покажите всю десятку - на factor проверим...

9313191731353531371913139
993131917313535313719131399
99931319173135353137191313999
3999313191731353531371913139993
339993131917313535313719131399933
33399931319173135353137191313999333
9333999313191731353531371913139993339
793339993131917313535313719131399933397
37933399931319173135353137191313999333973
3379333999313191731353531371913139993339733

? isprime(3379333999313191731353531371913139993339733)
%1 = 1
? isprime(37933399931319173135353137191313999333973)
%2 = 1
? isprime(793339993131917313535313719131399933397)
%3 = 1
? isprime(9333999313191731353531371913139993339)
%4 = 1
? isprime(33399931319173135353137191313999333)
%5 = 1
? isprime(339993131917313535313719131399933)
%6 = 1
? isprime(3999313191731353531371913139993)
%7 = 1
? isprime(99931319173135353137191313999)
%8 = 1
? isprime(993131917313535313719131399)
%9 = 1
? isprime(9313191731353531371913139)
%10 = 1
? isprime(31319173135353137191313)
%11 = 0

-- 29.12.2020, 22:51 --

Вторая и третья десятки:
10:999939739_159957139311515113931759951_937939999
10:333333199_777599739393959393937995777_991333333

[kazvadim]

Dmitriy40, Ваша взяла... у меня прога туфтовая... зато есть новые идеи... поработаем?

[Dmitriy40]

На удивление найдена и последовательность из 11 элементов:
11:9339339133_977775171795353597171577779_3319339339

[kazvadim]

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

[Dmitriy40]

Иссякнет терпение, так как тот же PARI/GP вполне себе работает с целыми числами до миллиона (может и больше, не помню) знаков.

[kazvadim]

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

Иссякнет терпение, так как тот же PARI/GP вполне себе работает с целыми числами до миллиона (может и больше, не помню) знаков.

С такой мощной поддержкой, как Ваша, моё терпение не исчерпается!

[Dmitriy40]

kazvadim
Ну-ну.
Вот смотрите, все начальные палиндромы длиной до 27 знаков (или все числа длиной до 13 знаков без чётных цифр и не начинающиеся с 5, их было почти 100 млн) перебрались грубо за 15ч, или типа 7млн чисел в час. Чтобы перебрать все начальные палиндромы длиной 101 цифры надо проверить порядка $4\cdot5^{49}\approx7\cdot10^{34}$ чисел, для чего понадобится не менее $10^{28}$ часов или $10^{24}$ лет счёта. Даже запустив все компьютеры в мире время счёта не снизится даже до тысячелетий. Удачи вам в ожидании.
Про более длинные палиндромы вообще промолчу.

[kazvadim]

Dmitriy40
И не ставлю так задачу вычислений. Остановимся на 12, так и остановимся. Сделали и сделали, показали, что было в наших возможностях, а дальше (известный приём, не мы первые) ставим ремарку, что дескать открытая задача.

[kazvadim]

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

11:9339339133_977775171795353597171577779_3319339339

Приведу Вашу цепочку для примера.
Назовём 9339339133 «цифровой приставкой», которая даёт цепочку, к простому палиндрому 977775171795353597171577779. Такие цифровые приставки не могут содержать цифру 1 или 7 в количестве больше одной, иначе число будет делиться на 3, что видно из прогрессий $3k+1, 3k+2$. Поэтому, после появления цифры 1 или 7, дальше подставляем только 3 и 9, программа будет работать быстрей.

[kazvadim]

Недооценил свойства простых палиндромов, содержащих чётные цифры.
Добавим операцию ««отражения» натурального числа». Когда цифра числа «отражается» в 10-ичной СС: 1 в 9, 2 в 8, 3 в 7, 4 в 6, 5 в 5, 6 в 4, 7 в 3, 8 в 2, 9 в 1; 0 в 0 (это странный приём, не нашёл пока лучше). Такая последовательность пар простых палиндромов начинается так:
3,7; 5,5; 7,3; 181,929; 191, 919; 313, 797; 353,757; 383,727; 727,383; 757,353; 797,313; 919,191; 929,181; 10301,90709; 12421,98689; 12721,98389; 14341,96769; 16061,94049; 17971,93139; 30403,70607; 30803,70207; 32323,78787;...
Свойство таких пар: с увеличением количества знаков простых палиндромов - количество простых палиндромов в таких парах с чётными цифрами существенно преобладает.

[novichok2018]

Интересно, что у матриц тоже есть палиндромы, и это сильно помогает при вычислениях.

[kazvadim]

Реализация простого палиндрома в стеснённых условиях.
Введём операцию «палиндромного бинарного цифрового умножения». Для простых палиндромов - это операция «палиндромного бинарного цифрового умножения +» («+» - обозначение вставки центральной цифры, так как простые палиндромы - из нечётного количества цифр). Это проще пояснить на примерах.
131, 1311131, 131113161311131 – первая цепочка из 3-х таких простых палиндромов, полученная с помощью операции «палиндромного бинарного цифрового умножения +».
131, 131-1-131, 131-1-131-6-131-1-131, здесь простой палиндром 131 цифро-умножается на 2, 4 с вставкой центральной цифры (первый шаг, где вставка - цифра 1; второй шаг, где вставка – цифра 6).
Свойства центральной вставки: не может быть цифра 0, для каждого числа цепочки возможны или 1,3,4,6,7,9, или 2,3,5,6,8,9.
Цепочка из 5-ти простых палиндромов:
37404540473, 37404540473937404540473,
37404540473937404540473237404540473937404540473,
37404540473937404540473237404540473937404540473337404540473937404540473237404540473937404540473, 374045404739374045404732374045404739374045404733374045404739374045404732374045404739374045404737
37404540473937404540473237404540473937404540473337404540473937404540473237404540473937404540473 (191 знаков).
Встречаются и простые красавицы:
9989899699898999998989969989899999898996998989999989899699898997998989969989899999898996998989999989899699898999998989969989899 (127 знаков).
Напрашивается вывод: при известных оценках стремительного уменьшения количества простых палиндромов с увеличением количества их знаков - реализация простого палиндрома исключительна.

[Dmitriy40]

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

Встречаются и простые красавицы:
9989899699898999998989969989899999898996998989999989899699898997998989969989899999898996998989999989899699898999998989969989899 (127 знаков).

Да, но ни половина ни четверть её совсем не простые.


Бинарную операцию $p \oplus X \to pXp$ логичней назвать "удвоение_со_вставкой".
Чтобы сократить "портянки" палиндромов введу сокращённую запись: N:[p, x1, x2, ..., xi], где N это количество палиндромов в последовательности, p начальный палиндром, xi это цифры для вставки по порядку следования. Пример: цепочка палиндромов 131, 1311131, 131113161311131 записывается как 3:[131, 1, 6]. А ваша простая красавица 9989899699898999998989969989899999898996998989999989899699898997998989969989899999898996998989999989899699898999998989969989899 запишется как 5:[9989899, 6, 9, 9, 7].

Как-то странно Вы приводите свои примеры, вот нашли цепочку из 5 простых палиндромов, но почему-то пропустили цепочку из 5 простых палиндромов гораздо меньшего начального палиндрома
5:[1362631, 6, 7, 6, 3], digits=127 (длина последнего палиндрома в цифрах)

Более того, пропустили 6 цепочек той же длины и той длины в цифрах
5:[10348284301, 8, 9, 9, 3], digits=191
5:[12454945421, 4, 7, 9, 2], digits=191
5:[14467076441, 3, 2, 3, 1], digits=191
5:[15710901751, 9, 3, 8, 5], digits=191
5:[17073737071, 9, 4, 3, 5], digits=191
5:[30776367703, 2, 5, 9, 9], digits=191
и цепочки меньшей длины в цифрах и начальных палиндромов
5:[142545241, 5, 9, 1, 6], digits=159
5:[154303451, 7, 1, 3, 9], digits=159
5:[345868543, 3, 4, 7, 1], digits=159
5:[345868543, 3, 4, 7, 9], digits=159
5:[369040963, 5, 9, 1, 1], digits=159
5:[926787629, 3, 9, 4, 3], digits=159
5:[929777929, 5, 8, 3, 7], digits=159
5:[940474049, 1, 4, 7, 1], digits=159

Но совсем уж странно что пропустили цепочку из 6 простых палиндромов!
6:[794999497, 5, 2, 5, 6, 1], digits=319

Мне хватило часа на написание программы (с отладкой, проверкой возможных оптимизаций и оформления вывода) и она за два часа уже проверила все начальные простые палиндромы длиной до 17 цифр включительно. И нашла при этом не только 2791 цепочек длиной 5, но и 57 цепочек длиной 6 и даже одну цепочку длиной 7 из почти 900 цифр!
7:[7047894987407, 1, 6, 2, 2, 5, 2], digits=895

(Приведу ещё несколько интересных цепочек)

Например вставка только одной и той же цифры:
6:[14515771917751541, 1, 1, 1, 1, 1], digits=575
5:[32092073937029023, 2, 2, 2, 2], digits=287
5:[30038882128883003, 3, 3, 3, 3], digits=287
5:[1044719623269174401, 3, 3, 3, 3], digits=319
5:[92508131113180529, 4, 4, 4, 4], digits=287
5:[10271999099917201, 5, 5, 5, 5], digits=287
5:[129379858973921, 6, 6, 6, 6], digits=255
6:[179702638323836207971, 6, 6, 6, 6, 6], digits=703
5:[98378705450787389, 7, 7, 7, 7], digits=287
5:[1034563660663654301, 7, 7, 7, 7], digits=319
5:[1391767049407671931, 8, 8, 8, 8], digits=319
6:[139543656345931, 9, 9, 9, 9, 9], digits=511

Или например три разных цепочки из одного начального палиндрома:
5:[72628276867282627, 9, 9, 8, 2], digits=287
5:[72628276867282627, 9, 9, 8, 6], digits=287
5:[72628276867282627, 9, 9, 8, 8], digits=287
5:[1261134435344311621, 8, 9, 3, 5], digits=319
5:[1261134435344311621, 8, 9, 3, 8], digits=319
5:[1261134435344311621, 8, 9, 3, 9], digits=319
5:[114545538040835545411, 2, 6, 6, 6], digits=351
5:[114545538040835545411, 2, 6, 6, 8], digits=351
5:[114545538040835545411, 2, 6, 6, 9], digits=351
5:[147753504767405357741, 4, 9, 2, 6], digits=351
5:[147753504767405357741, 4, 9, 2, 8], digits=351
5:[147753504767405357741, 4, 9, 2, 9], digits=351
5:[152525188777881525251, 6, 6, 9, 2], digits=351
5:[152525188777881525251, 6, 6, 9, 3], digits=351
5:[152525188777881525251, 6, 6, 9, 8], digits=351
5:[181635325222523536181, 1, 9, 5, 6], digits=351
5:[181635325222523536181, 1, 9, 5, 8], digits=351
5:[181635325222523536181, 4, 6, 8, 6], digits=351 - мало того что три разных, так ещё и разных прямо с первой вставляемой цифры!
5:[199156236545632651991, 1, 3, 2, 2], digits=351
5:[199156236545632651991, 1, 3, 2, 6], digits=351
5:[199156236545632651991, 1, 3, 2, 9], digits=351
5:[305269762525267962503, 9, 6, 7, 1], digits=351
5:[305269762525267962503, 9, 6, 7, 3], digits=351
5:[305269762525267962503, 9, 6, 7, 6], digits=351
5:[327537460242064735723, 3, 7, 7, 7], digits=351
5:[327537460242064735723, 3, 7, 7, 9], digits=351
5:[327537460242064735723, 3, 9, 8, 8], digits=351
5:[343013773717377310343, 7, 1, 1, 1], digits=351
5:[343013773717377310343, 7, 1, 1, 4], digits=351
5:[343013773717377310343, 7, 1, 1, 9], digits=351
5:[354395947575749593453, 8, 8, 8, 2], digits=351
5:[354395947575749593453, 8, 8, 8, 3], digits=351
5:[354395947575749593453, 8, 8, 8, 9], digits=351
5:[354590413333314095453, 1, 7, 9, 3], digits=351
5:[354590413333314095453, 1, 7, 9, 8], digits=351
5:[354590413333314095453, 1, 7, 9, 9], digits=351

Или две, но длиной 6:
6:[139543656345931, 9, 9, 9, 9, 6], digits=511
6:[139543656345931, 9, 9, 9, 9, 9], digits=511
6:[9986509897989056899, 5, 5, 6, 3, 2], digits=639
6:[9986509897989056899, 5, 5, 6, 3, 5], digits=639
6:[111935667626766539111, 9, 5, 8, 9, 3], digits=703
6:[111935667626766539111, 9, 5, 8, 9, 7], digits=703
6:[118787590666095787811, 7, 6, 3, 3, 2], digits=703
6:[118787590666095787811, 7, 6, 3, 3, 9], digits=703
6:[147846661050166648741, 6, 3, 8, 2, 2], digits=703
6:[147846661050166648741, 6, 3, 8, 2, 5], digits=703
6:[163786209535902687361, 8, 2, 9, 6, 3], digits=703
6:[163786209535902687361, 8, 2, 9, 6, 6], digits=703
6:[167442165868561244761, 6, 4, 4, 1, 1], digits=703
6:[167442165868561244761, 6, 4, 4, 1, 3], digits=703
6:[167650445898544056761, 3, 8, 5, 8, 6], digits=703
6:[167650445898544056761, 3, 8, 5, 8, 9], digits=703
6:[302047912818219740203, 5, 8, 5, 5, 5], digits=703
6:[302047912818219740203, 5, 8, 5, 5, 8], digits=703
6:[358573139949931375853, 7, 3, 3, 7, 6], digits=703
6:[358573139949931375853, 7, 3, 3, 7, 7], digits=703

Или две, но разных не лишь в конце:
5:[724869313968427, 9, 4, 9, 2], digits=255
5:[724869313968427, 9, 9, 2, 8], digits=255
5:[1441628162618261441, 6, 3, 9, 8], digits=319
5:[1441628162618261441, 6, 8, 3, 3], digits=319
5:[7567603576753067657, 4, 3, 2, 3], digits=319
5:[7567603576753067657, 4, 4, 1, 4], digits=319
5:[116298929000929892611, 2, 2, 2, 2], digits=351
5:[116298929000929892611, 2, 8, 3, 3], digits=351
5:[175975900111009579571, 4, 3, 9, 7], digits=351
5:[175975900111009579571, 4, 6, 9, 3], digits=351
5:[195000986292689000591, 1, 1, 4, 3], digits=351
5:[195000986292689000591, 1, 4, 1, 4], digits=351
5:[323039877050778930323, 4, 7, 6, 8], digits=351
5:[323039877050778930323, 9, 9, 4, 3], digits=351

Или с кучей одинаковых цифр в начальном палиндроме (соответственно и во всех остальных):
5:[922000030000229, 9, 3, 7, 3], digits=255
5:[74569100000196547, 3, 1, 4, 6], digits=287
5:[98345000000054389, 5, 3, 3, 9], digits=287
5:[785561111165587, 8, 2, 5, 5], digits=255
5:[12671111711117621, 4, 1, 4, 1], digits=287
5:[19022229492222091, 5, 3, 4, 6], digits=287
5:[19891122222119891, 9, 3, 1, 7], digits=287
5:[716333303333617, 2, 2, 5, 8], digits=255
5:[70103333333330107, 8, 8, 8, 9], digits=287
5:[136444474444631, 6, 6, 4, 6], digits=255
5:[99981344444318999, 6, 6, 7, 4], digits=287
5:[3446744442444476443, 9, 3, 3, 7], digits=319
5:[958975555579859, 6, 2, 2, 5], digits=255
5:[19755552125555791, 5, 5, 2, 6], digits=287
5:[1340945555555490431, 1, 3, 3, 1], digits=319
5:[73736666166663737, 7, 3, 2, 9], digits=287
5:[75668966666986657, 2, 3, 7, 3], digits=287
5:[755767777767557, 4, 6, 9, 3], digits=255
5:[17037777877773071, 4, 6, 8, 3], digits=287
6:[19858188888185891, 4, 3, 3, 1, 4], digits=575
5:[704599999995407, 7, 6, 2, 9], digits=255
5:[90899990109999809, 9, 5, 2, 5], digits=287
5:[3300000111110000033, 4, 9, 8, 2], digits=319

Или вставляемые цифры сами составляют палиндром:
6:[139543656345931, 9, 9, 9, 9, 9], digits=511
6:[360660272066063, 9, 9, 4, 9, 9], digits=511
6:[14515771917751541, 1, 1, 1, 1, 1], digits=575
6:[39714947074941793, 5, 9, 1, 9, 5], digits=575
6:[1438143852583418341, 9, 1, 7, 1, 9], digits=639
6:[3546336597956336453, 7, 4, 7, 4, 7], digits=639
6:[3854658289828564583, 1, 4, 1, 4, 1], digits=639
6:[7544706492946074457, 6, 9, 2, 9, 6], digits=639
6:[9648894496944988469, 9, 2, 8, 2, 9], digits=639
6:[107699646616646996701, 3, 9, 2, 9, 3], digits=703
6:[124418618090816814421, 6, 1, 1, 1, 6], digits=703
6:[128450500000005054821, 9, 3, 7, 3, 9], digits=703
6:[137643805020508346731, 9, 4, 1, 4, 9], digits=703
6:[146836343414343638641, 9, 6, 2, 6, 9], digits=703
6:[151810859060958018151, 6, 7, 7, 7, 6], digits=703
6:[166234232858232432661, 6, 4, 4, 4, 6], digits=703
6:[179702638323836207971, 6, 6, 6, 6, 6], digits=703
6:[195187417818714781591, 3, 3, 8, 3, 3], digits=703
6:[197989293979392989791, 3, 1, 1, 1, 3], digits=703
6:[303822755262557228303, 7, 4, 1, 4, 7], digits=703
6:[307036212161212630703, 7, 1, 7, 1, 7], digits=703
6:[320811009080900118023, 7, 6, 5, 6, 7], digits=703
6:[338219971191179912833, 9, 3, 3, 3, 9], digits=703
6:[344854156141651458443, 9, 9, 9, 9, 9], digits=703
6:[355485905454509584553, 6, 9, 9, 9, 6], digits=703
6:[363636864454468636363, 9, 6, 8, 6, 9], digits=703
6:[366452812878218254663, 3, 9, 5, 9, 3], digits=703
6:[374666171303171666473, 6, 7, 7, 7, 6], digits=703
6:[379675371767173576973, 7, 9, 5, 9, 7], digits=703
6:[389245555080555542983, 8, 3, 4, 3, 8], digits=703

-- 07.01.2021, 13:54 --

Кстати насчёт оптимизаций, давно хотел сказать. Исключение из проверок вставления нуля (ну да, не подумал что для палиндромов он недопустим) ускорило программу с 8.7с до 8.1с, а исключение трёх из девяти других цифр ускорило с 8.1с до 7.9с. Общее ускорение составило жалкие 10%. Так что далеко не любая оптимизация перебора имеет смысл.

[kazvadim]

Dmitriy40
Спасибо! Пока только начинаю знакомиться с PARI/GP, воспользовавшись Вашим советом. Программы пишу коряво (мягко говоря). Нашёл 9 5-ок и, зная, что пропустил кучу вариантов, привёл одну. Вот если бы мне увидеть, как Вы написали программу, то моё обучение продвинулось бы. Красивое простое число - для украшения сообщения, оно отдельное и не относится к цепочкам.

[mathpath]

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

Напрашивается вывод: при известных оценках стремительного уменьшения количества простых палиндромов с увеличением количества их знаков - реализация простого палиндрома исключительна.

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