2014 dxdy logo

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

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




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


16/08/19
103
grizzly в сообщении #1522274 писал(а):
Даже если разрешить всякий раз вставлять цифру (или не более фиксированного числа цифр) на любые позиции, процесс получения новых простых очень быстро закончится :)


Позволю не согласиться с вами
По-моему, каждый раз при увеличении разрядности число вариантов вставки возрастает как минимум на два порядка
Ваш алгоритм не строгий, я не пробовал его реализовать, но мне кажется, он даст гораздо более длинные последовательности
Дело в том, что не имеет особого значения, на какую позицию вставлять
Например , если взять исходное простое число 75972593 и начинать вставлять в конец, между 9 и 3, то получается последовательность
7597259 + 32724230162366361339669 + 3, или :
759725933,
7597259323,
...

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


09/09/14
6328
mathpath в сообщении #1522317 писал(а):
По-моему, каждый раз при увеличении разрядности число вариантов вставки возрастает как минимум на два порядка
Любопытно оно выглядит по-Вашему. Но, боюсь, Вы ошиблись на пару порядков :)
mathpath в сообщении #1522317 писал(а):
Ваш алгоритм не строгий
В каком смысле?
mathpath в сообщении #1522317 писал(а):
мне кажется, он даст гораздо более длинные последовательности
Чуть более длинные, конечно. Я не спорю.

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


23/07/05
17973
Москва
mathpath, разумеется, при увеличении количества вариантов вставки шанс на построение длинной последовательности простых чисел растёт. Например, если мы будем вставлять одну цифру ($1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ или $9$) впереди записи числа и одну цифру ($1$, $3$, $7$ или $9$) позади, то, начиная с простого числа $2$, можно добраться до $89$-значного числа
$28\,653\,986\,512\,599\,224\,126\,837\,727\,956\,373\,223\,223\,982\,112\,239\,771\,911\,791\,731\,191\,911\,919\,173\,971\,137\,913\\913\,799\,377,$
а если начать с последовательности $02$ (что выглядит, конечно, весьма искусственно), то сможем дойти до $94$-значного числа
$7\,736\,891\,492\,553\,529\,192\,988\,698\,484\,137\,788\,839\,531\,856\,154\,027\,199\,117\,313\,777\,997\,997\,739\,137\,139\,119\\713\,771\,397\,793\,773.$

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


16/08/19
103
Алгоритм grizzly, если я правильно его понял, заключается в том, что мы проверяем ВСЕ разряды в исходном числе,
и если при вставке на один из этих разрядов одной из 10 цифр получается простое число, то итерация продолжается
Пример:
Имеется исходное простое число 7949
Имеется массив : ["2:3", "4:3", "5:6", "6:5", "7:1", "8:2", "9:6", "10:6", "11:7", "12:3", "13:9", "12:9", "13:2", "16:1", "16:8", "17:9", "19:4", "18:3", "14:2", "21:7", "15:2", "20:0", "23:1", "21:0", "21:5", "28:1", "27:9", "24:5", "31:3", "31:4", "31:2", "34:3", "31:6", "29:1", "28:3", "38:3", "28:5", "40:0", "40:6", "41:1", "39:2", "35:1", "45:8", "41:1", "44:5", "47:7", "43:8", "44:1", "47:0", "44:5", "45:0", "52:4", "53:3", "52:9", "50:5", "34:9", "53:3", "59:6", "53:4", "52:5", "57:7", "61:8", "61:4", "52:2", "59:3", "67:9", "62:0", "67:4", "68:2", "69:4", "71:0", "56:6", "74:0", "68:2", "68:3", "69:6", "75:6", "78:7", "73:9", "73:3", "83:0", "84:6", "67:2", "61:0", "86:9", "70:7", "84:3", "90:8", "73:9", "47:6", "92:9", "93:4", "93:6", "91:8", "97:0", "83:1", "97:5", "92:3", "86:4", "94:2"]
Первая итерация: берем первый элемент массива - "2:3", это значит , что на позицию 2 ставим 3, получаем 79349 - простое
Вторая итерация: 79349 -> 793439 - простое
И т.д.
Я привел только первые сто элементов этого массива, а он практически бесконечен ...

