Проект «Простые числа»

Поиск арифметической прогрессии (если получится, то прогрессии без пропусков) или значимого расстояния между двумя соседними простыми числами из более чем 10.000 знаков.

Главная Виды чисел Проекты Программы Команды Персоны Отчеты

ОТЧЕТ 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.
Поиск продолжается!

2016.08.09 GAP = 157.264



Другие мои отчеты: http://Prime-Numbers.ru/person/Alex_soldier/
© Copyright 2014 - Today by Alex_soldier
Сайт сделан по технологии AML

ВИДЫ ПРОСТЫХ ЧИСЕЛ

Одиночные простые:



Семейства простых:



Поиск делителей:



Разное: