Делители чисел Ферма: k*2^(m+2) +1

25 July 2020
Пьер Ферма (1601-1665)
Пьер Ферма (1601-1665)

В прошлый раз я начал рассказывать о числах Ферма. Это числа вида

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 требуются такие огромные вычислительные ресурсы, которых у Человечества не предвидится в ближайшие века!

Поэтому, на рубеже тысячелетий (что символично), энтузиасты бросили все силы на поиск новых делителей, чтобы хотя бы таким способом - шаг за шагом, исключать из дальнейшего рассмотрения составных кандидатов. Координацией усилий занимается проект FERMATSEARCH.ORG, о котором я скоро тоже расскажу подробнее. Ну а пока приведу краткие "сводки с фронтов".

В 1878 году Люка доказал, что все делители чисел Ферма Fm = 2^(2^m) +1 должны иметь вид k*2^(m+2) +1, что очень помогло в дальнейших поисках.

На 24 июля 2020 года всего найдено 353 делителя (последовательность A023394) для 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 - Такого еще нет (это потенциальный рекорд)!

См. страницу составных чисел FERMATSEARCH.ORG >>>

Интересна и статистика чисел Ферма по количеству делителей:

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 шт

См. страницу искателей FERMATSEARCH.ORG >>>

Распределение найденных делителей по искателям:

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 шт

См. страницу делителей FERMATSEARCH.ORG >>>

Отдельно хочу упомянуть нескольких искателей:

Gary Gostin - действительно Легенда, интенсивно искал делители в 1978-93 годах, затем, после перерыва, возобновил поиски в 2000-н.в. Использует собственную программу для факторизации (разложения на множители) чисел Ферма.

Tadashi Taura - знаменит тем, что много лет собирает у себя дома различную вычислительную технику, и живет, по сути, внутри мэйнфрейма! Занимался поиском делителей чисел Ферма в 1995-2002, а затем переключился на поиск делителей чисел Мерсенна (и нашел их уже несколько миллионов)!

Leonid Durman - основатель проекта FERMATSEARCH.ORG и разработчик программы для факторизации FERMAT. Очень поспособствовал развитию поиска делителей в России!

Ryan Propper - хотя в данном проекте его результаты пока скромные, но он отличился во многим других: находил огромные делители чисел Мерсенна, факторизовал одно из RSA-чисел, ставил и рекорды Простых чисел в отдельных номинациях. Думаю, я еще напишу о нем.

Ссылки по теме:

Страница "хранителя" делителей чисел Ферма - Вилфрида Келлера >>>

Координирующий проект по поиску делителей чисел Ферма >>>

Раздел форума с обсуждением вопросов поиска делителей >>>

Читайте также:

Числа Ферма >>>

Оглавление - все мои публикации о Простых числах >>>

Пишите в комментариях, если тоже хотите поучаствовать в совместных поисках Простых чисел!