Где-то через минут пять после старта я добираюсь до 1000-значного простого числа

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


09/09/14
6328
mathpath в сообщении #1522375 писал(а):
Я привел только первые сто элементов этого массива, а он практически бесконечен
Да, всё верно, вероятность на Вашей стороне. Это я про что-то не то думал, сорри.

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

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


16/08/19
103
grizzly в сообщении #1522382 писал(а):
Теперь любопытно, доказуемо ли, что по таким правилам можно построить хоть одну бесконечную последовательность простых.


Чисто интуитивно - да, конечно
Я смотрю, как в соответствии с моим алгоритмом ищется подходящий разряд для вставки
Алгоритм построен на том, что проверка идет от самых младших разрядов к старшим
И по статистике я вижу, что при росте разрядности искомый разряд лежит практически всегда в правой половине числа и никогда не добирается даже до середины числа

Жаль,я программист, а не математик

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


20/08/14
11065
Россия, Москва
Скорее можно попытаться доказать что нет такого простого, которое нельзя расширить до большего простого.
Рассмотрим простое число из миллиона цифр. Для него существует (примерно) 10млн вариантов расширения. И чтобы все эти 10млн чисел были составными желательно чтобы средняя плотность простых в этом диапазоне была сильно менее одной десятимиллионной, а это явно не так, $1/\ln(10^{1000000}) \approx 1/2.3\cdot10^{6}>1/10^7$.

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


23/07/05
17973
Москва
mathpath в сообщении #1522375 писал(а):
Алгоритм grizzly, если я правильно его понял, заключается в том, что мы проверяем ВСЕ разряды в исходном числе,
и если при вставке на один из этих разрядов одной из 10 цифр получается простое число, то итерация продолжается
Да, разумеется. Я разницу вижу. Я пока рассматривал случай, когда количество вариантов вставок ограничено некоторой величиной. Но можно рассмотреть и алгоритм grizzly.

Заранее предупреждаю, что последующее рассуждение не использует аккуратных оценок и основано только на асимптотике, поэтому рассматривать его как строгое доказательство не следует.

Как известно, плотность множества простых чисел в окрестности большого натурального числа $x$ имеет асимптотику $\frac 1{\ln x}$.
Если десятичная запись простого числа $x$ содержит $n$ цифр, то $10^{n-1}<x<10^n$, а число $x'$, полученное расширением числа $x$ одной цифрой (неважно, куда вставленной), удовлетворяет неравенству $10^n<x'<10^{n+1}$, поэтому $\frac 1{\ln x'}<\frac 1{n\ln 10}$.
Для вставки перед первой цифрой имеется $9$ вариантов (первая цифра не должна быть $0$), для вставки после последней цифры разумными являются только $4$ варианта ($1$, $3$, $7$, $9$), так как в остальных случаях получается составное число, которое делится на $2$ или на $5$. Так как таким образом отсекаются все числа, делящиеся на $2$ или на $5$, то плотность простых чисел среди оставшихся увеличивается в $\frac 21\cdot\frac 54=2{,}5$ раза и оценивается теперь величиной $\frac{2{,}5}{n\ln 10}$ ("асимптотически сверху").
По этой причине вероятность того, что конкретная вставка даст составное число, можно оценить ("асимптотически снизу") величиной $1-\frac{2{,}5}{n\ln 10}$.
Число возможных вставок в методе grizzly равно $9+10(n-1)+4=10n+3$, поэтому можно ожидать, что вероятность того, что все вставки дадут составное число, "асимптотически больше", чем $$f(n)=\left(1-\frac{2{,}5}{n\ln 10}\right)^{10n+3}.$$
Можно проверить, что функция $f(n)$ возрастает при $n\geqslant 2$, и что $$\lim_{n\to\infty}f(n)=\exp\left(-\frac{25}{\ln 10}\right)=1{,}9262\ldots\cdot 10^{-5}.$$
(24/VI-2021 исправил опечатку в этой формуле.)
В частности, при $n\geqslant 669$ будет $f(n)>1{,}9\cdot 10^{-5}$, а вероятность того, что хотя бы одна вставка из $10n+3$ возможных даст простое число, будет "асимптотически меньше" $1-1{,}9\cdot 10^{-5}$. Соответственно, вероятность того, что, начиная с не менее чем $n\geqslant 669$-значного простого числа, нам удастся продлить цепочку простых чисел не менее чем на $k$ шагов, будет "асимптотически меньше" $$(1-1{,}9\cdot 10^{-5})^k\xrightarrow[k\to\infty]{}0.$$
Таким образом, каждая конкретная цепочка вставок обрывается с вероятностью $1$. Это, однако, не доказывает невозможность бесконечной цепочки вставок, дающих простые числа, а также не доказывает, что, начав с некоторого простого (или составного) числа, невозможно найти сколь угодно длинные цепочки вставок, дающих простые числа.

Я далеко не специалист в теории чисел, поэтому подробнее вдаваться в это дело не буду.

mathpath в сообщении #1522375 писал(а):
Где-то через минут пять после старта я добираюсь до 1000-значного простого числа
Судя по полученной оценке вероятности существования успешной вставки, Вам следует продлить свой эксперимент до чисел, содержащих хотя бы сотню тысяч цифр, а может быть и больше. Но тут уже, вероятно, придётся использовать не математические пакеты, а специализированные программы, умеющие эффективно выполнять тест с помощью теоремы Ферма. Например, OpenPFGW. И придётся написать для неё скрипт, автоматизирующий поиск вставок и сохраняющий некоторые промежуточные результаты, достаточные для возобновления расчётов в случае прерывания вычислений. Но даже и здесь вычисления могут потребовать чрезвычайно много времени.

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


16/08/19
103
Someone в сообщении #1522418 писал(а):
mathpath в сообщении #1522375 писал(а):
Где-то через минут пять после старта я добираюсь до 1000-значного простого числа
Судя по полученной оценке вероятности существования успешной вставки, Вам следует продлить свой эксперимент до чисел, содержащих хотя бы сотню тысяч цифр, а может быть и больше. Но тут уже, вероятно, придётся использовать не математические пакеты, а специализированные программы, умеющие эффективно выполнять тест с помощью теоремы Ферма. Например, OpenPFGW. И придётся написать для неё скрипт, автоматизирующий поиск вставок и сохраняющий некоторые промежуточные результаты, достаточные для возобновления расчётов в случае прерывания вычислений. Но даже и здесь вычисления могут потребовать чрезвычайно много времени.


Да, суровый у вас анализ, и я не знаю, к чему можно придраться

Я бы гипотезу, сформулированную выше grizzly, сформулировал бы так:
Существует бесконечно много простых чисел, с помощью которых можно сформировать бесконечно длинные последовательности

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

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

Если рассмотреть алгоритм формирования данной последовательности, то можно сказать, что он линейно не детерминирован
Что это значит ?
В начале алгоритма, когда мы начинаем вставлять число в какую-то позицию, может оказаться, что мы получим более одного варианта
И уже в самом начале на свет появляется дерево вариантов
Это дерево обладает бесконечной глубиной
Написать разумный алгоритм прохода по этому дереву не представляется возможным в силу ограниченности ресурсов
Мы просто случайным образом выбираем один из вариантов и двигаемся по нему вниз, игнорируя бесконечное количество других вариантов

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


20/04/10
1776
Поскольку на каждом шаге в среднем имеется $25/\ln{10}$ "простых продолжений". То дерево разрастается экспоненциально и пусть даже на некотором шаге часть ветвей не будет иметь "простых продолжений", таких ветвей будет меньшая часть, так как вероятность гибели ветви, как показал Someone невелика. Таким образом, если дерево начало расти, то почти наверняка оно не погибнет.

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


23/07/05
17973
Москва
mathpath в сообщении #1522425 писал(а):
Да, суровый у вас анализ, и я не знаю, к чему можно придраться
Ну, я, как профессиональный математик, понимаю, к чему можно придраться, да и другие специалисты на нашем форуме тоже понимают. Рассматривайте этот анализ как правдоподобное рассуждение; может быть, кто-нибудь из специалистов по теории чисел сделает необходимые уточнения.

mathpath в сообщении #1522425 писал(а):
Я бы гипотезу, сформулированную выше grizzly, сформулировал бы так:
Существует бесконечно много простых чисел, с помощью которых можно сформировать бесконечно длинные последовательности
Я продолжу свой комментарий.

Как мы видели, вероятность того, что число $x'$, полученное из $x$ вставкой одной цифры, окажется простым, лежит примерно между $\frac{2{,}5}{(n+1)\ln 10}$ и $\frac{2{,}5}{n\ln 10}$. Вариантов вставок у нас $10n+3$, поэтому среднее число удачных вставок, дающих простые числа, "асимптотически равно" $$\frac{2{,}5(10n+3)}{n\ln 10}\xrightarrow[n\to\infty]{}\frac{25}{\ln10}=10{,}857362\ldots,$$ то есть, дерево вставок должно сильно ветвиться. Из-за этого вероятность обрыва всех цепей с ростом высоты дерева очень быстро стремится к нулю (грубо говоря, как $\left(1{,}9\cdot 10^{-5}\right)^{10^k}$, где $k$ — номер уровня в дереве, считая исходное число нулевым уровнем). Поэтому вымирание всех ветвей должно быть большой редкостью, и мало шансов обнаружить такое дерево, содержащее больше одного-двух-трёх уровней, считая и нулевой уровень (это чисто эмоциональное суждение). Вот и lel0lel о том же пишет.

С другой стороны, как мы видели, каждая конкретная цепь обрывается с вероятностью $1$. Тем не менее, бесконечные цепи обязательно должны существовать: бесконечное дерево, у которого все уровни конечные, обязано иметь хотя бы одну бесконечную цепь. А у нас число элементов на $k$-м уровне можно оценить сверху величиной $$\prod_{j=0}^{k-1}(10(n+j)+3).$$ Но бесконечные цепи в совокупности образуют множество нулевой вероятности. И я не представляю, как можно было бы указать конкретную бесконечную цепь.

mathpath в сообщении #1522425 писал(а):
Я не пользуюсь специализированными математическими пакетами в силу того, что я программист, и использую популярные языки программирования
Простые числа длиной более 1000 знаков на современном железе плохо поддаются обработке, а работа с простыми числами в сотню тысяч знаков практически нереальна. Для этого нужны какие-то специальные вычислительные мощности.
Ну, есть стандартные библиотеки для работы с больши́ми числами: GMP, NTL и другие. GMP позиционируется как одна из наиболее быстрых из широко доступных библиотек, а NTL, как мне показалось, имеет более удобный интерфейс, но считает существенно медленнее. Однако её можно откомпилировать так, чтобы она для вычислений использовала GMP, и тогда вычисления сильно ускоряются (насколько я помню, я с этим однажды экспериментировал, и получил ускорение в несколько раз). NTL я компилировал просто в C++Builder, а для компиляции GMP пришлось установить MSYS/MinGW. При этом сначала долго тестировались возможности процессора, и только потом пошла собственно компиляция, которая заняла массу времени.
Что касается упомянутой прошлый раз программы OpenPFGW, то она предназначена для поиска очень больших простых чисел специальных видов, и для умножения длинных чисел в тестах использует какой-то особо эффективный вариант БПФ (быстрое преобразование Фурье).

Советую посмотреть список "5000 самых больших известных простых чисел" вот здесь: https://primes.utm.edu/. Самое большое моё простое число равно $4\,294\,967\,295\cdot 2^{1\,002\,700}-1$, оно уже слишком маленькое, чтобы находиться в этом списке. Найдено оно было на домашнем компьютере с помощью программы OpenPFGW.

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


16/08/19
103
Сейчас все, так или иначе, пользуются методом Миллера-Рабина - он же метод Ферма - проверки числа на простоту, независимо от используемого математического пакета или языка программирования
Время работы метода Миллера-Рабина пропорционально логарифму в кубе от самого числа, т.е. полиномиально
Его можно использовать для проверки одного очень большого числа
Но его нельзя использовать для массовой работы с большими числами

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


23/07/05
17973
Москва
Проделал некоторый численный эксперимент с алгоритмом grizzly (начальное число простое; на каждом шаге в простое число вставляется одна цифра в любую позицию так, чтобы получилось снова простое число). Именно, проверил первые $100\,000$ простых чисел ($p_{100\,000}=1\,299\,709$). Результаты следующие.

1) Нашлось ровно одно число, все вставки в которое дают составное число, то есть, на этом числе цепочка простых чисел обрывается: $p_{31\,478}=369293$. От однозначных простых чисел к этому числу ведут $6$ цепочек, начинающихся с однозначного простого числа.
$$\xymatrix{3\ar[r]&23\ar[r]&293\ar[r]&9\,293\ar[r]&39\,293\ar[rd]\\
2\ar[ru]\ar[r]&29\ar[ru]\ar[r]&929\ar[ru]\ar[r]&3\,929\ar[ru]\ar[r]&36\,929\ar[r]&369\,293}$$

