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

[kazvadim]

Назовём палиндром, который является простым числом, простым палиндромом.
Начало последовательности простых палиндромов:
1) 1, 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313, 353, 373, 383, 727, 757, 787, 797, 919, 929, 10301, 10501, 10601, 11311, 11411, 12421, 12721, 12821, 13331, 13831, 13931, 14341, 14741, 15451, 15551, 16061, 16361, 16561, 16661, 17471, 17971, 18181, 18481, 19391,19891, 19991, ...
Свойство простых палиндромов – это числа состоящие из нечётного количества цифр (кроме числа 11). Палиндромы с чётным количеством цифр делятся на 11.
Исключим из последовательности 1) палиндромы с чётными числами в цифрах:
2) 1, 3, 5, 7, 11, 101, 131, 151, 191, 313, 353, 373, 757, 797, 919, 929, 10301, 10501, 11311, 13331, 13931, 15551, 17971, 19391, 19991, ...

Введём операцию «удлинения палиндрома». Когда к палиндрому «в начале и в конце» добавляется цифра и получается палиндром на 2 знака длиннее.
Построим цепочки простых палиндромов из последовательности 2), применив операцию «удлинения палиндрома». Подходят цифры 1, 3, 7, 9, другие дадут составные палиндромы. Цепочки чисел из 2-х, 3-х, 4-х знаков встречаются часто.
Цепочки из 5-ти простых палиндромов:
35353, 3353533, 333535333, 93335353339, 3933353533393;
1513151, 915131519, 79151315197, 3791513151973, 337915131519733;
7159517, 371595173, 93715951739, 9937159517399, 999371595173999;
173373371, 71733733717, 9717337337179, 397173373371793, 33971733733717933;
739777937, 37397779373, 3373977793733, 933739777937339, 19337397779373391;
919171919, 99191719199, 9991917191999, 799919171919997, 37999191719199973;
951353159, 79513531597, 3795135315973, 937951353159739, 99379513531597399;...
Из 6-ти:
1917191, 919171919, 99191719199, 9991917191999, 799919171919997, 37999191719199973;...
Сколько удалось пока посчитать, дальше программа не справляется, моего умения не хватает.

[kotenok gav]

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

1

Извините, а вы уверены, что это простое?
<дальше здесь была глупость, которую я удалил>

[kazvadim]

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

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

1

Извините, а вы уверены, что это простое?

Не уверен. Дела здесь это не меняет.

[Andrey A]

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

дальше программа не справляется...

