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

[kazvadim]

Dmitriy40
Основное это было связать простые палиндромы с простыми близнецами. Ну и дополнительно - это простые палиндромы от $5$ до $35$ нечётных знаков, которые состоят из простых близнецов, а не все подряд.

-- 02.07.2021, 14:45 --

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

Весь набор формул - 'это для получения простых палиндромов от $5$-ти до $8$-и знаков.

Извините (рассеянность). Правильно. Весь набор формул - 'это для получения простых палиндромов от $5$-ти до $35$-ти знаков.

[Dmitriy40]

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

Основное это было связать простые палиндромы с простыми близнецами.

Аналогия: Вы связали натуральные числа с рациональными (не в обратную сторону! именно так). Т.е. взяли все простые палиндромы и выделили из них очень узкий класс подходящих под ваши формулы. Правда ли это? Да, правда, связали. Есть ли польза? Нет, не видно. Формулы никак не помогают из всех палиндромов выделить простые палиндромы, или продолжая аналогию из всех рациональных выделить натуральные. Процентное содержание простых палиндромов в ваших формулах практически совпадает с процентным содержанием простых палиндромов среди всех палиндромов. Простыми словами, ваши формулы ничем не помогают найти простые палиндромы среди любых палиндромов.
Ещё более простыми словами: среди простых чисел есть с младшей 1. Есть? Да, есть. Связали простые с младшей 1 с вообще числами? Да, связали. Польза от этого есть? Нет. Потому что по младшей 1 нельзя сказать простое число или нет. Вы сделали ровно то же самое.

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

[kazvadim]

Dmitriy40
Вы всё правильно говорите и о процентной составляющей простых палиндромов, и об отсутствии общей и универсальной формулы. Но мне представляется проще и быстрее вычислить простой 35-значный палиндром, составленный из простых близнецов, перебрав $300$ комбинаций вставок, чем молотить все $35$-значные простые палиндромы и проверять их состав на предмет заданных простых близнецов. Комбинаций меньше (посмотрю mod3).
По поводу скорости вычислений. $381315$ простых палиндромов, составленных из $8$-значных простых близнецов, вычисляются на моём очень старом компьютере и медленной программой где-то $20$ минут. На современном компьютере и хорошей программой эти вычисления будут в разы быстрее.

[Dmitriy40]

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

Но мне представляется проще и быстрее вычислить простой 35-значный палиндром, составленный из простых близнецов, перебрав $300$ комбинаций вставок, чем молотить все $35$-значные простые палиндромы и проверять их состав на предмет заданных простых близнецов.

Как раз это и неправда, все палиндромы перебирать не придётся, простой встретится в среднем пусть через те же 300 проверок. Я же (и Someone) это прямо проверяли! Всё так и есть. Что перебрать 300 вариантов по вашим формулам и найти один простой, что перебрать примерно 300 просто палиндромов и найти простой. Из-за одинаковой вероятности, с чем Вы вроде и согласились, но тут же снова противоречите. Ну как так можно то ... Вы своими словами прямо иллюстрируете что не понимаете о чём говорите. Или слишком туманно выражаетесь.
Одинаково по времени ещё и потому что сами вставки и генерация палиндромов намного быстрее проверки его на простоту. Т.е. почти без разницы как генерить палиндром, хоть по вашим формулам, хоть по другим. И время зависит практически только от количества проверенных палиндромов (по любым формулам) до нахождения простого. А это количество практически одинаково что по вашим формулам, что просто все палиндромы. Пока речь идёт о нахождении первого же простого палиндрома, в принципе задача может быть и другой (например найти 400 простых 35-значных палиндрома, ваши формулы вообще не справятся по вашим словам).

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

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

Но и все другие вычисления будут ровно в те же разы быстрее! А значит только от этого никакого выигрыша не появится. Это вообще банальность. Зачем Вы не в первый раз её упоминаете ... Сами показываете своё недопонимание.

[kazvadim]

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

Как раз это и неправда, все палиндромы перебирать не придётся, простой встретится в среднем пусть через те же 300 проверок. Я же (и Someone) это прямо проверяли! Всё так и есть. Что перебрать 300 вариантов по вашим формулам и найти один простой, что перебрать примерно 300 просто палиндромов и найти простой..

Уфф... Не могу никак объяснить который раз. Тот простой палиндром, который Вы найдёте придется проверять из каких чисел он состоит. Если он никак не состоит из простых близнецов, то он, хоть и простой палиндром, но ничем не помогает в нашей задаче. Далее ищете следующий, следующий, ... проверяете, проверяете, ... пока не найдёте тот простой палиндром, который будет состоять из простых близнецов. Не думаю, что это будет быстрее, чем проверить на простоту до трёхсот палиндромов уже составленных из простых близнецов. Причём, первая формула из (3) находит около 90% положительных решений (до 100 проверок палиндрома), вторая добивает те палиндромы, с которыми не справилась первая, третья подбирает палиндромы, оставшиеся после второй. Извините, я, конечно, очень невнятно объясняю, но я стараюсь.

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

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

Не интересен в этой задаче просто простой палиндром, а интересен только тот, который составлен из простых близнецов.

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

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