2) В рассмотренном диапазоне наибольшее число ветвей ($23$) получается для числа $p_{89\,638}=1\,154\,603$: $11\,534\,603$, $11\,543\,603$, $11\,545\,603$, $11\,546\,033$, $11\,546\,063$, $11\,546\,083$, $11\,546\,203$, $11\,546\,503$, $11\,546\,603$, $11\,546\,803$, $11\,546\,903$, $11\,564\,603$, $11\,584\,603$, $11\,594\,603$, $11\,654\,603$, $11\,854\,603$, $11\,954\,603$, $15\,154\,603$, $16\,154\,603$, $18\,154\,603$, $21\,154\,603$, $31\,154\,603$, $51\,154\,603$ (числа отсортированы по возрастанию). К этому числу ведут $3$ цепочки.
$$\xymatrix{3\ar[r]&13\ar[r]\ar[rd]&103\ar[r]&1103\ar[r]&11503\ar[r]&115603\ar[r]&1154603\\
&&113\ar[ru]\ar[r]&1153\ar[ru]}$$

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


16/08/19
103
Someone в сообщении #1522954 писал(а):

1) Нашлось ровно одно число, все вставки в которое дают составное число, то есть, на этом числе цепочка простых чисел обрывается: $p_{31\,478}=369293$.


Как интересно !
Я почему-то был уверен, что хотя бы одно такое число найдется
Дальше вероятность появления еще одного такого числа будет стремиться к нулю

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


20/08/14
11065
Россия, Москва
Всё уже добыто до нас: A125001. 3000 примеров ...

Кстати число вставок прилично завышено:
Someone в сообщении #1522418 писал(а):
Число возможных вставок в методе grizzly равно $9+10(n-1)+4=10n+3$,
Их будет точно не выше чем $6+7(n-1)+4$, а в среднем даже ещё на 1 меньше. Потому что в каждую позицию ровно три числа вставить не получится, те что дополняют число до кратного трём. А для младшей позиции вероятность для 1 и 7 по той же причине будет 0.5. Ну и наверное ещё ограничений можно наложить.

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

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



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

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


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

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