Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

ON THE FEATURE OF THE PRIMES DISTRIBUTION ON THE ULAM SPIRAL

Porshnev S.V. 1
1 Federal State Autonomous Educational Institution of Higher Professional Education «Ural Federal University named after the first President of Russia B.N. Yeltsin»
The issues of the prime number distribution on the Ulam spiral in polar coordinates have been studied. This distribution is a deterministic fractal with Hausdorff dimension 1,75 consisting of 44 pairwise disjoint spirals similar to the Archimedean spiral. The origin of each spiral coincides with the corresponding index of a prime (i = 1, 2..., 44). Prime numbers lie along the spirals by order – that is the spiral with index i contains primes with indices i + 44k, k = 0, 1, ... . The primes of one selected from the detected Archimedean spirals by their number dependence is a deterministic function. This function can be approximated by a polynomial of degree 6. It can be used to estimate the area for search the next prime number belonging to the corresponding Archimedean spiral.
prime numbers
Ulam spiral (Ulam cloth)
fractal dimension
1. Kronover R.M. Fractaly i haos v dinamicheskih sistemax. M.: Texnosfera, 2006. 488 p.
2. Porshnev S.V. Komputernoe modelirovanie phizicheskih processov v pakete MATLAB. Spb.: 2011. рр. 736.
3. O’ Neill M.E. The Genuine Sieve of Eratosthenes// Journal of Functional Programming. Published online by Cambridge University Press. 9 October 2008. Available at: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf (accessed 1 Juny 2013).
4. Stein M.L., Ulam S.M.; Well M.B. (1964), A Visual Display of Some Properties of the Distribution of Primes, American Mathematical Monthly (Mathematical Association of America). 1964. Vol. 71 (5). рр. 516–520.
5. Stein M., Ulam S.M. An Observation on the Distribution of Primes, American Mathematical Monthly (Mathematical Association of America). 1967. Vol. 74 (1). рр. 43–44.

Скатерть Улама - двумерная плоскость, на которой, начиная с единицы, последовательно по спирали записываются члены натурального ряда (первый этап) и далее из рассмотрения исключаются составные числа (второй этап) (рис. 1). Процедура исключения эквивалентна размещению в ячейках, содержащих составные числа, белых квадратов, в ячейках, содержащих простые числа - черных квадратов. Полученная таким образом фигура в русскоязычной литературе носит название скатерти Улама, в англоязычной литературе - спирали Улама. Один из наиболее известных результатов изучения особенностей распределения простых чисел на скатерти Улама в декартовой системе координат [4, 5] состоит в том, что имеет место некоторая упорядоченность простых чисел - часть из них группируется вдоль диагональных прямых (рис. 2).

pic_29.tif pic_30.tif

Рис. 1. Создание спирали Улама (слева – первый этап, справа – второй этап)

pic_31.tif

Рис. 2. Скатерть Улама (общее число членов натурального ряда 105, простых чисел ‒ 9593)[1]

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

Материалы и методы исследования

В нашем исследовании мы использовали пакет MATLAB, в котором была создана функция Eratosphen(), реализующая известный алгоритм «Решето Эратосфена» [3]. Входным параметром данной функции является число членов натурального ряда N, среди которых ищутся простые числа. Функция возвращает вектор-строку длиной N, в которой все составные числа натурального ряда заменены нулями.

Листинг файла Eratosphen.m

pic_32.wmf

Ниже представлен результат, возвращаемый функцией Eratosphen().

pic_33.wmf

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

pic_34.wmf

Далее в полярной системе координат поточечно визуализировалась зависимость значения простого числа от его порядкового номера.

Результаты исследования и их обсуждение

Рассмотрим результаты компьютерного моделирования распределения простых чисел на скатерти Улама в полярной системе координат, представленные на рис. 3. Из рис. 3 видно, что форма распределения простых чисел на скатерти Улама в полярной системе координат при изменении масштаба графика остается неизменной. Таким образом, в полярной системе координат распределение простых чисел оказывается детерминированным фракталом. Значение его фрактальной размерности, полученное в соответствие с алгоритмом Минковского [1], программная реализация которого в пакете MATLAB приведена в [2], оказалось близким 1,75.

