В завершение темы простых чисел, приведем вид так называемой “спирали Улама”. Математик Станислав Улам открыл ее случайно в 1963 году, рисуя во время скучного доклада на бумаге числовую спираль и отмечая на ней простые числа:
Как оказалось, простые числа образуют вполне повторяющиеся узоры из диагональных линий. В более высоком разрешении изображение выглядит так (картинка с сайта http://ulamspiral.com):
В общем, можно предположить что далеко не все тайны простых чисел раскрыты и до сих пор.
6. Совершенные числа
Еще одно удивительное свойство мира чисел было доказано еще Евклидом: если число вида 2>p-1 является простым (уже известное нам число Мерсенна), то число 2>P-1(2>p-1) является совершенным, т.е. равно сумме всех его делителей.
Рассмотрим пример для p=13:
2>13-1 = 8191. Как показывает приведенная ранее программа, 8191 - действительно простое число.
2>12*(2>13-1) = 33550336.
Чтобы найти все делители числа и их сумму, напишем небольшую программу:
def is_perfect(n):
sum = 0
for i in range(1, int(n/2)+1):
if n % i == 0:
sum += i
print(i)
print("Сумма",sum)
return sum == n
is_perfect(33550336)
Действительно, 33550336 делится на числа 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8191, 16382, 32764, 65528, 131056, 262112, 524224, 1048448, 2096896, 4193792, 8387584, 16775168. И сумма этих чисел равна искомому 33550336.
Совершенные числа встречаются довольно-таки редко, их последовательность согласно Википедии, образует вид:
6,
28,
496,
8128,
33 550 336,
8 589 869 056,
137 438 691 328,
2 305 843 008 139 952 128,
2 658 455 991 569 831 744 654 692 615 953 842 176,
Кстати, еще Эйлер доказал, что все совершенные числа имеют только вид 2>p-1(2>p-1). А вот нечетных совершенных чисел пока не обнаружено, но и не доказано что их не существует. Интересно проверить этот факт практически. Совершенное число 137438691328 обнаружил еще немецкий математик Иоганн Мюллер в 16 веке. Сегодня такое число несложно проверить на компьютере.
Во-первых, слегка оптимизируем приведенную выше программу. Как нетрудно видеть, если число N делится нацело на P, то мы “автоматом” сразу находим и второй делитель N/P. Например, если 10 делится нацело на 2, то оно делится и на 10/2=5. Это позволяет заметно сократить число вариантов перебора. Во-вторых, используем тип чисел Decimal, позволяющий использовать большие числа. Обновленная программа выглядит так:
from decimal import *