Проект «Простые числа»: Отчет 0009 от Alex_soldier

Внезапно появилось желание посчитать что-то простое и относительно небольшое. Вспомнил про свой давний интерес к прогрессиям из простых чисел. Подумал, что неплохо было бы поискать одиночные простые числа в окрестностях какой-нибудь большой экспоненты (я выбрал 2^{^35.753} - 10.763 знаков и красивая палиндромная степень): кто знает, вдруг они сложатся в AP, а то и CP!

К сожалению, NewPGen тут меня сильно подвел: прогрессии он считает как-то очень странно, а простейший сплошной диапазон и вовсе не умеет просеивать. Пришлось самому генерировать файл для LLR в нужном формате и без всякого предварительного отсеивания составных кандидатов.

LLR заработала весьма резво, но удивило, что никак не может найти ни одного PRP, хотя обсчитала уже несколько тысяч кандидатов. Потом я вспомнил, что плотность простых чисел на отрезке можно оценить весьма простой формулой: a/ln(X) = 1.000.000/(35.753*ln(2)) ≈ 40 простых на миллион (для сравнения: в 1-м миллионе их было более 78 тысяч).

Стало понятно, что поиск "в лоб" будет слишком долгим. Пришлось наскоро написать собственную программу для предварительного отсева составных кандидатов - PrimeBigSieve, причем отсев был реализован одновременно в обе стороны от экспоненты: и в плюс, и в минус. На следующий день я несколько ускорил программу, и отсеял изрядную долю кандидатов на диапазоне: -10.000.000 < k < 10.000.000

Вскоре "попались" и первые PRP: 2^{^35.753} -12.753 и 2^{^35.753} +8.705

Учитывая, что среднее расстояние между соседними простыми числами (GAP) в данной области примерно 25.000, шансов найти AP с маленькой разницей практически нет. Зато каждая AP может оказаться еще и CP, что придает поиску дополнительный азарт. На текущий момент рекорд для CP3 - 10.546 знаков, а для AP5 - 7.035 знаков. Моя экспонента содержит 10.763 знака, поэтому любые найденные CP3+ или AP5+ автоматически станут мировыми рекордами!

Единственный минус: крайне хлопотно проверять вручную, не сложилась ли прогрессия из каких-либо найденных PRP. Для этих целей я написал вторую программу - APBuilder. Она перебирает все возможные комбинации PRP и сигнализирует, получается ли из них хоть одна AP3. Позднее я добавил в нее и функцию проверки наличия GAP в таблицах Томаса Найсли.

Ну что же, поиск идет, найдено несколько сотен PRP, с каждым из которых растут шансы получить прогрессию, или крупный GAP!



Ссылки:

Страница рекордов CP: http://primes.utm.edu/top20/page.php?id=13

Страница рекордов AP: http://primes.utm.edu/top20/page.php?id=14

Страница рекордов GAP: http://trnicely.net/#TPG

Программа для отсева составных претендентов PrimeBigSieve:
Слишком кустарная, в свободный доступ выкладывать нет смысла.

Программа для тестирования оставшихся претендентов LLR:
http://primes.utm.edu/bios/page.php?id=431
http://jpenne.free.fr/index2.html

Программа для комбинирования прогрессий из разрозненных PRP APBuilder:
Слишком кустарная, в свободный доступ выкладывать нет смысла.

Программа для финального тестирования Primo (только под Linux):
http://www.ellipsa.eu/public/primo/primo.html

1) Найти CP3+ и установить новый рекорд.
2) Найти AP5+ и установить новый рекорд.
3) Найти крупный GAP и попасть в таблицы Томаса Найсли (готово - 2016.08.09).

2016.08.05: Старт вычислений. Написана версия ПО PrimeBigSieve v.1 для предварительного отсева составных кандидатов и версия ПО APBuilder v.1 для поиска возможных CP/AP среди всего множества найденных PRP.

2016.08.09: Неожиданно нашел GAP = 157.264 - оказалось, такого значения еще нет в таблицах Томаса Найсли. Так что программа-минимум уже выполнена :)

2016.08.12: Наткнулся на непонятное магическое число k = 2.796.202. До него время проверки 1 кандидата росло очень плавно, а тут вдруг скакнуло с 4 до 14 секунд! Видимо, был пройден какой-то порог в APRCL-тесте в LLR. Мне удалось установить, что у порога весьма интересный двоичный вид: 10 1010 1010 1010 1010 1010. Продолжаю считать дальше, хоть и в 3,5 раза медленнее.

На момент 2016.09.03 проверен диапазон -3.750.000 < k < 3.730.000
Прогрессий AP3 не найдено. Найден 1 значимый результат GAP.
Поиск продолжается!