Смотря каких простых палиндромов. Эти формулы для палиндромов, построенных из близнецов. К другим палиндромам они не имеют ни какого отношения. Для простых близнецов, начинающихся на цифры 1,3,7,9 , эти формулы вычисляют 381315 35-значных простых палиндромов, составленных из простых близнецов (для всех 8-значных простых близнецов за исключением 17-ти).

[Dmitriy40]

kazvadim
Разумеется если искать только простые палиндромы именно из простых близнецов, то надо пользоваться вашими формулами (или похожими) и не перебирать все палиндромы.
Но похоже задача в такой формулировке мало кому интересна ...

[Someone]

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

Не могу никак объяснить который раз. Тот простой палиндром, который Вы найдёте придется проверять из каких чисел он состоит. Если он никак не состоит из простых близнецов, то он, хоть и простой палиндром, но ничем не помогает в нашей задаче. Далее ищете следующий, следующий, ... проверяете, проверяете, ... пока не найдёте тот простой палиндром, который будет состоять из простых близнецов.

Хм. У меня всё время было впечатление, что Вы ищете любые простые палиндромы, и Вы почему-то убеждены, что их проще получать, используя пары простых близнецов. И, похоже, Dmitriy40 пребывал в том же заблуждении.

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

вычислить простой 35-значный палиндром, составленный из простых близнецов, перебрав $300$ комбинаций вставок

$300$ попыток на один $35$-значный палиндром? Что-то многовато. Плотность простых чисел в районе $10^{35}$ равна примерно $\frac 1{\ln 10^{35}}=\frac 1{35\ln 10}$. Учитывая, что заранее отброшены все числа, кратные $2$ или $5$, плотность простых среди оставшихся нужно умножить на $2{,}5$, и получится $\frac{2{,}5}{35\ln 10}=\frac 1{14\ln 10}$. Плотность простых среди палиндромов, начинающихся (и оканчивающихся) на цифры $1,3,7,9$, должна быть примерно такой же, поэтому на один простой палиндром должно тратиться в среднем примерно $14\ln 10\approx 32{,}2362$ попытки. Эта оценка должна быть немного завышенной, так как относится к верхней границе множества $35$-значных чисел.
Я проделал численный эксперимент, вычислив $381\,315$ случайных простых $35$-значных простых палиндромов. Процессор двухъядерный, тактовая частота $2{,}4$ GHz, используется система компьютерной математики Wolfram Mathematica 11.3.
Палиндромы генерируются командами
$\mathrm{Lst = Append[RandomChoice[Range[0, 9], 17], RandomChoice[\{1,3,7,9\}]];}$
$\mathrm{Lst = Join[Reverse[Delete[Lst, 1]], Lst];}$
$\mathrm{p = FromDigits[Lst];}$
Далее построенный палиндром проверяется на простоту, подсчитывается количество сгенерированных палиндромов и количество простых среди них.
В итоге для получения $381\,315$ простых потребовалось проверить $11\,887\,270$ палиндромов, то есть, в среднем $\frac{11\,887\,270}{381\,315}\approx 31{,}1744$ проверок на один простой палиндром.
Затраты времени составили $729{,}585$ секунды.
Последний найденный простой палиндром равен $91\,305\,982\,163\,813\,568\,886\,531\,836\,128\,950\,319$.

[kazvadim]

Someone
Спасибо, полезная информация.

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

Последний найденный простой палиндром равен $91\,305\,982\,163\,813\,568\,886\,531\,836\,128\,950\,319$.

Последний $35$-значный простой палиндром из простых близнецов $(99999539, 99999541)$: $99999539\,6\,14599999\,1\,99999541\,6\,93599999$

[Someone]

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

Последний $35$-значный простой палиндром из простых близнецов…

