Большие простые числа: вес последовательностей

Посмотрите на эту картинку. Она называется «скатерть Улама». Пиксели нумеруются из центра по спирали, и если номер пикселя — простое число, то он закрашивается чёрным. В глаза сразу бросаются диагональные линии. Если присмотреться, можно заметить горизонтальные и вертикальные линии. Что это? Простые числа вдруг подчиняются какому-то закону? Или же Вселенная пытается нам что-то сказать? Конечно же нет. Это наглядная иллюстрация того, что числовые последовательности могут иметь разный вес.

То, что существуют формулы, порождающие необычайно много простых чисел, заметил ещё великий российский математик швейцарского происхождения Леонард Эйлер. Найденный им многочлен x² − x + 41 принимает простые значения для всех x меньших 41. И хотя при больших x начинают встречаться составные числа, простых всё равно оказывается неожиданно много. Диагональные, вертикальные и горизонтальные линии на скатерти Улама описываются формулой 4x² + bx + c. Многочлен Эйлера хорошо виден на скатерти — это линия, начинающаяся чуть выше центра и уходящая вправо вверх.

Чем же вызван подобный эффект? Если коротко, то взаимодействием многочленов с маленькими простыми числами. Для каждого простого числа известны особые формулы, которые всегда делятся на это число. Например, такие формулы дают малая теорема Ферма и теорема Эйлера. Эти формулы очень легко применить к многочленам. Возьмём многочлен 2x² + 1, он будет делиться на 3 при x, не делящемся на 3, а на 11 только при x = 11n ± 4. И такие правила делимости существуют для каждого многочлена, у каких-то их больше, у каких-то меньше. В результате, маленькие простые числа хорошо "просеивают" одни многочлены и не трогают другие. Эти зависимости не всегда очевидны в алгебраическом виде, но их легко увидеть на практике. Например, на скатерти Улама.

Просеивание с помощью маленьких простых чисел хорошо известно с античных времён в виде алгоритма под названием «решето Эратосфена». Из последовательности чисел от 2 до N вычёркиваются все, делящиеся на 2, потом делящиеся на 3, потом делящиеся на 5 и так далее до некоторого простого числа P, которое называется «глубина просеивания». Сколько остаётся чисел в этой последовательности? Допустим, N много больше P. Тогда мы можем оценить количество оставшихся чисел S(N,P) с помощью вероятностей. Вероятность того, что число не делится на 2, равна 1/2. Не делится на 3 = 2/3. Не делится на 5 = 4/5. Перемножив эти дроби, мы получим вероятность "выживания" числа при просеивании. Интересно, что эту вероятность можно вычислить гораздо проще, с помощью третьей теоремы Мертенса:

где γ — постоянная Эйлера-Маскерони. Таким образом, результат работы решета Эратосфена можно предсказать с помощью константы e^γ, найденной через пару тысяч лет после Эратосфена.

Но можем ли мы написать подобную формулу для многочленов? Гипотеза Бейтмана-Хорна и некоторые другие гипотезы утверждают, что да. Для этого нам понадобится некоторая характеристика последовательности, которую мы назовём «вес». Она показывает, насколько больше или меньше чисел остаётся после просеивания в этой последовательности по сравнению с последовательностью целых чисел. Например, если мы возьмём чётные числа, то очевидно, что после первого же шага просеивания в этой последовательности не останется ни одного числа. Вес чётных чисел равен нулю. Если же мы возьмём нечётные числа, то после просеивания их останется в два раза больше, поэтому их вес равен двум. Тот же принцип работает и для многочленов, и даже для экспоненциальных последовательностей. Это, конечно, не доказано и, возможно, никогда не будет доказано, но прекрасно работает на практике. Просеивание произвольных последовательностей f описывается формулой:

Как узнать вес C_f последовательности? Для некоторых его можно точно вычислить, но гораздо проще оценить его экспериментально. Возьмём N = 100 000, P = 1 000 и выполним просеивание. Для примера возьмём многочлен Эйлера, после просеивания останется 54 110 чисел. Таким образом, вес многочлена Эйлера можно оценить как

Неудивительно, что эта линия так хорошо видна на скатерти. В ней в 6,66 раз больше точек, чем в случайной.

