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

[kazvadim]

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

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

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

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

Ключевое слово = поиск. Разумеется, что простые палиндромы - это только подкласс простых чисел. Вы рассмотрели общий алгоритм - это отлично, палиндромы могут с маленькой вероятностью зацепиться за какие-нибудь веточки, если не обнаруживается ни одной такой веточки, то и будет закрыт вопрос о палиндромах. Закономерность в общем решении если и есть, то она будет сложной, а на палиндромах (частное решение) может что-то и удастся увидеть, как отросточек общей закономерности...

[lel0lel]

kazvadim
При всём уважении к вашему исследованию, хочется заметить, что палиндромность -- слишком искусственный вид симметрии, который зависит от выбора позиционной системы счисления и, как отмечалось ранее, десятичная система не является какой-то фундаментальной. Поэтому искать закономерности конечно можно, если есть время и желание, но вероятность успеха невелика. Сейчас посмотрю какие получаются деревья, которые меня интересуют больше всего, а потом посеем палиндромы) Предложите пожалуйста два-три палиндрома, которые вам наиболее симпатичны, можно многозначные, вплоть до 100 знаков.

Вот результат для дерева с тройкой в качестве корня:
$\{1, 8, 54, 344, 2303, 16016, 115907, 866177, 6654537\}$ -- число ветвей в поколениях,
$\{8, 6.75, 6.37, 6.69, 6.95, 7.23, 7.47, 7.68\}$ -- "коэффициенты размножения ветвей". Наблюдается рост, но смотреть дальше не хватает терпения -- долго.

[kazvadim]

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

-- 21.06.2021, 00:08 --

Простое число остаётся простым во всех системах счисления, поэтому было бы интересно посмотреть на 6-ричные простые палиндромы. Оценить их плотность по сравнению с плотностью 10-тичных простых палиндромов. Дело в том, что прогрессии $6k-1$ и $6k+1$ давно доказаны.

[Someone]

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

мне больше нравится 6-ричная, но сразу с места в карьер не стал, а то...

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

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

Дело в том, что прогрессии $6k-1$ и $6k+1$ давно доказаны.

В каком смысле "доказаны"? Что именно о них доказано?
Предположение: доказано, что все простые числа, кроме $2$ и $3$, содержатся в арифметических прогрессиях $6k-1$ и $6k+1$.
Ну да, можно сформулировать общее утверждение на этот счёт для всех позиционных систем счисления. В частности, для двоичной системы счисления все простые, кроме $2$, содержатся в прогрессии $2k+1$, для троичной — все, кроме $3$, в одной и прогрессий $3k+1$ и $3k-1$, для десятичной — все, кроме $2$ и $5$ — в одной из прогрессий $10k+1$, $10k-1$, $10k+3$ и $10k-3$. Ну и так далее. Я не вижу какого-либо особого свойства именно шестеричной системы счисления.
Я не угадал? Тогда изложите яснее.

[kazvadim]

Someone
Вы правы, всё так в системах счисления.
В профессионализме математиков уверен, а то мог бы провалить тему, не имея аргументов кроме предположений. Спасибо, немножко посмотрел на системы и убедился.

Количество простых палиндромов в позиционных системах счисления (п.с.с.) от $2$-0й до $10$-ой. Исходя из $9$-ти знаков для $10$-ой п.с.с. Простое число переводилось в другие п.с.с. и проверялось на палиндром. В скобках - п.с.с.
$3657(2), 2623(3), 4289(4), 3519(5), 2752(6), 3230(7), 2319(8), 3416(9), 5953(10)$...
Таким образом из рассмотренных п.с.с. лучше $10$-ая по количеству простых палиндромов. А, например, $6$-ая хуже (как бы она мне не нравилась).

[Someone]

Рассмотрим палиндромы в $m$-ичной системе счисления.
Число $n$-значных (натуральных) чисел в $m$-ичной системе счисления равно $(m-1)m^{n-1}$.
Простыми среди них могут быть только те, которые оканчиваются на цифру, взаимно простую с основанием системы счисления, поэтому число таких цифр равно $\varphi(m)$ (функция Эйлера). Исключениями являются только простые числа $p<m$, являющиеся делителями $m$ (для десятичной системы счисления это $2$ и $5$), и число $p=10_m=m$, если $m$ простое (индекс в записи числа указывает систему счисления; для десятичной системы индекс "$^{10}$" не указываем).
Далее мы будем рассматривать не менее чем трёхзначные числа, поэтому все $n$-значные простые числа находятся среди $N_m(n)=(m-1)m^{n-2}\varphi(m)$  $n$-значных чисел, оканчивающихся на цифры, взаимно простые с $m$ (для $m=10$ это цифры $1$, $3$, $7$ и $9$, так что $\varphi(10)=4$).
Число $2n$-значных и $2n-1$ значных палиндромов одинаково и равно $m^{n-1}(m-1)$.
Все чётно-значные палиндромы делятся на $11_m=m+1$, поэтому они все составные, кроме, может быть, палиндрома $11_m=m+1$, если число $m+1$ простое.
Ввиду сказанного, имеет смысл рассматривать только палиндромы, запись которых содержит нечётное количество цифр. Учитывая сделанное выше замечание о последних цифрах, имеет смысл рассматривать только те палиндромы, запись которых оканчивается на цифры, взаимно простые с $m$; число нечётно-значных палиндромов, оканчивающихся на цифры, взаимно простые с $m$, равно $Np_m(n)=m^{\frac{n-1}2}\varphi(m)$, где $n$ — нечётное число.

