Главная » Файлы » Библиотека » Науки, Образование

ПЕРВЫЕ 50 МИЛЛИОНОВ ПРОСТЫХ ЧИСЕЛ
[ Скачать с сервера (51.0 Kb) ] 13.12.2009, 23:49
ПЕРВЫЕ 50 МИЛЛИОНОВ ПРОСТЫХ ЧИСЕЛ
Дон Цагир
Мне хотелось бы поговорить с вами об одной проблеме, которая, хотя сам я над ней и не работал, всегда меня чрезвычайно привлекала и которая очаровывала математиков, пожалуй, с доисторических времён и до наших дней, – а именно о проблеме распределения простых чисел.
Вам, конечно, известно, что простым числом называется отличное от 1 натуральное число, не делящееся ни на какие иные натуральные числа, кроме 1; во всяком случае, именно такое определение дают специалисты по теории чисел. Правда, другие математики иногда используют и иные определения. Так, для специалиста по теории функций простое число – это целочисленный нуль аналитической функции

sin  pG(s)
s
sin  p
s

Для алгебраиста – это
«характеристика конечного поля» 1,
или
«точка из spec Z» 2,
или
«неархимедово нормирование» 3.
Для специалиста по комбинаторике простые числа определяются рекуррентной формулой [1]

  n  
 pn+1 =    1 – log 2  ( 1
2  +  å å (–1)r
2  p i1 ...  p ir  – 1
)  
  r = 1      1 £ i1 £ ... £ ir £ n       
где [x] – целая часть числа x 4. И, наконец, логики определяют в последнее время простые числа как положительные значения многочлена [2]
F(a, b, с, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z) =
    = {k + 2} {1 – (wz + h + j – q)2 – (2n + p + q + z – e)2
    – (a2y2 – y2 + 1 – x2)2 – ({e4 + 2e3}{a + 1}2 – o2)2
    – (16{k + 1}3{k + 2}{n + 1}2 + 1 – f 2)2
    – ({(a + u4 – u2a)2 – 1}{n + 4dy}2 + 1 – {x + cu}2)2
    – (ai + k + 1 – l – i)2
    – ({gk + 2g + k + 1}{h + j} + h – z)2
    – (16r2y4{a2 – 1} + 1 – u2)2
    – (p – m + l{a – n – 1} + b{2an + 2a – n2 – 2n – 2})2
    – (z – pm + pla – p2l + t{2ap – p2 – 1})2
    – (q – x + y{a – p – 1} + s{2ap + 2a – p2 – 2p – 2})2
    – (a2l2 – l2 + 1 – m2)2 – (n + l + v – y)2}.
Но я думаю, вы вполне удовлетворены первым из приведённых мной определений.
Имеются два главных факта о распределении простых чисел, о которых я надеюсь рассказать вам так, чтобы они навек запечатлелись в вашей памяти. Первый: простые числа, при своём таком простом определении и при своей роли кирпичиков, из которых строятся все натуральные числа 5, являются самыми капризными и упрямыми из всех объектов, вообще изучаемых математиками. Они растут среди натуральных чисел как сорная трава, не подчиняясь, кажется, ничему, кроме случая, и никто не может предсказать, где взойдет ещё одно простое, а, увидев число, – определить, простое оно или нет. Другой факт озадачивает ещё больше, так как он состоит в прямо противоположном утверждении, а именно: простые числа демонстрируют удивительную регулярность, они подчиняются законам, и притом с почти педантичной точностью.
Чтобы пояснить первое утверждение, я покажу вам список простых и составных чисел, не превосходящих 100 (табл.1), причём, за исключением числа 2, приведены лишь нечётные числа, а затем список простых из ста натуральных чисел, предшествующих и следующих за 10 000 000 (табл.2).
Таблица 1. Простые и (нечётные) составные числа от 1 до 100.

простые составные
2
3
5
7
11
13
17 19
23
29
31
37
41
43 47
53
59
61
67
71
73 79 
83 
89 
97  9
15
21
25
27
33
35 39
45
49
51
55
57
63 65
69
75
77
81
85
87 91 
93 
95 
99 

Таблица 2. Простые числа в интервалах длины 1000 слева и справа от 10 миллионов.

между
 9 999 900   и   10 000 000  между
 10 000 000   и   10 000 100 
9 999 901
9 999 907
9 999 929
9 999 931
9 999 937
9 999 943
9 999 971
9 999 973
9 999 991 10 000 019
10 000 079

Полагаю, вы согласитесь, что нет явно видимой причины, по которой одно число является простым, а другое – нет. Напротив, при взгляде на эти таблицы возникает ощущение, будто стоишь перед непостижимой тайной творения. Что и математики до сих пор ещё не раскрыли эту тайну, пожалуй, наиболее убедительно подтверждает то усердие, с которым они и поныне ищут всё бульшие простые. Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Например в 1876 г. Люка доказал, что число 2127 – 1 – простое [См. подробности в статье А. Н. Рудакова. – E.G.A.], и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если взглянуть на него:
2127 – 1 = 170141183460469231731687303715884105727.