Из такого исследования пока что видно только что их много — простых палиндромов. Взять помощнее программу, окажется что их слишком много. Если же искать существенные свойства, сразу обращает на себя внимание зависимость от 10-ичной системы счисления. В троичной палиндром не интересен? Хотя и тут уже мало доказанных фактов (см. например https://dxdy.ru/post257343.html#p257343), и самые мощные компьютеры не спасают. А не хватает на мой взгляд хорошего вопроса. Откидывая палиндромы из одной и двух цифр, предложу как вариант: существует ли порог, по превышении которого любое натуральное число представимо в виде палиндрома в некоторой $p$-ичной системе счисления? Если нет, множество $\mathbb{N}$ распадается на два подмножества, и как поведут себя в этой ситуации простые — уже интересно. От $7$ до $41$ на самом деле всего два простых не представимы палиндромом из $\geqslant 3$-х цифр — $11,19$. Причем $17$ и $31$ представимы двумя способами. Как-то так. А единицу из списка простых надо было, конечно, убрать.

[alisa-lebovski]

Стоит посмотреть в двоичной системе, она наиболее фундаментальна.

[kazvadim]

Andrey A в сообщении #1498090 писал(а):

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

дальше программа не справляется...

Из такого исследования пока что видно только что их много — простых палиндромов. Взять помощнее программу, окажется что их слишком много.

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

Andrey A в сообщении #1498090 писал(а):

Если же искать существенные свойства, сразу обращает на себя внимание зависимость от 10-ичной системы счисления. В троичной палиндром не интересен?

Интересен. Будет нам с вами ещё работа. Пока бы выудить побольше из 10-ичной системы. Например, в проблеме 196 ищут 10-ичный палиндром или его отсутствие.

Andrey A в сообщении #1498090 писал(а):

Хотя и тут уже мало доказанных фактов (см. например https://dxdy.ru/post257343.html#p257343), и самые мощные компьютеры не спасают. А не хватает на мой взгляд хорошего вопроса.

Спасибо, интересно. На досуге поразмыслю.

Andrey A в сообщении #1498090 писал(а):

Откидывая палиндромы из одной и двух цифр, предложу как вариант: существует ли порог, по превышении которого любое натуральное число представимо в виде палиндрома в некоторой $b$-ичной системе счисления? Если нет, множество $\mathbb{N}$ распадается на два подмножества, и как поведут себя в этой ситуации простые — уже интересно. От $7$ до $41$ на самом деле всего два простых не представимы палиндромом из $\geqslant 3$-х цифр — $11,19$. Причем $17$ и $31$ представимы двумя способами. Как-то так.

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

Andrey A в сообщении #1498090 писал(а):

А единицу из списка простых надо было, конечно, убрать.

Сознаю, рассеянность, каюсь... когда меня носом ткнули, то правка сообщения была уже закрыта. Может модератора попросить о помощи?

-- 28.12.2020, 11:35 --

alisa-lebovski в сообщении #1498097 писал(а):

Стоит посмотреть в двоичной системе, она наиболее фундаментальна.

Спасибо, посмотрим, вот и ещё нам работа...

[kazvadim]

Последовательность чисел Софи Жермен A005384:
2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953, 1013, 1019, 1031, 1049, 1103, 1223, 1229, 1289, 1409, 1439, 1451, 1481, 1499, 1511, 1559,...
Простые палиндромы в числах Софи Жермен:
2, 3, 5, 11, 131, 191, 19391, 38183, 1508051, 1609061, 1628261, 3717173, 3916193, 161535161, 161838161, 170646071, 172747271, 182949281, 190909091, 352909253, 354848453, 360818063, 364636463,...
В этой последовательности простые палиндромы начинаются только с цифр 1, 3. Последняя цифра 7 палиндрома (равная первой) даст составное число с делителем 5, так как $2\cdot7+1=15$; простые палиндромы, начинающиеся на цифру 9, не дают результата в числах Софи Жермен.
Цепи Каннингема 1-го и 2-го типов не получаются из простых палиндромов (когда знаков числа больше 2).

[Andrey A]

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

... не всё понял. Поясните, пожалуйста

$17=101_4=10001_2$
$31=111_5=11111_2$

В цепных дробях вопрос сводится к количеству оснований квадратов $<m$, сравнимых с единицей по $\mod m$. Поэтому наименьшее количество палиндромов получаем именно если $m$ степень простого или удвоенная степень простого: $\dfrac{18}{1}=18, \dfrac{18}{17}=1,16,1.$ Тут $1^2 \equiv 17^2 \equiv 1 \mod 18,$ и других нет. Но для составного $m=21$ квадратов больше: $1^2 \equiv 8^2 \equiv 13^2 \equiv 20^2 \mod 21.$ И, соответственно, кроме $\dfrac{21}{1}=21,\dfrac{21}{20}=1,19,1$ имеем нетривиальные $\dfrac{21}{8}=2,1,1,1,2;\ \dfrac{21}{13}=1,1,1,1,1,1,1.$

Можно условиться записывать $p$-ичную дробь подобным образом, например через двойной slash: $17//4=1,0,1;\ 31//5=1,1,1.$ И тогда оказывается, что $1$ и $m-1$ "в знаменателе" тоже возвращают палиндром, поскольку в "одноричной" системе счисления палиндром – любое число, а $m//(m-1)=1,1.$ Симптоматично. Вот если бы выяснить, какими свойствами должен обладать "знаменатель" в случае нетривиального палиндрома, это действительно было бы решением. Может и несложно, просто вопрос так не ставился.

[kazvadim]

Спасибо, Andrey A, за задачу, заманчиво решить... Правильно ли понимаю, что нетривиальный палиндром - это составной палиндром (чтобы не путаться).

[Andrey A]

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

нетривиальный палиндром - это составной палиндром

Ни в коем случае. Нетривиальный палиндром — такой, которым может быть выражено любое $m.$ Либо это палиндром из одного знака (цифры) $m$, либо из двух знаков $11$ в $(m-1)$-ичной сист. сч., либо $m$ единиц в "одноричной" сист. сч.
Я понимаю вопрос. Аналогии с цепными дробями могут навести на мысль, а могут и запутать.

[kazvadim]

Andrey A в сообщении #1498128 писал(а):

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

нетривиальный палиндром - это составной палиндром

Ни в коем случае. Нетривиальный палиндром — такой, которым может быть выражено любое $m.$ Либо это палиндром из одного знака $m$, либо из двух знаков $11$ в $(m-1)$-ичной сист. сч., либо $m$ единиц в "одноричной" сист. сч.
Я понимаю вопрос. Аналогии с цепными дробями могут навести на мысль, а могут и запутать.

Ещё хуже запутался. Приведите несколько примеров таких тривиальных палиндромов, получаемых из $m$ или $m-1$ (ну как-то, чтобы я понял...)...

-- 28.12.2020, 16:22 --

Andrey A, alisa-lebovski.
Простые палиндромы (знаков больше 2) в 10-ичной, 3-ичной, 2-ичной СС.
101: [3]10202, [2]1100101;
131: [3]11212, [2]10000011;
151: [3]12121, [2]10010111;
181: [3]20201, [2]10110101;
191: [3]21002, [2]10111111;
313: [3]102121, [2]100111001;
353: [3]111002, [2]101100001;
373: [3]111211, [2]101110101;
383: [3]112012, [2]101111111;
727: [3]222221, [2]1011010111;
757: [3]1001001, [2]1011110101;
787: [3]1002011, [2]1100010011;
797: [3]1002112, [2]1100011101;
919: [3]1021001, [2]1110010111;
929: [3]1021102, [2]1110100001;
10301: [3]112010112, [2]10100000111101;
10501: [3]112101221, [2]10100100000101;
10601: [3]112112122, [2]10100101101001;
11311: [3]120111221, [2]10110000101111;
11411: [3]120122122, [2]10110010010011;
12421: [3]122001001, [2]11000010000101;
12721: [3]122110011, [2]11000110110001;
12821: [3]122120212, [2]11001000010101;
13331: [3]200021202, [2]11010000010011;
13831: [3]200222021, [2]11011000000111;
13931: [3]201002222, [2]11011001101011;
14341: [3]201200011, [2]11100000000101;
14741: [3]202012222, [2]11100110010101;
15451: [3]210012021, [2]11110001011011;
15551: [3]210022222, [2]11110010111111;
16061: [3]211000212, [2]11111010111101;
16361: [3]211102222, [2]11111111101001;
16561: [3]211201101, [2]100000010110001;
16661: [3]211212002, [2]100000100010101;
17471: [3]212222002, [2]100010000111111;
17971: [3]220122121, [2]100011000110011;
18181: [3]220221101, [2]100011100000101;
18481: [3]221100111, [2]100100000110001;
19391: [3]222121012, [2]100101110111111;
19891: [3]1000021201, [2]100110110110011;
19991: [3]1000102102, [2]100111000010111;
30103: [3]1112021221, [2]111010110010111;
30203: [3]1112102122, [2]111010111111011;
30403: [3]1112201001, [2]111011011000011;
30703: [3]1120010011, [2]111011111101111;
30803: [3]1120020212, [2]111100001010011;
31013: [3]1120112122, [2]111100100100101;
31513: [3]1121020011, [2]111101100011001;
32323: [3]1122100011, [2]111111001000011;
32423: [3]1122110212, [2]111111010100111;
33533: [3]1200222222, [2]1000001011111101;
34543: [3]1202101101, [2]1000011011101111;
34843: [3]1202210111, [2]1000100000011011;
35053: [3]1210002021, [2]1000100011101101;
35153: [3]1210012222, [2]1000100101010001;
35353: [3]1210111101, [2]1000101000011001;
35753: [3]1211001012, [2]1000101110101001;
36263: [3]1211202002, [2]1000110110100111;
36563: [3]1212011012, [2]1000111011010011;
37273: [3]1220010111, [2]1001000110011001;
37573: [3]1220112121, [2]1001001011000101;
38083: [3]1221020111, [2]1001010011000011;
38183: [3]1221101012, [2]1001010100100111;
38783: [3]1222012102, [2]1001011101111111;
39293: [3]1222220022, [2]1001100101111101;
70207: [3]10120022021, [2]10001001000111111;
70507: [3]10120201101, [2]10001001101101011;
70607: [3]10120212002, [2]10001001111001111;
71317: [3]10121211101, [2]10001011010010101;
71917: [3]10122122121, [2]10001100011101101;
72227: [3]10200002002, [2]10001101000100011;
72727: [3]10200202121, [2]10001110000010111;
73037: [3]10201012002, [2]10001110101001101;
73237: [3]10201110111, [2]10001111000010101;
73637: [3]10202000022, [2]10001111110100101;
74047: [3]10202120111, [2]10010000100111111;
74747: [3]10210112102, [2]10010001111111011;
75557: [3]10211122102, [2]10010011100100101;
76367: [3]10212202102, [2]10010101001001111;
76667: [3]10220011112, [2]10010101101111011;
77377: [3]10221010211, [2]10010111001000001;
77477: [3]10221021112, [2]10010111010100101;
77977: [3]10221222001, [2]10011000010011001;
78487: [3]10222122221, [2]10011001010010111;
78787: [3]11000002001, [2]10011001111000011;
78887: [3]11000012202, [2]10011010000100111;
79397: [3]11000220122, [2]10011011000100101;
79697: [3]11001022202, [2]10011011101010001;
79997: [3]11001201212, [2]10011100001111101;
90709: [3]11121102121, [2]10110001001010101;
91019: [3]11121212002, [2]10110001110001011;
93139: [3]11201202121, [2]10110101111010011;
93239: [3]11201220022, [2]10110110000110111;
93739: [3]11202120211, [2]10110111000101011;
94049: [3]11210000022, [2]10110111101100001;
94349: [3]11210102102, [2]10111000010001101;
94649: [3]11210211112, [2]10111000110111001;
94849: [3]11211002221, [2]10111001010000001;
94949: [3]11211020122, [2]10111001011100101;
95959: [3]11212122001, [2]10111011011010111;
96269: [3]11220001112, [2]10111100000001101;
96469: [3]11220022221, [2]10111100011010101;
96769: [3]11220202001, [2]10111101000000001;
97379: [3]11221120122, [2]10111110001100011;
97579: [3]11221212001, [2]10111110100101011;
97879: [3]11222021011, [2]10111111001010111;
98389: [3]11222222001, [2]11000000001010101;
98689: [3]12000101011, [2]11000000110000001;
...
Ничего примечательного не увидел.

[Andrey A]

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

ну как-то, чтобы я понял...

$11_2=3$
$11_3=4$
$11_4=5$
$11_5=6$
$11_6=7$

$.\ .\ .$


kazvadim
Вы бы лучше выписали те простые, которые не представимы палиндромом ни в одной сис.сч. Если уж ничего другого не признаете кроме "метода выписывания".

[kazvadim]

Andrey A в сообщении #1498134 писал(а):

kazvadim
Вы бы лучше выписали те простые, которые не представимы палиндромом ни в одной сис.сч. Если уж ничего другого не признаете кроме "метода выписывания".

Простые, которые не являются палиндромами - это пожалуйста по первой заявке помогу. А вот по поводу определения простого числа, то не понял - это при чём здесь система счисления? Может быть Вы имеете в виду, что ни в одной системе счисления простое число не будет палиндромом. Так систем счисления бесконечно много, это надо ставить локальный предел на количество знаков, ограничивая количество систем счисления для выставленного предела. Какая польза будет от этой рутинной работы? А выписываю не что попало, а то, что нужно для работы...

[Andrey A]

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

Так систем счисления бесконечно много...

Для отображения простого $m$ в $p$-ичной сис.сч. достаточно брать $p<\sqrt{m}$, поскольку двузначный палиндром нас не интересует. Раскладывать можно так:
1) Находим остаток от деления $m/p$, это последний знак $a_k$.
2) Находим $m'=(m-a_k)/p$ и остаток от деления $m'/p$, это предпоследний знак $a_{k-1}$.
И далее по той же схеме, пока не получим $m''^{...}'<p$, это первый знак $a_1.$

[wrest]

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

Начало последовательности простых палиндромов:

А продолжение тут A002385