Ну, у меня "последний" означает "сгенерированный последним", а не "самый большой". Простые палиндромы генерировались в случайном порядке. Например:
$p = 33\,591\,578\,014\,362\,818\,481\,826\,341\,087\,519\,533$, число попыток $= 33$
$p = 75\,293\,303\,113\,433\,584\,848\,533\,431\,130\,339\,257$, число попыток $= 47$
$p = 92\,919\,246\,822\,894\,319\,391\,349\,822\,864\,291\,929$, число попыток $= 54$
$p = 78\,089\,748\,453\,173\,346\,164\,337\,135\,484\,798\,087$, число попыток $= 55$
$p = 70\,648\,093\,909\,272\,474\,847\,427\,290\,939\,084\,607$, число попыток $= 99$
$p = 71\,070\,222\,244\,311\,978\,887\,911\,344\,222\,207\,017$, число попыток $= 102$
$p = 39\,257\,405\,957\,280\,215\,051\,208\,275\,950\,475\,293$, число попыток $= 111$
$p = 17\,428\,869\,736\,994\,566\,366\,549\,963\,796\,882\,471$, число попыток $= 170$
$p = 13\,040\,959\,395\,374\,872\,227\,847\,359\,395\,904\,031$, число попыток $= 173$
$p = 34\,230\,970\,866\,973\,386\,168\,337\,966\,807\,903\,243$, число попыток $= 210$
$\vdots$
$p = 92\,211\,485\,471\,626\,055\,755\,062\,617\,458\,411\,229$, число попыток $= 2\,817$
$p = 38\,051\,191\,759\,006\,122\,522\,160\,095\,719\,115\,083$, число попыток $= 2\,847$
$p = 32\,411\,785\,226\,633\,419\,891\,433\,662\,258\,711\,423$, число попыток $= 2\,853$
$p = 79\,875\,514\,556\,075\,558\,985\,557\,065\,541\,557\,897$, число попыток $= 2\,894$
$p = 93\,740\,428\,917\,216\,890\,709\,861\,271\,982\,404\,739$, число попыток $= 2\,912$
$p = 39\,804\,364\,243\,771\,983\,138\,917\,734\,246\,340\,893$, число попыток $= 2\,933$
$p = 94\,775\,334\,435\,939\,598\,389\,593\,953\,443\,357\,749$, число попыток $= 2\,970$
$p = 73\,935\,698\,885\,526\,905\,350\,962\,558\,889\,653\,937$, число попыток $= 2\,987$
$p = 38\,843\,274\,560\,691\,893\,939\,819\,606\,547\,234\,883$, число попыток $= 3\,038$
$p = 76\,993\,418\,824\,470\,140\,304\,107\,442\,881\,439\,967$, число попыток $= 3\,042$
Всего в этом списке было сгенерировано $100$ простых палиндромов, на что было затрачено $3\,042$ попытки, то есть, в среднем $30{,}42$ попытки на один простой палиндром.

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

эти формулы вычисляют 381315 35-значных простых палиндромов, составленных из простых близнецов (для всех 8-значных простых близнецов за исключением 17-ти).

Ну, не много. Количество $35$-значных палиндромов, оканчивающихся на цифры $1,3,7,9$, равно $4\cdot 10^{17}$, плотность простых среди них можно оценить величиной $\frac 1{14\ln 10}$, поэтому число $35$-значных простых палиндромов можно оценить величиной $\frac{4\cdot 10^{17}}{14\ln 10}\approx 1{,}24\cdot 10^{16}$.

[Someone]

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

Вычисления сделаны для всех нечётных $n$, $3\leqslant n\leqslant 17$. Желающие могут продолжить вычисления дальше или проделать их для других систем счисления.

Продолжать эти вычисления не собирался, но потом всё-таки запустил вычисления для $19$-значных чисел. Результаты следующие.
Количество $19$-значных палиндромов, оканчивающихся на $1,3,7,9$, равно $4\cdot 10^9$.
Среди них простых — $239\,093\,865$.
Доля простых среди палиндромов равна $0{,}0597735$.
Количество $19$-значных чисел, оканчивающихся на $1,3,7,9$, равно $36\cdot 10^{17}$.
Среди них простых — $209\,317\,712\,988\,603\,747$.
Доля простых равна $0{,}0581438$.
Вычисления заняли $77\,200$ секунд.

Дополнительно подсчитал отношения доли простых палиндромов к доле всех простых данной разрядности (для $19$-значных это $\left(\frac{239\,093\,865}{4\cdot 10^9}\right)/\left(\frac{209\,317\,712\,988\,603\,747}{36\cdot 10^{17}}\right)\approx\frac{0{,}0597735}{0{,}0581438}\approx 1{,}02803$).

\begin{tabular}{|c|c|} \hline n&Отношение\\ \hline $3$&$0{,}944056$\\ \hline $5$&$1{,}00084$\\ \hline $7$&$1{,}0258$\\ \hline $9$&$1{,}03243$\\ \hline $11$&$1{,}03297$\\ \hline $13$&$1{,}03201$\\ \hline $15$&$1{,}02591$\\ \hline $17$&$1{,}03828$\\ \hline $19$&$1{,}02803$\\ \hline \end{tabular}

[kazvadim]

Someone
Спасибо!
А вот я ошибся и по поводу количества простых палиндромов из простых близнецов (их значительно больше), и по поводу самого большого $35$-значного. Самые большие:
$35$ знаков - $99999899599900001910000999599899999, (99999899,99900001)$;
$39$ знаков - $999999916579999991666199999975619999999, (619999997,619999999)$;
$43$ знака - $9999999862926899999972799999986292689999999, (2689999997,2689999999)$.

[Someone]

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

$35$ знаков - $99999899599900001910000999599899999, (99999899,99900001)$;

Какие-то странные у Вас близнецы…

[kazvadim]

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

Какие-то странные у Вас близнецы…

Вот такие получились. У этого палиндрома старшие цифры $999998$ (он один такой). Встречаются палиндромы, начинающиеся на $999997, 999996$,..., но они, конечно, меньше. А палиндрома на $999999$ нет.

[Someone]

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

Вот такие получились.

Вы разность-то между ними посчитайте: $99999899-99900001$.

[kazvadim]

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

Вы разность-то между ними посчитайте: $99999899-99900001$.

Эти мои поспешность, невнимательность, рассеянность до добра не доведут. Ну, конечно, я написал перевёрнутое число, как оно входило в формулу. Должно быть так: $99899999,99900001$. Спасибо.