Рассказы о математике с примерами на языках Python и C | страница 13

В завершение темы простых чисел, приведем вид так называемой “спирали Улама”. Математик Станислав Улам открыл ее случайно в 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 *