Последовательность Петрова - вероятность распределения п. ч.

[uzlprog]

Всем доброй пятницы! Очередной пятничный тред (если я не опоздал с темой - но вроде бы такой не нашел).

Так как некоторые уверенны в том, что я и есть г-н Петров И. (Иваном) Б. , то не стану их разочаровывать и выложу информацию по очередной свежей (увы, уже нет...) статьи [Петров И. Б. "Квазиэкспоненциальные простые числа", СИ, 2021 год], где автор предложил для поиска больших простых чисел рассмотреть последовательность чисел вида $a^a-a-1$, где $a > 2$, $a$ - любое натуральное число. Сам автор факторизовал результат вычисления формулы до $a = 5000$ и обнаружил, что простые числа будут при $a = 3, 4, 5, 6, 9, 17, 22, 85, 710, 844, 1379.$. Это все что есть в статье.

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

Сама идея для поиска простых чисел использовать такую последовательность весьма интересна (может кому-то будет полезна), так как мне не приходилось видеть подобное. И кое-где в сети нашлись желающие для факторизации чисел последовательности до $a = 100 000$ (но понятно, что вычислительных силенок им хватило только до $a = 10 000$, я попробовал факторизовать число Петрова для $a = 10 000$ - как-то после получаса работы скрипта - забил, долго в общем, но это если тупо раскладывать на ВСЕ делители, есть же иные способы проверки простых чисел). Так вот, как утверждают любители раскладывать числа в промежутке $a = (1379; 10000]$ формула Петрова не выдает ни единого простого числа.

Я честно говоря так и не понял в чем суть вопроса, но появилась тема о неком "непонятном" распределении вероятности простых чисел в озвученной последовательности. Дескать с чего такой разброс вероятностей? Для той же последовательности Мерсенна такого разброса не наблюдается. Я понимаю к чему возникла тема: первое - это тупо практический интерес, реально ли вычислить простые числа Петрова, но в реалиях текущих вычислительных мощностей; второе - это тема распределения простых чисел на числовой оси; третье - интерес к самой формуле (ИМХО - вариация на тему "золотого сечения", не?!).

Стало интересно порассуждать хотя бы на интуитивном уровне. Формула Петрова - это своего рода экспоненциально возрастающая последовательность, состоящая из нечетных натуральных чисел. Мои (виртуальные) оппоненты (я с ними не спорил, просто видел комменты), судя по всему исходят из простого: значения последовательности выпадают на числовую ось множества натуральных чисел. Так как с виду последовательность Петрова ни чем особым не отличается, то и распределение в ней простых чисел должно примерно пропорционально соответствовать теореме о распределении простых чисел... То есть грубо говоря на каждую 1000 значений числа $a$, должно приходится хотя бы одно простое число. А этого не происходит...

ИМХО: а с чего это вообще должно происходить?! Это как надо было натянуть теорему о распределении простых чисел на последовательность вида $a^a-a-1$ ? Как заметил на одном форуме один комментатор (ув. Rados) множество образованное формулой Петрова, строго говоря, вообще не компактное. И следующее найденное простое число для такой формулы может быть при $ a = 10^{21}$, как пример

В чем я не прав?

[mihaild]

Безотносительно остального,

uzlprog в сообщении #1529115 писал(а):

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

Это что-то странное. Не выполнено даже для гораздо более простой последовательности $1, 2, 3, \ldots, n, n + 1, \ldots$.

[nnosipov]

Первоисточник https://oeis.org/A065798 Сомнительно, что простота аккуратно доказана для указанных значений типа $a=1379$ (максимум доказана псевдопростота).

[uzlprog]

mihaild в сообщении #1529119 писал(а):

Безотносительно остального,

uzlprog в сообщении #1529115 писал(а):

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

Это что-то странное. Не выполнено даже для гораздо более простой последовательности $1, 2, 3, \ldots, n, n + 1, \ldots$.

Ну и это тоже...

Цитата:

Первоисточник https://oeis.org/A065798 Сомнительно, что простота аккуратно доказана для указанных значений типа $a=1379$ (максимум доказана псевдопростота).