Последнее утверждение требует пояснения. Как связан вес и количество простых чисел в последовательности? Теорема о распределении простых чисел говорит нам, что вероятность простоты зависит только от размера числа. Меняется ли она для тяжёлых последовательностей? Нет. Вероятность остаётся той же самой, но вот количество кандидатов в тяжёлых последовательностях гораздо больше. Если просуммировать вероятности, то математическое ожидание количества простых в тяжёлой последовательности будет в вес раз больше, чем для случайных чисел того же размера. Это можно использовать при генерации простых чисел. Кроме того, на вероятность простоты очевидно влияет глубина просеивания. При достаточно большой глубине просеивания вероятность простоты может оказаться равной 1, как это и задумывалось Эратосфеном. Поэтому при выборе проекта распределённых вычислений для поиска больших простых чисел следует обращать внимание не на вес проверяемых там последовательностей, а на глубину просеивания.

Как уже упоминалось ранее, с точки зрения веса и просеивания экспоненциальные последовательности ведут себя так же, как и полиномиальные. Исторически особый интерес представляют последовательности вида k·2ⁿ + 1. Вацлав Серпинский доказал, что существует бесконечное число нечётных k, при которых вес последовательности равен нулю, то есть в ней никогда не встретится простое число. Такие k называются «числа Серпинского». Самое маленькое из известных чисел Серпинского равно 78 557. То, что оно минимальное легко доказать — достаточно найти по одному простому числу в каждой последовательности с k < 78 557. К началу 2000-х годов это было сделано для всех последовательностей кроме семнадцати. Благодаря усилиям проектов Seventeen or Bust (SoB) и PrimeGrid, к настоящему моменту осталось только пять k: 21 181, 22 699, 24 737, 55 459 и 67 607. В следующей таблице приведены примерные веса соответствующих последовательностей:

Видно, что у двух последовательностей вес сильно меньше других. Что это означает в практическом плане? Что кандидатов с k 22 699 и 67 607 сильно меньше других. Хорошо это или плохо? С одной стороны, меньше кадидатов — меньше работы. Но с другой стороны, это ведёт к тому, что для этих k размер кандидатов растёт очень быстро. А с увеличением размера числа в два раза, вероятность найти простое за единицу процессорного времени падает в 8 раз (вероятность простоты падает в 2 раза, количество длинных умножений увеличивается в 2 раза, сложность длинного умножения увеличивается в >2 раза). Таким образом, высока вероятность, что последовательность 67 607 уйдёт в область очень больших чисел, где один тест простоты будет выполняться недели и месяцы на современных вычислительных устройствах. Решение задачи о минимальном числе Серпинского при нашей жизни во многом зависит от того, повезёт ли нам с 67 607 и 22 699.

Кстати о везении. Для решения задачи, мы ищем только первое простое в каждой последовательности. Можно вычислить такую характеристику, как «ожидаемое количество простых в последовательности на момент первого реального простого». Иначе говоря, сколько работы мы затратили относительно теоретически необходимой (похожая характеристика у майнеров называется «effort»). Если работы затрачено меньше 1, то нам повезло. Если больше 1, то не повезло. Теорема о распределении простых чисел говорит нам, что работа в среднем равна 1, что подтверждается практикой. Если взять все k и отсортировать их по затраченной работе, то получится экспоненциальное распределение, что также соответствует теории.

На этом графике представлены все k < 271 129, в том числе отмечено текущее положение последовательностей, в которых поиск ещё продолжается. Задача о минимальном числе Серпинского отмечена как SoB (текущее n = 42 480 391), задача о минимальном простом числе Серпинского (Prime Sierpiński Problem) отмечена как PSP (текущее n = 33 140 576) и задача о втором числе Серпинского (Extended Sierpiński Problem) отмечена как ESP (текущее n = 27 249 801). Эти две дополнительные задачи проверяют все k до 271 129.

По мере того, как проверяется всё больше кандидатов, актуальные k сдвигаются вправо. Можно заметить, что есть группа "неудачливых" k (положение среди всех k > 95%), которым пока просто не повезло найти простое число. Но в этих последовательностях много кандидатов, поэтому есть уверенность, что рано или поздно поиск увенчается успехом. Однако, есть группа "медленных" k (<90%), которые не то, чтобы сильно неудачливы, просто у этих последовательностей низкий вес и мало кандидатов. Но если случится так, что 67 607 помимо "медленности" ещё окажется и "неудачливым", то количество ресурсов, необходимых для решения задачи, может выйти на галактический масштаб по шкале Кардашёва.

Последний на данный момент успех был с k = 202 705. Число 202 705 · 2^{21 320 516} + 1 оказалось простым. Это k является самым неудачливым во всём списке. В момент нахождения первого простого в последовательности, там ожидалось уже 10,1 простых. Вес этой последовательности 0,502, и количество кандидатов было очень большим. В конце концов это сработало.

Страшно подумать, что будет, если 67 607 тоже решит держаться до 10,1 (n = 10⁴⁷).