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

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

С древних времен известно, что во множестве натуральных чисел встречаются числа, которые делятся только на 1 и на само число. Такие числа назвали простыми.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,…

Еще Эвклид доказал, что простых чисел бесконечно много, но до сих пор не найдена формула, позволяющая вычислять следующее простое число, если известны все предыдущие простые числа. То есть, для того, чтобы найти следующее за простым числом 23 простое число, нужно проверить на делимость нечетные числа 25, 27, 29 и обнаружить, что из их только число 29 не имеет делителей, то есть является простым. Причем, достаточно для числа n проверять его на делимость до числа n/2+1, то есть для числа 29 это проверка до значения делителя 29/2+1=15.

Построение ряда простых чисел

Использование компьютера позволяет выполнять проверку очень быстро, то есть быстро строить ряд простых чисел. Программа, реализующая такую проверку, приведена ниже. В ней последовательно проверяются на простоту все нечетные числа в диапазоне {3...1999}, простые числа выводятся на экран:

REM nat_prost CLS FOR n% = 3 TO 1999 STEP 2    FOR i% = 2 TO n% \ 2 + 1       IF n% / i% = n% \ i% GOTO 1    NEXT i% PRINT n%; 1 NEXT n% END

Нахождение простых чисел - близнецов

Близнецами называют простые числа, разделенные единственным составным числом. В начале ряда натуральных чисел это: …, 3, 4, 5, 6, 7,… Установлено, что близнецы встречаются на всем протяжении исследованного натурального ряда, однако до сих пор не доказано, что близнецов бесконечно много.

Для выделения близнецов в ряду простых чисел воспользуемся цветом. Выделим близнецов желтым цветом с помощью оператора COLOR. В программе используется цикл WHILE … WEND. Условием выхода из цикла является превышение значения переменной nom% >16000. Введена переменная f%, которая в случае появления близнецов принимает значение 1, что вызывает значение параметра COLOR 14 (желтый цвет вывода чисел-близнецов). В противном случае значение параметра COLOR 7 (светлосерый цвет). В результате на экране появляется таблица простых чисел, в которой числа-близнецы выделены цветом.

REM prost_bliz CLS DIM p&(16000) n& = 1 WHILE nom% < 16000 1  n& = n& + 1    FOR i% = 1 TO nom%       IF n& \ p&(i%) = n& / p&(i%) THEN 1    NEXT i%    nom% = nom% + 1    p&(nom%) = n&    IF n& = p&(nom% - 1) + 2 THEN f% = 1: COLOR 14: GOTO 2    IF f% = 1 THEN COLOR 14: f% = 0 ELSE COLOR 7 2  PRINT p&(nom% - 1); WEND END

Результат работы программы - таблица простых чисел (простые числа - близнецы выделены желтым)

Скатерть Улама

Американский математик Станислав Улам, один из пионеров применения компьютеров в математических исследованиях, придумал оригинальный способ представления простых чисел. Как гласит легенда, он, присутствуя на каком-то скучном совещании, стал заполнять лист бумаги в клеточку натуральными числами, располагая их по спирали, а затем отметил простые числа. К его удивлению простые числа образовали на плоскости структуры из наклонных цепочек.

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

С тех пор такая программа создавалась на разных языках программирования (можно даже создать скатерть Улама в программе Microsoft Excel в виде электронной таблицы).

Программа для построения на экране скатерти Улама  для диапазона натурального ряда 1…230400, разработанная автором, приведена ниже. Простые числа изображаются на экране в виде белых точек, а составные в виде черных. Для того чтобы точки изображающие натуральные числа располагались на экране по спирали, в программе используются переменные f1% и f2%, которые принимают значения 1, 0, -1. Умноженные на переменные x% и y% они обеспечивают изменение их значений в нужном направлении. Например, при значении f1%=1, а f2%=0 значение x% меняется на +1, а значение y% остается прежним, то есть следующая точка, изображающая натуральное число расположится справа от предыдущей. Если f1%=0, а f2%=-1 следующая точка расположится сверху от предыдущей и т. п.

Многочлены - генераторы простых чисел

Попробуем разобраться, почему на скатерти Улама так много наклонных цепочек из простых чисел. Для этого определим, как изменяются значения натуральных чисел по диагонали от числа 1 вправо-вверх:

Видно, что это квадраты нечетных чисел 1², 3², 5², 7², 9², …

Действительно, наклонные цепочки чисел на скатерти Улама представляют значения некоторых квадратных многочленов типа:

Но еще великий математик Леонард Эйлер открыл, что многочлен вида:

 e = x² + x + 41 

при значения x от 1 до 39 дает значения e  в виде простых чисел:

• x = 1    e = 43
• x = 2    e = 47
• x = 3    e = 53
• …

При значении x=40 значение e будет составным числом, но и далее в решениях встречается очень много простых чисел, значительно больше, чем в таком же диапазоне натурального ряда. Позже были найдены и другие многочлены, в решениях которых аномально много простых чисел. Таким образом, структура распределения простых чисел на скатерти Улама наглядно показывает совсем не очевидную связь между таким свойством числа как простота и решениями квадратных многочленов.

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

