Рассказы о математике с примерами на языках Python и C - [5]

Читая труды по географии, Эратосфен нашел интересный факт — в городе Сиене в день летнего солнцестояния Солнце стоит так высоко, что предметы в полдень не отбрасывают тени. Другой может и не обратил бы на это внимание, но Эратосфен не зря интересовался и математикой и астрономией. Он знал что в его городе Александрии тень в этот же день имеет другой угол. Эратосфен дождался солнцестояния, измерил угол солнечных лучей и получил величину 7,2 градуса.

Что это значит? Объяснение данному факту могло быть только одно — Земля круглая, и угол падения солнечных лучей в разных точках Земли в одно время различается.

Картинка с сайта physicsforme.com

Дальше, как говорится, дело техники. Зная примерное расстояние между Сиеном и Александрией (которое было известно из времени в пути каравана верблюдов) и угол, легко получить длину всей окружности. К чести Эратосфена, его результат отличается от сегодняшнего всего лишь на 1%. Так, задолго до эпохи авиации и воздухоплавания, человек впервые смог измерить радиус планеты, даже при этом не отрываясь от нее. Увидеть настоящую кривизну Земли сумели лишь пилоты стратостатов в начале 20 века, более чем через 2000 лет после описанного опыта.

Разумеется, повторить подобный эксперимент сегодня легко может любой школьник. Нужно лишь сделать простейший угломер из транспортира и отвеса, и с помощью знакомых в другом городе, сделать измерения высоты Солнца в двух точках в одно и то же время.

5. Простые числа

Каждый знает, что простые числа — такие числа, которые делятся только на единицу и самих себя. Но так ли они просты, как кажутся, и актуальны ли сегодня? Попробуем разобраться.

То, что существуют числа, которые не делятся ни на какое другое число, люди знали еще в древности. Последовательность простых чисел имеет следующий вид:

1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Доказательство того, что этих чисел бесконечно много, дал еще Евклид, живший в 300 г. до н. э. Примерно в те же годы уже известный нам греческий математик Эратосфен, придумал довольно-таки простой алгоритм получения простых чисел, суть которого была в последовательном вычеркивании чисел из таблицы. Те оставшиеся числа, которые ни на что не делились, и были простыми. Алгоритм называется «решето Эратосфена» и за счет своей простоты (в нем нет операций умножения или деления, только сложение) используется в компьютерной технике до сих пор.

Видимо, уже во время Эратосфена стало ясно, что какого-либо четкого критерия, является ли число простым, не существует — это можно проверить лишь экспериментально. Существуют различные способы для упрощения процесса (например, очевидно, что число не должно быть четным), но простой алгоритм проверки не найден до сих пор, и скорее всего найден не будет: чтобы узнать, простое число или нет, надо попытаться разделить его на все меньшие числа.

Это несложно записать в виде программы на языке Python:

import math

def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

# Вывод всех простых чисел от 1 до N
N = 100
for p in range(1, N, 2):
    if is_prime(p): print(p)

# Вывод результата, является ли заданное число простым
print(is_prime(2147483647))

Желающие могут поэкспериментировать с программой самостоятельно.

Подчиняются ли простые числа каким-либо законам? Да, и они довольно любопытны. Так, например, французский математик Мерсенн еще в 16-м веке обнаружил, что много простых чисел имеет вид 2^N - 1, эти числа названы числамиМерсенна. Еще незадолго до этого, в 1588 году, итальянский математик Катальди обнаружил простое число 2¹⁹ - 1 = 524287 (по классификации Мерсенна оно называется M19). Сегодня это число кажется весьма коротким, однако даже сейчас с калькулятором проверка его простоты заняла бы не один день, а для 16 века это было действительно огромной работой. На 200 лет позже математик Эйлер нашел другое простое число 2³¹ - 1 = 2147483647. Необходимый объем вычислений каждый может представить сам. Он же выдвинул гипотезу, названную позже «проблемой Эйлера», или «бинарной проблемой Гольдбаха»: каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел. Например, можно взять 2 любых четных числа: 123456 и 888777888. С помощью компьютера можно найти их сумму в виде двух простых чисел: 123456 = 61813 + 61643 и 888777888 = 444388979 + 444388909. Интересно здесь то, что точное доказательство этой теоремы не найдено до сих пор, хотя с помощью компьютеров она была проверена до чисел с 18 нулями.

Существует и другая теорема, называемая теоремой Ферма-Эйлера, открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4 * k + 1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4 * 111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197 * 19197 + 8710*8710. Теорема была доказана Эйлером лишь через 100 лет.

И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.