аpic_35.tifбpic_36.tifвpic_37.tif

Рис. 3. Распределение простых чисел на скатерти Улама в полярной системе координат:а – N = 103; б – N = 104; с – N = 105

Также необходимо отметить, что распределение простых чисел на скатерти Улама состоит из 44 спиралей, подобных спиралями Архимеда. Начальная точка каждой спирали совпадает с соответствующим порядковым номером простого числа (i = 1,2,… 44). Простые числа располагаются вдоль спиралей упорядочено - i-й спирали принадлежат числа с номерами i + 44k, k = 0,1,… Примеры зависимостей значений простых чисел, принадлежащих соответствующей спирали, от их порядкового номера представлены на рис. 4 (здесь была использована последовательность, состоящая из N = 107, в которой находится 664581 простых чисела). Из рис. 4 видно, что для простых чисел, принадлежащих i-й спирали, зависимость между значением простого числа и его порядковым номером можно описать, используя для этого аппроксимирующий полином относительно невысокой степени (рис. 5). Данные полиномы, построенные для K простых чисел, можно также использовать для оценки области поиска простых чисел.

а pic_38.tif б pic_39.tif

в pic_40.tif г pic_41.tif

Рис. 4. Зависимость простого числа, принадлежащего i-й спирали от его порядкового номера(по обеим координатным осям использованы логарифмические шкалы):а – i = 1; б – i = 10; в – i = 20; г – i = 44

pic_42.tif

Рис. 5. Зависимость простого числа, принадлежащего спирали i = 1, от его номера и результаты аппроксимации данной зависимости полиномом 6-й степени (внизу ‒ остатки модели)

Заключение

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

Приложение. Алгоритм визуализации скатерти Улама и его программная реализация

Для построения алгоритма визуализации скатерти Улама рассмотрим рис. 1. Обозначим единичные шаги вправо, вверх, влево и вниз буквами П, В, Л, Н соответственно. В выбранных обозначениях перемещение из точки 1 в точку 7 (первый виток спирали) будет описываться следующий правилом:

ПВЛЛНН, (1)

из точки 7 в точку 21 (второй виток спирали):

ПППВВВЛЛЛЛНННН, (2)

из точки 21 в точку 43 (третий виток спирали):

ПППППВВВВВЛЛЛЛЛЛНННННН. (3)

Из приведенных выше правил видно, что число шагов в каждом из направлений на k + 1-м витке спирали зависит от числа шагов на k-м шаге спирали:

Шk + 1 = Шk + 2, (4)

где Ш = П, В, Л, Н.

Из приведенного выше описания алгоритма видно, что (1) в терминологии L-систем (Лиденмайер, 1968) [4] - есть аксиома, а (4) - порождающее правило. Соответственно, для визуализации скатерти Улама следует использовать технологию терл-графики [4] (от turtle - черепашка), в которой основным исполнителем является черепашка (точка), которая перемещается по экрану дискретными шагами, прочерчивая или не прочерчивая (как в нашем случае) свой след. «Мгновенное» положение черепашки задается тремя параметрами (x, y, a), где (x, y) - координаты черепашки, a - направление следующего шага. Последовательность команд, определяющих направление перемещения и действия черепашки, задается кодовым словом, буквы которого читаются справа налево. (Примеры программных реализаций алгоритмов терл-графики, используемых для визуализации изображений детерменированных фракталов, можно найти в [5].) Отметим, что здесь наиболее затратной с вычислительной точки зрения оказывается процедура вычисления порождающего правила, представляющего собой рекурсивную процедуру. При построении скатерти Улама вследствие относительной простоты алгоритма перемещения оказывается возможным обойтись без использования рекурсивной процедуры.

Листинг файла Ulam.m

pic_42.wmf
pic_42.wmf
pic_43.wmf

Рецензенты:

Доросинский Л.Г., д.т.н., профессор, зав. кафедрой информационных технологий, ГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург;

Суханов В.И., д.т.н., доцент, зав. кафедрой микропроцессорной техники, ГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.

Работа поступила в редакцию 15.07.2013.


[1] Алгоритм визуализации скатерти Улама и его программной реализации, созданной в пакете MATLAB, представлен в приложении.