Далее рассматривается только десятичная система счисления. Количество простых палиндромов с заданных количеством цифр определяется непосредственной проверкой всех палиндромов рассматриваемой разрядности, количество всех простых чисел заданной разрядности вычисляется через функцию $\pi(x)$: число $n$-значных простых чисел равно $\pi(m^n-1)-\pi(m^{n-1}-1)$ (где $m=10$).
Вычисления сделаны для всех нечётных $n$, $3\leqslant n\leqslant 17$. Желающие могут продолжить вычисления дальше или проделать их для других систем счисления.

\begin{tabular}{|c|c|c|c|c|c|c|} \hline &\multicolumn{3}{|c|}{Палиндромы}&\multicolumn{3}{|c|}{$n$-значные числа}\\ \cline{2-7} $n$&Все на $1,3,7,9$&Простые&Плотность&Все на $1,3,7,9$&Простые&Плотность\\ \hline $3$&$4\cdot 10^1$&15&$0{,}375$&$36\cdot 10^1$&$143$&$0{,}397222$\\ \hline $5$&$4\cdot 10^2$&$93$&$0{,}2325$&$36\cdot 10^3$&$8363$&$0{,}232306$\\ \hline $7$&$4\cdot 10^3$&$668$&$0{,}167$&$36\cdot 10^5$&$586081$&$0{,}1628$\\ \hline $9$&$4\cdot 10^4$&$5172$&$0{,}1293$&$36\cdot 10^7$&$45086079$&$0{,}125239$\\ \hline $11$&$4\cdot 10^5$&$42042$&$0{,}105105$&$36\cdot 10^9$&$3663002302$&$0{,}10175$\\ \hline $13$&$4\cdot 10^6$&$353701$&$0{,}0884253$&$36\cdot 10^{11}$&$308457624821$&$0{,}0856827$\\ \hline $15$&$4\cdot 10^7$&$3036643$&$0{,}0759161$&$36\cdot 10^{13}$&$26639628671867$&$0{,}073999$\\ \hline $17$&$4\cdot 10^8$&$27045226$&$0{,}0676131$&$36\cdot 10^{15}$&$2344318816620308$&$0{,}06512$\\ \hline \end{tabular}

Рассматривая эту таблицу, можно увидеть, что, начиная с пятизначных, плотность простых чисел среди палиндромов чуть-чуть больше, чем среди всех чисел такой же разрядности. Что будет при увеличении разрядности, не ясно; пока предположим, что преимущество палиндромов будет и дальше возрастать. Однако доля простых палиндромов среди всех простых чисел определённой разрядности очень мала; например, для семнадцатизначных простых доля палиндромов составляет

$$\frac{27045226}{2344318816620308}\approx 1{,}15365\cdot 10^{-8}.$$

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

[Dmitriy40]

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

[kazvadim]

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

[kazvadim]

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

[kotenok gav]

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

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

Нетривиальными - нет, как уже говорил Andrey A на первой странице темы.

[kazvadim]

Исправляю свою ошибку. В предположении надо было написать «как минимум в одной из позиционных систем счисления», извините за рассеянность. На примере двухзначных простых чисел. В скобках – п.с.с.
$17(10)-10001(2), 31(10)-11111(2), 73(10)-1001001(2),$
$13(10)-111(3), 23(10)-212(3),$
$17(10)-101(4), 29(10)-131(4), 59(10)-323(4),$
$31(10)-111(5), 41(10)-131(5), 67(10)-232(5), 83(10)-313(5),$
$37(10)-101(6), 43(10)-111(6), 61(10)-141(6), 67(10)-151(6),$
$71(10)-131(7),$
$73(10)-111(8), 89(10)-131(8), 97(10)-141(8),$
$(9)$-нет простых палиндромов.
Числа, которые пока не поддались палиндромам в п.с.с. от $2$-ой до $9$-ой: $19, 47, 53, 79$.
Посмотрел бы в п.с.с. старше $10$-ой, но пока у меня не получается программа.
Наблюдение. Повторение комбинаций цифр в разных п.с.с.: $101$-$2$ раза, $111$-$4$ раза, $131$-$4$ раза, $141$-$2$ раза.

[kotenok gav]

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

В предположении надо было написать «как минимум в одной из позиционных систем счисления», извините за рассеянность.

Вы это и написали. Повторяю, существуют простые числа, не являющиеся нетривиальными палиндромами (т.е. теми, которые содержат больше одной цифры и не являются палиндромом $11$) во всех позиционных системах счисления.

[kazvadim]

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

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

В предположении надо было написать «как минимум в одной из позиционных систем счисления», извините за рассеянность.

Вы это и написали. Повторяю, существуют простые числа, не являющиеся нетривиальными палиндромами (т.е. теми, которые содержат больше одной цифры и не являются палиндромом $11$) во всех позиционных системах счисления.

Это не так. Утверждение верно!
Для всех натуральных чисел (кроме $1, 2$) (в том числе и для простых чисел (кроме $2$)) есть как минимум один простой палиндром $11$ в соответствующей позиционной системе счисления. Формула:
$n(n-1)=11$, где $n$-натуральное, в скобках-п.с.с.

[Mikhail_K]

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

есть как минимум один простой палиндром $11$

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

[kotenok gav]

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

в скобках-п.с.с.

Так не пишут. Ваша формула в общепринятых обозначениях записывается как $n=11_{n-1}$.