Специалисты по теории чисел, занятые поисками больших простых чисел, часто рассматривают числа вида k2ⁿ + 1 для какого-то выбранного k при разных n. Пробные расчеты позволяют предположить, что для большинства значений k среди этих чисел встречается по крайней мере одно простое число, часто больше. К примеру, если k = 1, то 1 × 2ⁿ + 1 является простым для n = 2, 4, 8. Если k = 3, то 3 × 2ⁿ + 1 простое при n = 1, 2, 5, 6, 8, 12. Если k = 5, то 5 × 2ⁿ + 1 простое при n = 1, 3, 7. (В общем случае мы можем разделить k на 2 столько раз, сколько нужно, чтобы получить нечетное число, а все двойки включить в 2n. Поэтому можно смело считать k нечетным, не теряя общности. К примеру, 24 × 2ⁿ = 3 × 23× 2ⁿ = 3 × 2ⁿ⁺³.)

Соблазнительно предположить, что для любого k³≥2 существует по крайней мере одно простое число вида k2ⁿ + 1. Однако в 1960 г. Вацлав Серпинский доказал, что существует бесконечно много нечетных k, для которых все числа вида k2ⁿ + 1 являются составными. Эти числа получили название чисел Серпинского.

В 1992 г. Джон Селфридж доказал, что 78 557 – число Серпинского; он показал, что все числа вида 78 557 × 2ⁿ + 1 делятся по крайней мере на одно из чисел 3, 5, 7, 13, 19, 37, 73. Говорят, что эти числа образуют покрывающее множество. Приведем первые десять известных чисел Серпинского:

78 557 271 129 271 577 322 523 327 739

482 719 575 041 603 713 903 983 934 909

Считается, что 78 557 – наименьшее число Серпинского, но пока этот факт никем не доказан и не опровергнут. В 2002 г. на сайте был организован поиск простых чисел вида k2ⁿ + 1, существование которых доказывало бы, что k не является числом Серпинского. Когда поиск только начинался, у математиков было 17 кандидатов на роль чисел Серпинского, не превышающих 78 557, но постепенно они были ликвидированы, так что осталось только шесть: 10 223, 21 181, 22 699, 24 737, 55 459 и 67 607. Попутно в рамках проекта было найдено несколько очень больших простых чисел.