Простые числа и палиндромы : Математика (общие вопросы) - Страница 18 fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21  След.
 
 Re: Простые числа и палиндромы
Сообщение20.06.2021, 21:45 


15/11/20
179
Россия, Москва.
Someone в сообщении #1523586 писал(а):
kazvadim в сообщении #1523530 писал(а):
Поиск закономерности в таких палиндромах, которые рождают деревья простых чисел.
Я не помню, чтобы Вы продемонстрировали какую-нибудь закономерность, касающуюся простых палиндромов. Ну, не считая того, что простой палиндром не может содержать чётное количество цифр. Я что-нибудь забыл?
Можете ли Вы утверждать, что плотность простых чисел среди всех палиндромов больше, чем среди всех натуральных чисел, содержащих такое же количество цифр? А если исключить числа, делящиеся на хотя бы одно из чисел $2$ и $5$?
Можете ли Вы утверждать, что простые палиндромы порождают больше ветвей в обсуждаемом алгоритме, чем произвольные простые числа? И что в процессе палиндромы будут постоянно воспроизводиться достаточно часто, чтобы существенно влиять на весь процесс?
Ключевое слово = поиск. Разумеется, что простые палиндромы - это только подкласс простых чисел. Вы рассмотрели общий алгоритм - это отлично, палиндромы могут с маленькой вероятностью зацепиться за какие-нибудь веточки, если не обнаруживается ни одной такой веточки, то и будет закрыт вопрос о палиндромах. Закономерность в общем решении если и есть, то она будет сложной, а на палиндромах (частное решение) может что-то и удастся увидеть, как отросточек общей закономерности...

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


20/04/10
1889
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\}$ -- "коэффициенты размножения ветвей". Наблюдается рост, но смотреть дальше не хватает терпения -- долго.

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение20.06.2021, 23:24 


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

-- 21.06.2021, 00:08 --

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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение21.06.2021, 18:03 
Заслуженный участник
Аватара пользователя


23/07/05
17988
Москва
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$. Ну и так далее. Я не вижу какого-либо особого свойства именно шестеричной системы счисления.
Я не угадал? Тогда изложите яснее.

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


15/11/20
179
Россия, Москва.
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$-ая хуже (как бы она мне не нравилась).

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение22.06.2021, 23:56 
Заслуженный участник
Аватара пользователя


23/07/05
17988
Москва
Рассмотрим палиндромы в $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}.$$ То есть, это весьма специфические простые числа, особенность которых не имеет смысла за пределами определённого способа записи, и потому может быть любопытной для любителей математики, но малоинтересна для самой математики.

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


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

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


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

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


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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение23.06.2021, 09:28 


21/05/16
4292
Аделаида
kazvadim в сообщении #1523891 писал(а):
Предположение: все простые числа представимы палиндромами, как минимум в одной из позиционных систем счисления.

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

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


15/11/20
179
Россия, Москва.
Исправляю свою ошибку. В предположении надо было написать «как минимум в одной из позиционных систем счисления», извините за рассеянность. На примере двухзначных простых чисел. В скобках – п.с.с.
$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$ раза.

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


21/05/16
4292
Аделаида
kazvadim в сообщении #1523963 писал(а):
В предположении надо было написать «как минимум в одной из позиционных систем счисления», извините за рассеянность.

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

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


15/11/20
179
Россия, Москва.
kotenok gav в сообщении #1523974 писал(а):
kazvadim в сообщении #1523963 писал(а):
В предположении надо было написать «как минимум в одной из позиционных систем счисления», извините за рассеянность.

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

 Профиль  
                  
 
 Re: Простые числа и палиндромы
Сообщение23.06.2021, 17:06 
Заслуженный участник
Аватара пользователя


26/01/14
4855
kazvadim в сообщении #1523981 писал(а):
есть как минимум один простой палиндром $11$
Внимательно прочитайте цитату, на которую Вы отвечаете. Там 11 назван "тривиальным палиндромом" и утверждается, что есть простые числа, не являющиеся нетривиальными палиндромами. Что любое натуральное число больше двух представимо в виде тривиального палиндрома, с этим никто не спорит.

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


21/05/16
4292
Аделаида
kazvadim в сообщении #1523981 писал(а):
в скобках-п.с.с.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 301 ]  На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20, 21  След.

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



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

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


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

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