Не знал, что такую последовательность уже исследовали. Получается она хорошо известна. Но вроде бы oeis только таблицы с уже доказанными данными. Или нет?

[Someone]

nnosipov в сообщении #1529121 писал(а):

Сомнительно, что простота аккуратно доказана для указанных значений типа $a=1379$ (максимум доказана псевдопростота).

У кого на компьютере многоядерный процессор и Linux-64, могут скачать программу Primo и проверить. У меня Windows, а для неё есть только старая версия, которая число длиной 4330 цифр будет проверять несколько месяцев.

Для проверки последовательности $a^a-a-1$ на псевдопростоту можно использовать программу OpenPFGW. Она весьма шустрая.

[tolstopuz]

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

У кого на компьютере многоядерный процессор и Linux-64

Windows 11 уже поддерживает Linux-64 :)

В общем, примерно за два часа проверка для $a=1379$ успешно завершилась.

[nnosipov]

tolstopuz в сообщении #1529135 писал(а):

В общем, примерно за два часа проверка для $a=1379$ успешно завершилась.

А на каком процессоре?

[tolstopuz]

nnosipov в сообщении #1529139 писал(а):

А на каком процессоре?

i9-9900K, 8 потоков, больше не ставил, чтобы продолжать спокойно параллельно работать.

(Оффтоп)

Вообще программа попахивает кустарщиной, там используется самописная библиотека длинной арифметики на FreePascal и ассемблере x64, даже без SSE, не говоря уже об AVX. Думаю, еще в несколько раз ее ускорить возможно.

[nnosipov]

tolstopuz
Спасибо, интересный опыт. Значит, уже за пару часов можно получить сертификат простоты для числа с 4 тысячами знаков.

[uzlprog]

tolstopuz

Также благодарю за инфу!

[Someone]

uzlprog в сообщении #1529115 писал(а):

И кое-где в сети нашлись желающие для факторизации чисел последовательности до $a = 100 000$ (но понятно, что вычислительных силенок им хватило только до $a = 10 000$, я попробовал факторизовать число Петрова для $a = 10 000$ - как-то после получаса работы скрипта - забил, долго в общем, но это если тупо раскладывать на ВСЕ делители, есть же иные способы проверки простых чисел).

Вряд ли речь шла о факторизации, наверняка использовались тесты, основанные малой теореме Ферма и её усилениях. Хотя проверить не очень большие делители полезно, и их проверяют. Если ограничиваться попытками факторизации, то было бы много чисел, для которых не удалось найти ни одного делителя. Искать полное разложение на простые множители, конечно, интересно, но для проверки на простоту совершенно не нужно, и для чисел порядка $10^{500}$ в настоящее время практически неосуществимо.

Кстати, в A065798 написано

Цитата:

There is no further term up to 3000.

С помощью программы OpenPFGW я пока проверил диапазон $1$–$16\,000$. Других псевдопростых чисел, кроме уже перечисленных в стартовом сообщении, не обнаружено. Точных затрат времени не зафиксировал, но диапазон $14\,001$–$16\,000$ проверялся примерно $19$ часов. Планирую довести проверку до $20\,000$

[Someone]

Закончил проверку до $20\,000$. Псевдопростых чисел не встретилось.
Проверка диапазона $18\,001$–$20\,000$ заняла около полутора суток.
Десятичная запись числа $20\,000^{20\,000}-20\,000-1$ содержит $86\,021$ цифру.

Дальше проверять не буду. Если кто-нибудь может — внесите, пожалуйста, результаты в OEIS.

[Dmitriy40]

2000 чисел (18001-20000) за полтора суток это примерно по числу в минуту. Это как раз скорость работы OpenPFGW. Т.е. проверяли ей все числа подряд.
Но, потратив 15 минут (на PARI/GP, вообще почти не заморачиваясь с программой) на отфильтровывание из 2000 чисел делящихся на простые до $10^7$ можно уменьшить количество чисел для дальнейшей проверки OpenPFGW до 291шт, почти в 7 раз меньше, затратив на них часов 5-6 вместо полутора суток.
Можно ли заставить OpenPFGW быстро проверять малые (до сотен миллионов) делители и не фильтровать числа заранее я не знаю.

[Someone]

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

Можно ли заставить OpenPFGW быстро проверять малые (до сотен миллионов) (до сотен миллионов) делители

Можно. Она у меня и проверяет. Диапазон проверки она определяет сама в зависимости от величины проверяемого числа. Его можно увеличить или уменьшить, указав в ключе -f число процентов от диапазона "по умолчанию". Например, чтобы увеличить диапазон в $10$ раз, нужно написать -f1000. Если написать -f0, то никаких делителей она проверять не будет. Можно также указать конкретные границы для проверяемых делителей. Для числа $19\,999^{19\,999}-19\,999-1$ она проверяет делители до $29\,019\,905$. Если делитель не обнаружен, далее выполняется тест Ферма по основанию $3$ (можно указать другое основание от $2$ до $256$). Это не даёт доказательства, что число простое, но если требуется доказательство, то программа использует другие тесты.

В данном случае использовалась команда

..\pfgw64.exe -f -lLog.txt Dat-6.txt

(программа находится в объемлющем каталоге).
Файл Dat-6.txt содержит

ABC2 $a^$a-$a-1
a: from 18001 to 20000

(диапазон от $1$ до $20\,000$ был разбит на $6$ частей: первая — от $1$ до $10\,000$, остальные — по $2\,000$ значений).
В файл Log.txt записывается ход проверки. Его окончание выглядит так:

(Оффтоп)

19985^19985-19985-1 has factors: 527123

19986^19986-19986-1 has factors: 41

19987^19987-19987-1 has factors: 5

19988^19988-19988-1 has factors: 107

19989^19989-19989-1 has factors: 882169

19990^19990-19990-1 has factors: 23

19991^19991-19991-1 has factors: 139

19992^19992-19992-1 has factors: 78791

19993^19993-19993-1 has factors: 11

19994^19994-19994-1 has factors: 937

19995^19995-19995-1 has factors: 8360479

19996^19996-19996-1 has factors: 13

19997^19997-19997-1 is composite: RES64: [20A1E2AB8F8E4B39] (408.7699s+155.0299s)
19998^19998-19998-1 has factors: 5

19999^19999-19999-1 is composite: RES64: [8C95D79F277F8325] (408.2279s+129.6659s)
20000^20000-20000-1 has factors: 6619

Наблюдая за работой программы, я заметил, что за время тестирования, если оно сколько-нибудь продолжительное, USB-диск (твердотельный) успевает отключиться, и, когда программа хочет что-нибудь записать на него, ей приходится ждать, пока операционная система соблаговолит его подключить. Время ожидания весьма ощутимое — десятки секунд.
Найденные простые числа записываются в файл pfgw-prime.log. В данном случае в нём оказалось следующее:

3^3-3-1
4^4-4-1
5^5-5-1
6^6-6-1
9^9-9-1

Найденные псевдопростые числа записываются в файл pfgw.log:

17^17-17-1
22^22-22-1
85^85-85-1
710^710-710-1
844^844-844-1
1379^1379-1379-1

Можно попытаться применить эту программу для доказательства простоты чисел, перечисленных в последнем файле. Для этого создаём вложенный каталог, переписываем в него файл pfgw.log, переименовав его в pfgw.txt, и запускаем программу командой

..\..\pfgw64.exe -tc -f -x -lLog.txt pfgw.txt

В файле Log.txt будет

(Оффтоп)