REM Eiler f1% = 1: f2% = 0: x% = 380: y% = 240: p% = 1 SCREEN 12 LOCATE 1, 1: PRINT "Формула Эйлера" z& = 1 e& = z& * z& + z& + 41 FOR n& = 1 TO 230400    IF INKEY$ = "f" THEN 100    LOCATE 3, 5: PRINT "n="; n&    LOCATE 5, 5: PRINT "e="; e&    IF n& = e& THEN z& = z& + 1: e& = z& * z& + z& + 41: GOSUB 200: GOTO 5    col% = 7 5  PSET (x%, y%), col%    x% = x% + f1%    y% = y% + f2%    i% = i% + 1    IF i% MOD p% = 0 AND v% = 0 THEN i% = 0: v% = 1: GOTO 10    IF i% MOD p% = 0 AND v% = 1 THEN p% = p% + 1: i% = 0: v% = 0: GOTO 10 10 IF i% MOD p% = 0 AND f1% = 1 THEN f1% = 0: f2% = 1: GOTO 20    IF i% MOD p% = 0 AND f2% = 1 THEN f2% = 0: f1% = -1: GOTO 20    IF i% MOD p% = 0 AND f1% = -1 THEN f1% = 0: f2% = -1: GOTO 20    IF i% MOD p% = 0 AND f2% = -1 THEN f2% = 0: f1% = 1: GOTO 20 20 NEXT n& 100 INPUT a$ END 200 FOR j& = 2 TO e& \ 2 + 1    IF e& / j& = e& \ j& THEN col% = 14: GOTO 201 NEXT j& col% = 0 201 RETURN

Результат работы программы

В программе Eiler.bas сохранена в основном структура программы Ylam.bas, только вместо определения простоты очередного натурального числа введена строка проверки совпадения очередного натурального числа с очередным решением уравнения Эйлера, а затем проверки этого решения на простоту в подпрограмме, к которой осуществляется переход с помощью оператора GOSUB 200. Если число простое, оно отображается белой точкой, а если составное то темной.

Можно поставить более общую задачу - как отображаются на скатерти Улама решения квадратного многочлена. Для этого создана программа, в которой предусмотрен ввод с клавиатуры значений коэффициентов A, B, C. При разных значениях коэффициентов A, B, C получаются разные изображения. Некоторые из них приведены ниже.

Неожиданно получение упорядоченных структур разного вида при разных значениях коэффициентов A, B, C.

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

Исследования свойств простых чисел имеет и практическое применение. Один из современных методов шифрования информации (метод RSA) основан на невозможности за разумное время разложить достаточно большое составное число на простые сомножители, которые образуют «секретный ключ» системы шифрования. Это дает возможность использовать такое число в качестве так называемого открытого ключа системы шифрования.

Дальнейшие исследования простых чисел

Для дальнейших исследований свойств простых чисел необходимо существенно расширить их диапазон. Для этого мною разработана программа, которая определяет значения простых чисел в диапазоне более трех миллионов. Так как работа такой программы продолжается несколько часов, чтобы ускорить дальнейшие исследования, список простых чисел записывается во внешний файл p.txt из которого такой список прочитать значительно быстрее чем каждый раз создавать его заново. Программа написана на языке Visual Basic, ниже показан ее код и результат ее работы (начало и конец файла со списком простых чисел от 3 до 3734749):

Option Explicit Dim p(300000) As Long Dim i, j, n, x, z As Long Dim r, kol(1000) As Integer Private Sub start_Click() Open "p.txt" For Output As #1 n = 1 Print #1, 2 While x < 300000 n = n + 2 For i = 1 To x If n Mod p(i) = 0 Then GoTo 1 Next i x = x + 1: p(x) = n Print #1, n 1 Wend Close #1 End Sub

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

Назовем количество составных чисел, которые разделяют смежные простые числа расстоянием между ними. Напишем программу, которая бы подсчитывала, сколько в диапазоне 3...3734749 находится пар простых чисел с расстоянием 1 (близнецы), 3, 5 и т.д. Для этого сначала напишем программу на языке QBasic, которая прочитает файл p.txt , выведет на экран и запишет во внешний файл raz.txt таблицу из значений расстояний между простыми числами и количеством пар простых чисел с этим расстоянием:

SCREEN 12 DIM p1, p2 AS LONG DIM r(1000), max, i AS INTEGER CLS OPEN "p.txt" FOR INPUT AS #1 WHILE EOF(1) = 0 INPUT #1, p1, p2 IF p2 - p1 > max THEN max = p2 - p1 r(p2 - p1) = r(p2 - p1) + 1 WEND CLOSE #1 OPEN "razn.txt" FOR OUTPUT AS #2 FOR i = 1 TO max IF r(i) <> 0 THEN LINE (5, i)-(5 + r(i) / 40, i): PRINT #2, i, r(i) NEXT i CLOSE #2 END

Результат работы программы

Рассматривая таблицу - результат работы программы видно, что в исследованном диапазоне простых чисел наиболее часто встречается расстояние между ними 5, затем 11, затем 1 (близнецы), а затем 3. С увеличением расстояния количество чисел уменьшается, а расстояния 113, 115, 121, 123 не встречаются вовсе.