Кстати, последовательность простых чисел Мерсенна 2N-1 имеет следующий вид:
M2=3, M3=7, M5=31, M7=127, M13=8191, M17=131071, M19=524287, M31=2147483647, ...
При этом показатели N, что удивительно, сами тоже являются простыми числами (доказательство этой теоремы можно найти в интернете):
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, ...
Существует и другая теорема, называемая теоремой Ферма-Эйлера, открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4*k+1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4*111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197*19197 + 8710*8710. Теорема была доказана Эйлером лишь через 100 лет.
И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.
Так что с простыми числами не все так просто. Есть и удивительные факты. Например, в 1883 г. русский математик И.М.Первушин из Пермского уезда доказал простоту числа 261 — 1 = 2305843009213693951. Даже сейчас компьютеру с запущенной вышеприведенной программой требуется несколько минут на проверку данного числа, а на то время это была поистине гигантская работа.
Кстати интересно, что существуют люди, обладающие уникальными способностями мозга — так например, известны аутисты, способные находить в уме (!) 8-значные простые числа. Как они это делают, непонятно. Такой пример описывается в книге известного врача-психолога Оливера Сакса “Человек, который принял жену за шляпу”. По некоторым предположениям, такие люди обладают способностью “видеть” числовые ряды визуально, и пользуются методом “решета Эратосфена” для определения, является ли число простым или нет.
Еще два интересных простых числа: 73939133 и 1979339333. Они интересны тем, что если от них убирать правую цифру, то каждое новое число - тоже простое:
73939133 - 7393913 - 739391 - 73939 - 7393 - 739 - 73 - 7
1979339333 - 197933933 - 19793393 - 1979339 - 197933 - 19793 - 1979 - 197 - 19 - 1
Для нахождения всех подобных чисел можно написать несложную программу, использующую написанную ранее функцию is_prime:
for v in xrange(10000001, 99999999, 2):
v0, v1, v2, v3, v4, v5, v6, v7 = v, v/10, v/100, v/1000, v/10000,
v/100000, v/1000000, v/10000000
if is_prime(v7) and is_prime(v6) and is_prime(v5) and is_prime(v4) and
is_prime(v3) and is_prime(v2) and is_prime(v1) and is_prime(v0):
print v0, v1, v2, v3, v4, v5, v6, v7
Несколько сотен лет математикам известна другая, не менее оригинальная последовательность, где все числа простые:
31 331 3331 33331 333331 3333331 33333331
Дальше ряд заканчивается, число 333333331 = 17*19607843, простым не является.
Желающие могут проверить самостоятельно, не обладают ли другие последовательности (51, 551, 61, 661 и пр) такими же свойствами.
Еще одна интересная гипотеза была выдвинута Ферма, который предположил, что все числа вида
являются простыми. Эти числа называются “числами Ферма”. Однако, это оказалось верным только для 5 первых чисел: F0=3, F1=5, F2=17,F3=257, F4=65537. В 1732 году Эйлер опроверг гипотезу, найдя разложение на множители для F5: F5= 641·6700417. Существуют ли другие простые числа Ферма, пока неизвестно до сих пор. Такие числа растут очень быстро (для примера, F7=340282366920938463463374607431768211457), и их проверка является непростой задачей даже для современных компьютеров.