Primality testing 17^17-17-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 7
Running N+1 test using discriminant 13, base 1+sqrt(13)
Running N+1 test using discriminant 13, base 2+sqrt(13)
Calling N+1 BLS with factored part 100.00% and helper 10.14% (311.59% proof)
17^17-17-1 is prime! (0.1882s+0.0233s)
Primality testing 22^22-22-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
Running N+1 test using discriminant 7, base 1+sqrt(7)
Calling N-1 BLS with factored part 41.84% and helper 20.41% (146.94% proof)
22^22-22-1 is prime! (0.0616s+0.0329s)
Primality testing 85^85-85-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 11
Running N+1 test using discriminant 23, base 2+sqrt(23)
Calling N+1 BLS with factored part 18.20% and helper 0.74% (55.51% proof)
85^85-85-1 is Fermat and Lucas PRP! (0.0638s+0.0122s)
Primality testing 710^710-710-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 7
Running N-1 test using base 19
Running N+1 test using discriminant 29, base 1+sqrt(29)
Calling N-1 BLS with factored part 0.73% and helper 0.42% (2.63% proof)
710^710-710-1 is Fermat and Lucas PRP! (1.2083s+0.0350s)
Primality testing 844^844-844-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Running N-1 test using base 23
Running N+1 test using discriminant 59, base 1+sqrt(59)
Calling N+1 BLS with factored part 0.85% and helper 0.56% (3.12% proof)
844^844-844-1 is Fermat and Lucas PRP! (2.0347s+0.1272s)
Primality testing 1379^1379-1379-1 [N-1/N+1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 11
Running N+1 test using discriminant 17, base 1+sqrt(17)
Calling N+1 BLS with factored part 0.78% and helper 0.01% (2.35% proof)
1379^1379-1379-1 is Fermat and Lucas PRP! (5.0483s+0.0566s)

Соответственно, файл pfgw-prime.log будет содержать

17^17-17-1
22^22-22-1

а файл pfgw.log —

85^85-85-1
710^710-710-1
844^844-844-1
1379^1379-1379-1

то есть, с последними четырьмя числами программа не справляется.

[Dmitriy40]

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

В данном случае использовалась команда

Да, спасибо, с -f (и с -eX при желании) действительно сначала перебирает малые делители. И достаточно быстро, раза в полтора быстрее PARI/GP (21с против 30с для n=19999).

Я ошибся в оценке скорости работы PFGW64 у Вас, у меня она работает сильно быстрее:

Используется синтаксис Text

T:\PFGW>pfgw64.exe -k -q19999^19999-19999-1
19999^19999-19999-1 is composite: RES64: [8C95D79F277F8325] (104.1404s+0.0025s)
T:\PFGW>pfgw64.exe -k -q19999^19999-19999-1 -f
19999^19999-19999-1 is composite: RES64: [8C95D79F277F8325] (103.8402s+20.9080s)
T:\PFGW>pfgw64.exe -k -q19999^19999-19999-1 -f -T4
19999^19999-19999-1 is composite: RES64: [8C95D79F277F8325] (95.9558s+20.9840s)

В один поток получается в 4.3 раза быстрее, в 4 потока (занимая при этом лишь 60% процессора и перебирая делители всегда однопоточно) в 4.6 раза быстрее. Поэтому и посчитал ошибочно что у Вас делители не проверяются.
Почему такая огромная разница в скорости непонятно, у меня Core i5 3.5ГГц и Win7, ну не может же у Вас процессор работать медленнее 1ГГц (если только не ноут в режиме экономии энергии).

С другой стороны, параллельность PFGW64 вообще никакая, выигрыш вместо 4x составил всего 7%, при том что процессор загрузился на 60% против 25%.
Потому выгоднее запускать именно предварительно отсев делителей многопоточно (я в PARI/GP) и PFGW64 запускать в каждом потоке в однозадачном режиме, время в каждом потоке получится то же, 30с+104с (PARI/GP+PFGW64 для n=19999), зато будет реально в 4 потока полностью загружать процессор, т.е. эффективная скорость станет почти в 4 раза выше. И да, проверил на практике: запустив уже ночью счёт с нуля я в 4 потока досчитал до n=20000 за 10ч (а если бы процессор гад не перегревался, то и за 8.5ч), подтвердив Ваш результат отсутствия новых псевдопростых.

-- 07.09.2021, 13:04 --

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

Потому выгоднее запускать именно предварительно отсев делителей многопоточно (я в PARI/GP) и PFGW64 запускать в каждом потоке в однозадачном режиме

Про предварительный отсев я тут не прав конечно, выгоднее просто запускать много копий PFGW64 в однозадачном режиме каждую, а уж делать предварительный отсев или оставить его на усмотрение PFGW64 без разницы (выигрыш менее 10% времени вычислений).
И всё уменьшение времени перепроверки у меня объясняется аномально низкой скоростью PFGW64 у Вас.