Только в 1951 г. – после возникновения электронных вычислительных устройств – нашли бульшее простое число. Сведения о сменявших друг друга числах-рекордсменах вы найдете в табл.3 [3]. В настоящее время рекордсменом является 6002-значное число 219937 – 1 (я бы не хотел его здесь выписывать); счастливчик, оно может гордиться своей славой 6. Кто сомневается в сказанном, может справиться в книге мировых рекордов Гиннесса.
Таблица 3. Наибольшее известное простое число.

p число цифр
в числе p год
открытия кто открыл
2127 – 1 39 1876 Люка
(2148 + 1)/17 44 1951 Феррье
114(2127 – 1) + 1
180(2127 – 1)2 + 1 41
79 1951 Миллер + Уиллер + EDSAC 1
2521 – 1
2607 – 1
21279 – 1
22203 – 1
22281 – 1 157
183
386
664
687 1952 Лемер + Робинсон + SWAC
23217 – 1 969 1957 Ризель + BESK
24253 – 1
24423 – 1 1281
1332 1961 Хурвитц + Селфридж + IBM 7090
29689 – 1
29941 – 1
211213 – 1 2917
2993
3376 1963 Гиллис + ILIAC 2
219937 – 1 6002 1971 Таккермэн + IBM 360

Однако гораздо интереснее вопрос о законах, которым подчиняются простые числа. Я привёл вам ранее в табл.1 список простых чисел между 1 и 100. На рис.1 та же информация представлена графически, функция p(x), о которой теперь пойдёт речь, выражает количество простых чисел, меньших или равных x; следовательно, в нуле она имеет значение 0 и скачком увеличивается на 1 в точках x = 2, 3, 5 и т.д., т.е. когда x равно простому числу. Уже из этого графика видно, что растёт p(x), несмотря на малые локальные колебания, в общем, довольно регулярно. Если же увеличить область изменения x до 50 000, то регулярность эта становится настолько отчётливой, что дух захватывает (рис.2). По-моему, плавность, с которой поднимается эта кривая, следует отнести к числу удивительнейших фактов математики.


Рис.1. Функция p(x) при x £ 100.
Рис.2. Функция p(x) при x £ 50000.

Но где закономерность, там и учёные, которые пытаются её разгадать. И данный случай не стал исключением. Нетрудно найти эмпирическую формулу, хорошо описывающую рост количества простых чисел. От 1 до 100 имеется 25 простых чисел, т.е. четверть всех чисел; до 1000 их 168, т.е. около одной шестой; до 10 000 их 1229, т.е. примерно одна восьмая. Продолжая вычисления до 100 000, 1 000 000 и т.д. и определяя каждый раз отношение количества простых к количеству всех натуральных чисел, получим данные, приведённые в табл.4.
Таблица 4.

x  p(x)         x/p(x)        
10 4 2,5
100 25 4,0
1 000 168 6,0
10 000 1 229 8,1
100 000 9 592 10,4
1 000 000 78 498 12,7
10 000 000 664 579 15,0
100 000 000 5 761 455 17,4
1 000 000 000 50 847 534 19,7
  10 000 000 000         455 052 512 22,0

(Так скромно выписанные в ней значения p(x) потребовали тысяч часов трудоёмких вычислений.) Видно, что отношение x к p(x) при переходе от данной степени десяти к последующей всё время увеличивается примерно на 2,3. Математики сразу узнают в числе 2,3 логарифм 10 (разумеется, по основанию e). В результате возникает предположение, что

p(x) ~  x
 ln x ,

причем знак ~ означает, что отношение соединённых им выражений с ростом x стремится к 1. Это асимптотическое равенство, впервые доказанное в 1896. г., называется в настоящее время законом распределения простых чисел. Гаусс, величайший из математиков, открыл этот закон в пятнадцатилетнем возрасте, изучая таблицы простых чисел, содержавшиеся в подаренной ему за год до того таблице логарифмов. В течение всей своей жизни Гаусс живо интересовался распределением простых чисел и проводил обширные вычисления для выяснения этого вопроса. В своём письме к Энке [4] Гаусс описывает, как он «очень часто употреблял свободные четверть часа, чтобы то там, то здесь просчитать хилиаду» (т.е. интервал в 1000 чисел), и так до тех пор, пока он не нашёл, наконец, все простые, меньшие трёх миллионов (!), и не сравнил полученные результаты с предполагаемой формулой их распределения.

Категория: Науки, Образование | Добавил: NATALYA | Теги: математика
Просмотров: 2071 | Загрузок: 226 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *: