1 - 2010

Последовательность, почти всегда возвращающая простые числа

Тимофей Приходько (Технологический институт ВТУ, старший преподаватель)

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

О важности простых чисел в математике говорит основная теорема арифметики: любое число можно представить в виде произведения простых множителей. Вся математика опирается на простые числа, но закономерности появления их в натуральном ряду так никто еще и не объяснил.

Математики всего мира не раз пытались найти ту формулу, при вычислениях по которой всегда получались бы простые числа. Если в этой фразе отбросить слово «всегда», то таких формул удастся привести довольно много, например: f(n)=n2 + n + 17; f(n) = n2 – n + 41; f(n) = 2n2 + 29.

Последовательно подставляя, например, в первую формулу вместо n натуральные числа, получим числа 19, 23, 29, 37. Все они являются простыми, но торжествовать рано — уже f(16) = 289 = 172, то есть получилось составное число.

Эти формулы порождают много простых чисел, но это «много» еще не означает «всегда»! Более того, можно доказать, что никакой многочлен с целыми коэффициентами не может для всякого натурального значения n равняться простому числу.

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

Полотно Улама

Так чем же объясняются закономерности в распределении простых чисел? Пока ответа на этот вопрос нет, но все же есть множество визуальных наблюдений. Одну из таких закономерностей случайно открыл Станислав Улам, американский математик, поляк по происхождению. Сидя как­то на скучной лекции, он, ни о чем не думая, начал рисовать решетку из горизонтальных и вертикальных линий. В одной из полученных таким образом клеток он поставил 1 и стал нумеровать остальные клетки по спирали, расходящейся от первой клетки:

5 4 3

6 1 2

7 8 9

Когда спираль совершила несколько оборотов, Улам начал обводить кружками простые числа, не преследуя никакой определенной цели. Однако вскоре заметил, как на его глазах возникает довольно любопытная закономерность. Откуда ни возьмись, стали появляться прямые линии. Улам, конечно, сразу понял, что такие линии говорят о закономерности, которую можно облечь в формулу для простых чисел.

Составление формулы простого числа

Чтобы увидеть всё своими глазами, а не полагаться только на слова, составим простую компьютерную программу, которая бы рисовала точку в центре, а вокруг нее по спирали располагала бы все числа натурального ряда. Программа будет отмечать черным цветом точки, соответствующие простым числам, а серыми — составные. Вот что мы получим:

У самого центра диаграммы одна такая закономерность пролегает сверху вниз и слева направо. Она состоит из последовательности чисел: 7, 23, 47, 79... Оказывается, эту последовательность можно описать квадратичной функцией р = 4х2 + 4х – 1.

С помощью этого графика можно задать формулой любую последовательность простых чисел. Рассмотрим, например, последовательность, берущую свое начало из точки 5 и идущую справа налево сверху вниз. Следующее число в этой последовательности 19, затем идут 41, 71… Попробуем описать ее рекуррентной формулой. Для этого сначала рассмотрим каждый квадрат, состоящий из точек. У любого такого квадрата на восемь точек больше, чем у вложенного в него, — это очень легко доказать. Значит, разность между любыми двумя точками, лежащими в соседних квадратах по одному правилу, будет увеличиваться на восемь по сравнению с предыдущими. Для определенности за отношение «лежать по одному правилу» примем точки, лежащие в соседних квадратах, причем из точки, лежащей в меньшем квадрате,  можно перейти к точке из большего квадрата, если перейти в другой квадрат по кратчайшему расстоянию и затем сместиться на число t, где t целое, причем t — постоянное число для данного правила. В нашем случае t = 1.

Если разность между точками, лежащими в 1­м и 2­м квадратах от центра, равна 14, то разность между точками 2­го и 3­го квадратов возрастет на 8 и будет равна 22. Теперь можно составить формулу: следующий член последовательности будет отличаться от предыдущего на 14 + 8·n, где n — номер члена последовательности, то есть номер квадрата от центра. Если считать 5 нулевым членом и каждый член больше предыдущего на 8·(n – 1), где n — номер квадрата, то получим:

xn = xn – 1 + 14 + 8(n – 1)

xn = xn – 1 + 8n + 6

Это и есть формула данной последовательности.

И таким образом можно составить сколько угодно формул последовательностей простых чисел, но всегда на каком­то номере окажется, что число вовсе не простое. Примечательно, что если в качестве начальной точки взять число не 1, а 41, то мы увидим последовательность, состоящую из 41 простого числа!

Никакая целая рациональная функция от х с целыми коэффициентами не может для любого натурального значения х равняться простому числу (теорема Гольбаха).

САПР и графика 1`2010