2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 21  След.
 
 Re: Простые числа и палиндромы
Сообщение29.12.2020, 22:48 
Заслуженный участник


20/08/14
11057
Россия, Москва
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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение30.12.2020, 00:07 


15/11/20
179
Россия, Москва.
Dmitriy40, Ваша взяла... у меня прога туфтовая... зато есть новые идеи... поработаем?

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение30.12.2020, 08:32 
Заслуженный участник


20/08/14
11057
Россия, Москва
На удивление найдена и последовательность из 11 элементов:
11:9339339133_977775171795353597171577779_3319339339

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение30.12.2020, 11:54 


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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение30.12.2020, 12:31 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение30.12.2020, 12:42 


15/11/20
179
Россия, Москва.
Dmitriy40 в сообщении #1498322 писал(а):
Иссякнет терпение, так как тот же PARI/GP вполне себе работает с целыми числами до миллиона (может и больше, не помню) знаков.
С такой мощной поддержкой, как Ваша, моё терпение не исчерпается!

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение30.12.2020, 13:25 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение30.12.2020, 13:44 


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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение01.01.2021, 14:03 


15/11/20
179
Россия, Москва.
Dmitriy40 в сообщении #1498311 писал(а):
11:9339339133_977775171795353597171577779_3319339339
Приведу Вашу цепочку для примера.
Назовём 9339339133 «цифровой приставкой», которая даёт цепочку, к простому палиндрому 977775171795353597171577779. Такие цифровые приставки не могут содержать цифру 1 или 7 в количестве больше одной, иначе число будет делиться на 3, что видно из прогрессий $3k+1, 3k+2$. Поэтому, после появления цифры 1 или 7, дальше подставляем только 3 и 9, программа будет работать быстрей.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение02.01.2021, 01:15 


15/11/20
179
Россия, Москва.
Недооценил свойства простых палиндромов, содержащих чётные цифры.
Добавим операцию ««отражения» натурального числа». Когда цифра числа «отражается» в 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;...
Свойство таких пар: с увеличением количества знаков простых палиндромов - количество простых палиндромов в таких парах с чётными цифрами существенно преобладает.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение05.01.2021, 10:59 
Заблокирован


16/04/18

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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 06:20 


15/11/20
179
Россия, Москва.
Реализация простого палиндрома в стеснённых условиях.
Введём операцию «палиндромного бинарного цифрового умножения». Для простых палиндромов - это операция «палиндромного бинарного цифрового умножения +» («+» - обозначение вставки центральной цифры, так как простые палиндромы - из нечётного количества цифр). Это проще пояснить на примерах.
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 знаков).
Напрашивается вывод: при известных оценках стремительного уменьшения количества простых палиндромов с увеличением количества их знаков - реализация простого палиндрома исключительна.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 13:24 
Заслуженный участник


20/08/14
11057
Россия, Москва
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%. Так что далеко не любая оптимизация перебора имеет смысл.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 16:25 


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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение07.01.2021, 16:51 


16/08/19
103
kazvadim в сообщении #1499445 писал(а):
Напрашивается вывод: при известных оценках стремительного уменьшения количества простых палиндромов с увеличением количества их знаков - реализация простого палиндрома исключительна.


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 301 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 21  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group