Фотострана » Интересные страницы » Науки и технологии » Канал о Простых числах » 2.1.2. ДЕЛИТЕЛИ ЧИСЕЛ ФЕРМА k*2^(m+2) +1
2.1.2. ДЕЛИТЕЛИ ЧИСЕЛ ФЕРМА k*2^(m+2) +1
В прошлый раз я начал рассказывать о числах Ферма. Это числа вида
Fm = 2^(2^m) +1
Первые 5 из них являются простыми:
F0 = 2^(2^0) +1 = 2^1 +1 = 3 - Простое число из 1 цифры!
F1 = 2^(2^1) +1 = 2^2 +1 = 5 - Простое число из 1 цифры!
F2 = 2^(2^2) +1 = 2^4 +1 = 17 - Простое число из 2 цифр!
F3 = 2^(2^3) +1 = 2^8 +1 = 257 - Простое число из 3 цифр!
F4 = 2^(2^4) +1 = 2^16 +1 = 65537 - Простое число из 5 цифр!
Далее такой ряд демонстрирует крайне быстрый рост. На текущий момент установлено, что числа Ферма F5..F32 являются точно составными (у большинства были найдены делители, а F20 и F24 - без известных делителей - проверены с помощью теста Пепина). О характере остальных чисел остается лишь догадываться - даже для проверки следующего потенциального кандидата F33 требуются такие огромные вычислительные ресурсы, которых у Человечества не предвидится в ближайшие века!
Поэтому, на рубеже тысячелетий (что символично), энтузиасты бросили все силы на поиск новых делителей, чтобы хотя бы таким способом - шаг за шагом, исключать из дальнейшего рассмотрения составных кандидатов. Координацией усилий занимается проект , о котором я скоро тоже расскажу подробнее. Ну а пока приведу краткие "сводки с фронтов".
В 1878 году Люка доказал, что все делители чисел Ферма Fm = 2^(2^m) +1
должны иметь вид k*2^(m+2) +1, что очень помогло в дальнейших поисках.
На 01 июля 2020 года всего найдено 353 делителя (последовательность ) для 309 составных чисел Ферма.
РАСПРЕДЕЛЕНИЕ НАХОДОК ПО ГОДАМ:
1732 - 2 шт - Докомпьютерная эпоха (16 шт найдено вручную за 220 лет)
1855 - 2 шт
1877 - 1 шт
1878 - 1 шт
1886 - 1 шт
1899 - 2 шт
1903 - 5 шт
1906 - 1 шт
1925 - 1 шт
1953 - 2 шт - Начало компьютерных вычислений (ЭВМ SWAC)
1956 - 14 шт
1957 - 6 шт
1962 - 2 шт
1963 - 11 шт
1970-79 - 25 шт
1980-89 - 46 шт
1990-99 - 77 шт
2000-09 - 77 шт
2010-19 - 74 шт
2020 - 3 шт - (337 шт найдено с помощью компьютеров за 67 лет)
Более подробно смотрите на странице Истории:
Самым первым был найденный Эйлером в 1732 году делитель числа
F5 = 4294967297 = 641*6700417 (второй сомножитель, соответственно, был вторым). Последним известным (353-м) - найденный Гари Гостиным 30 июня 2020 делитель числа
F11075 = (171369935*2^11077 +1)*Кофактор
Самое маленькое из известных составных чисел Ферма - это F5 (снова спасибо Эйлеру).
Самое крупное - F5523858 = (13*2^5523860 +1)*Кофактор (спасибо Джеймсу Скотту Брауну и сообществу PrimeGrid, 22 января 2020 года).
Простые числа, являющиеся делителями чисел Ферма, выделены в отдельную группу, по которой также отслеживаются рекорды:
1) 13*2^5523860 +1 - делитель F5523858 (1.662.849 цифр) найден в 2020
2) 193*2^3329782 +1 - делитель F3329780 (1.002.367 цифр) найден в 2014
3) 57*2^2747499 +1 - делитель F2747497 (827.082 цифры) найден в 2013
4) 267*2^2662090 +1 - делитель F2662088 (801.372 цифры) найден в 2015
5) 9*2^2543551 +1 - делитель F2543548 (765.687 цифр) найден в 2011
ТОП-20 наибольших делителей см. на сайте Криса Колдуэлла:
А еще коэффициент "k" в формуле может быть четным или даже кратным степеням двойки! В этом случае мы получим делители вида:
k*2^(m+3) +1
k*2^(m+4) +1
k*2^(m+5) +1
...
k*2^(m+DELTA) +1
...
Причем, таких чисел оказалось немало:
DELTA = 2 - 178 шт (т.е. строго нечетное K)
DELTA = 3 - 86 шт (кратно 2)
DELTA = 4 - 47 шт (кратно 4)
DELTA = 5 - 13 шт (кратно 8)
DELTA = 6 - 10 шт (кратно 16)
DELTA = 7 - 5 шт (кратно 32)
DELTA = 8 - 6 шт (кратно 64)
DELTA = 9 - 3 шт (кратно 128)
DELTA = 10 - 3 шт (кратно 256)
DELTA = 11 - 1 шт (кратно 512)
DELTA = 12 - 1 шт (кратно 1024)
DELTA = 13 - Такого еще нет (это потенциальный рекорд)!
См. страницу составных чисел
ИНТЕРЕСНА И СТАТИСТИКА ЧИСЕЛ ФЕРМА ПО КОЛИЧЕСТВУ ДЕЛИТЕЛЕЙ:
8+ делителей - 1 шт (F12)
7+ делителей - Такого еще нет (это потенциальное достижение)!
6+ делителей - 1 шт (F13)
5+ делителей - 3 шт (F11,F15,F19)
4+ делителей - 11 шт (F10,F16,F17,F18,F25,F28,F29,F31,F32,F52,F287)
3+ делителей - 13 шт (F9,F27,F30,F36,F38,F39,F42,F77,F147,F150,F284, F416,F417)
2+ делителей - 280 шт (F5,F6,F7,F8,остальные)
Делитель единица тут не учитывается!
РАСПРЕДЕЛЕНИЕ НАЙДЕННЫХ ДЕЛИТЕЛЕЙ ПО СТРАНАМ:
USA - 102 шт
Japan - 31 шт
Russia - 23 шт
Austria - 9 шт
Finland - 5 шт
Germany - 5 шт
Iran - 5 шт
Brazil - 2 шт
Sweden - 2 шт
Ukraine - 2 шт
Belgium - 1 шт
South Africa - 1 шт
Spain - 1 шт
См. страницу искателей
РАСПРЕДЕЛЕНИЕ НАЙДЕННЫХ ДЕЛИТЕЛЕЙ ПО ИСКАТЕЛЯМ:
Gary Gostin - 83 шт
Tadashi Taura - 18 шт
Takahiro Nohara - 13 шт
Roman Maznichenko - 8 шт
Serge Batalov - 6 шт
Pacher Maximilian - 6 шт
Jim Fougeron - 6 шт
Payam Samidoost - 5 шт
Vasily Danilov - 5 шт
Leonid Durman - 5 шт
Peter Strasser - 3 шт
Tapio Rajala - 3 шт
Peter Grobstich - 2 шт
Goran Axelsson - 2 шт
Nestor Melo - 2 шт
Michael Eaton - 2 шт
Asko Vuori - 2 шт
Alexander Kruppa - 1 шт
Adolf Nordin - 1 шт
Ryan Propper - 1 шт
Mark Rodenkirch - 1 шт
Nikolay Kamenyuk - 1 шт
Andriy Sen - 1 шт
Sergei Maiorov - 1 шт
Dmitry Komin - 1 шт
Michael Dangler - 1 шт
Sergey Kuzmin - 1 шт
Anton Oleynik - 1 шт
Craig Kitchen - 1 шт
Alfredo Cano - 1 шт
Cedric Vonck - 1 шт
Ray Ballinger - 1 шт
Martin Schroeder - 1 шт
Marko Bodschwinna - 1 шт
Gennady Gusev - 1 шт
См. страницу делителей
Отдельно хочу упомянуть нескольких искателей:
Gary Gostin - действительно Легенда, интенсивно искал делители в 1978-93 годах, затем, после перерыва, возобновил поиски в 2000-н.в. Использует собственную программу для факторизации (разложения на множители) чисел Ферма.
Tadashi Taura - знаменит тем, что много лет собирает у себя дома различную вычислительную технику, и живет, по сути, внутри мэйнфрейма! Занимался поиском делителей чисел Ферма в 1995-2002, а затем переключился на поиск делителей чисел Мерсенна (и нашел их уже несколько миллионов)!
Leonid Durman - основатель проекта и разработчик программы для факторизации FERMAT. Очень поспособствовал развитию поиска делителей в России!
Ryan Propper - хотя в данном проекте его результаты пока скромные, но он отличился во многим других: находил огромные делители чисел Мерсенна, факторизовал одно из RSA-чисел, ставил и рекорды Простых чисел в отдельных номинациях. Думаю, я еще напишу о нем.
ССЫЛКИ ПО ТЕМЕ:
Страница "хранителя" делителей чисел Ферма - Вилфрида Келлера
Координирующий проект по поиску делителей чисел Ферма
Раздел форума с обсуждением вопросов поиска делителей (ENG)
КОМУ ИНТЕРЕСНЫ ДАННЫЕ ПУБЛИКАЦИИ - ЧИТАЙТЕ ПРОШЛЫЕ ВЫПУСКИ И ПОДПИСЫВАЙТЕСЬ НА КАНАЛ:
https://fotostrana.ru/public/352531/
ПИШИТЕ В КОММЕНТАРИЯХ, ЕСЛИ ТОЖЕ ХОТИТЕ ПОУЧАСТВОВАТЬ В СОВМЕСТНЫХ ПОИСКАХ ПРОСТЫХ ЧИСЕЛ!
войдите, используя
или форму авторизации