Спираль Улама, области запрета простых чисел

в 14:32, , рубрики: информационная безопасность, криптография, математика, простые числа

     Каждое натуральное число обладает очень многими известными и, по-видимому, еще в большем числе неизвестными свойствами. Четные — нечетные, простые — составные, рациональные — иррациональные, целые — дробные, конечные — бесконечные и др. свойства способствуют введению классификации чисел, некоторого порядка в их множестве. Традиционный подход предполагает, что не располагая самим числом (его значением) невозможно определить и его свойства. Но это не совсем так. Ряд полезных свойств для некоторых чисел можно определять не зная их значений, но имея данные об их положении в натуральном ряде чисел (НРЧ). Простыми числами, кроме 2, могут быть только нечетные, а их положение НРЧ определяется нечетной позицией. Сами эти позиции не все равнозначны. Про некоторые большие нечетные N(x1, x2) числа (разумеется в нечетных позициях НРЧ) можно, не пользуясь традиционными (вероятностными) и детерминированным (весьма трудоемким) алгоритмами, однозначно утверждать, они не могут быть простыми.

     Устройство НРЧ, положение чисел в НРЧ и их свойства

     Будем рассматривать связь свойств натуральных чисел и их положения в НРЧ, считая связь существующей.
     Например, нечетное число, равное четному квадрату без единицы, всегда составное: х&sup2 -1 = (х +1)(х -1). Нечетный квадрат — число составное. Информацию об этом в удобной форме как раз и предоставляет модель НРЧ — спираль Улама, где положение всех квадратов однозначно определено. Следовательно, описанные диагональные лучи, прижатые к диагоналям квадратов, простых чисел содержать не могут. Кроме упомянутых линий, ниже укажем на другие, обладающие этим же свойством. Это свойство модели ранее ни самим Уламом, ни другими авторами, которые с моделью работали или упоминали ее в публикациях, не отмечалось. Загадки большой в этом нет. Отождествим точку (клетку) с координатами (x1, x2) плоскости спирали и число N(x1, x2) в этой позиции.
     Факт существования запретной области для простых чисел в НРЧ установлен из наблюдений спирали, а затем подтвержден (доказан) автором математическими средствами. Полезность этого свойства не очевидна. Но для нечетных чисел, положение клеток (x1, x2) которых в спирали принадлежит области запрета простых чисел, устанавливается не только их не простота, но и факторизуются они без проблем.
     На основе этого факта о некоторых нечетных числах N(x1, x2) даже очень большой разрядности можно с достоверностью единица утверждать, что они составные и затем легко их факторизовать.

      Система координат модели. При использовании концепции контурного строения НРЧ в предыдущей работе «Модель натурального ряда чисел (НРЧ). Спираль Улама» автором предложена система координат на плоскости спирали. За начало координат принят центр спирали. Система скорее ближе к полярной, чем к декартовой.Роль первой координаты х1 числа N(x1, x2) отведена номеру контура (х1 = k). Вторая координата х2 < L(k), где L(k) — длина контура, определяет удаленность клетки с числом N(x1, x2) от начала контура. Для удобства читателя автор сохранил рисунки предыдущей работы в этой.

Спираль Улама, области запрета простых чисел
   Рисунок 1 -Модель НРЧ и увеличеный фрагмент центральной части спирали
  На рисунке 1 из фрагмента НРЧ (399х399 клеток), вырезается центральная часть с числом клеток 19х19 = 361 и приводится справа увеличенный фрагмент с заполнением клеток (x1, x2) числами. На рисунке (с числами) даже в ограниченном объеме хорошо просматриваются вертикальные и горизонтальные одинарные и сдвоенные полосы (магистрали), не содержащие закрашенных клеток, т.е. простых чисел. Ниже на рисунке 2 при внимательном его рассматривании эти магистрали также можно увидеть.
Спираль Улама, области запрета простых чисел
Рисунок 2 — Представление моделью спирали фрагмента (200х200 клеток) натурального ряда с закрашенными клетками для простых чисел.
     При манипулировании с простыми числами полезно знать и располагать сведениями о некоторых их свойствах и зависимостях. Например, то что квадраты простых, например p и q чисел, кроме 2, при сравнении по модулю 8 имеют всегда один вычет 1, р&sup2 ≡ 1(mod8), а по модулю 30 таких вычетов может быть только два 1 и 19: р&sup2 ≡ 1(mod30) или q&sup2 ≡ 19(mod30). Приведем более подробные сведения о числе 30, которые кое-что проясняют нам относительно такой загадочности в поведении простых чисел, их полных квадратов. Это число 30 = 2∙3∙5 играет заметную роль при изучении простых натуральных чисел.
     Число 30 самое большое число, для которого все взаимно простые с ним и меньшие его числа являются простыми. Числу 30 предшествует с таким же свойством число 24, которое также играет в теории чисел существенную роль.

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

    &nbspДля нас более привычно воспринимать натуральные числа как элементы линейной модели. Это удобно, так как на числовой оси все точки имеют одну единственную координату, более того, значение этой координаты совпадает с самим числом. Манипулируя с данными не надо задумываться, что обрабатывается — координата или само число. Не так на пллоскости. Точка ее имеет три характеристики: две координаты (х1, х2) и значение числа N(х1, х2) в точке, которое в нашей модели является функцией координат. Поэтому установим некоторые связи двух моделей линейной и плоской спирали. Понятие контура вводится в обеих моделях одинаково — начало контура нечетный квадрат. Длина контура кратна числу 8. Числа, образующие контур, — это отрезок натурального ряда.

     Натуральные числа могут быть представлены такой аналитической моделью:
30k, 30k&plusmn1, 30k&plusmn2, 30k&plusmn3,...,30k&plusmn15, k=1(1)∞, из них простые числа представляются только в виде соотношений 30k&plusmn1, 30k &plusmn7, 30k&plusmn11, 30k&plusmn13. Из них 8 простых чисел при k = 0,1 числа 7,11,13,17,19,23,29 и 31 ≡ 1(mod30) образуют мультипликативную группу вычетов по модулю 30. Порядок такой группы равен значению функции Эйлера ф(30)=ф(2)ф(3)ф(5) = 8. Такие группы называют группами Эйлера.
      Теперь о числе 24. Покажем, что при простых числах p, q > 3 разность квадратов двух простых p&sup2 — q&sup2 всегда делится на 24. Рассмотрим две тройки смежных чисел (р-1)р(р+1) и тройку (q-1)q(q+1), где р и q простые. В каждой тройке одно из чисел кратно трем и это не р и не q. Следовательно, кратны трем оба произведения (р -1)(р+1) и (q -1)(q+1), которые образованы парами последовательных четных чисел. Но для таких чисел известно, что одно из них кратно двум, а другое четырем. Отсюда следует, что оба произведения делятся на 8. Но они делятся и на три. Тогда каждое из произведений делится на 24. Разность произведений скобок (р -1)(р+1) — (q -1)(q+1) также должна делится на 24, а это и есть разность квадратов p&sup2 — q&sup2. Знание этого факта позволяет при одном известном квадрате тестировать другой. Это не исключает кратности разности квадратов обычных нечетных чисел числу 24, например, 225 — 81 =144 = 6∙24, но не гарантирует ее 1225 — 441 = 484 ≠ 24k, для разности квадратов обычного нечетного и простого чисел , 225 — 49 = 176 ≠ 24k. Для квадратов простых это гарантируется.

      И еще о значениях последовательных n-го и (n+1)-го простых чисел. Евклид доказал, справедливость соотношения для простых чисел р(n+1) < p(1)∙p(2)∙p(3)∙..∙p(n), где величины в скобках обозначают порядковые номера простых чисел. Это достаточно грубая оценка. Позже было показано, что при n > 4, соотношение принимает вид p(n+1)&sup2 < p(1)p(2)p(3)...p(n), т.е. уже для
p(5)&sup2 = 11&sup2 = 121< p(1)∙p(2)∙p(3)∙p(4)=2∙3∙5∙7 = 210;
p(5) =11< √(p(1)∙p(2)∙p(3)∙p(4))=√(2∙3∙5∙7) =√210. Это существенно улучшенная оценка.
П.Л. Чебышев доказал еще более сильный результат р(n+1) < 2р(n).

         &nbsp   Области плоской модели, исключающие появление в них простых чисел

     Теперь более внимательно присмотримся к лучам, выходящим из центральной части спирали и другим, которые упоминались ранее и также не содержащим клеток с простыми числами
      Назовем вертикальные и горизонтальные линии спирали «магистралями», а простые числа в их клетках «светофорами», ограничивающими скорость движения вдоль линий. Тогда на спирали можно указать специфические «скоростные» магистрали, идущие в направлении от центра в четырех направлениях: «Север – Юг» и «Запад – Восток», совсем не содержащие светофоров. Клетки этих магистралей заполняются только составными числами, т. е. не содержат простых чисел. Сам по себе факт достаточно замечательный и даже удивительный, возможно, содержит «намек» на природу и распределение простых чисел в НРЧ. Еще более удивительно то, что на Юг и Восток магистрали содержат по две смежные полосы, а на Север и Запад по одной. В пределах k-го контура обозначим клетки, принадлежащие магистралям символами сторон света: С(k) — северная магистраль; З(k) — западная магистраль; Ю1(k) — южная первая магистраль и Ю2(k) — южная вторая магистраль; B1(k) — восточная первая магистраль и B2(k) — восточная вторая магистраль.

     Теоретически магистрали из трех полос маловероятны, так как полоса перпендикулярного к магистралям направления (как и все другие) в трех смежных клетках содержит смежные натуральные числа. Среди таких чисел одно из трех всегда кратно трем, т. е. составное, а два из них либо четные, либо нечетные. Пусть кратное трем число в клетке на обочине двухполосной магистрали. Тогда четвертое число в контуре через две клетки также будет кратно трем.Следовательно, через две клетки от числа клетка на другой обочине содержит также составное число, которое в каком-то положении может оказаться простым. Четные и нечетные числа в клетках двухполосной магистрали размещаются в шахматном порядке и, видимо, существует закон управляющий заполнением нечетных клеток магистралей, исключающий появление в них простых чисел.
     Пары нечетных чисел в смежных клетках разных магистралей оказываются кратными последовательно возрастающим 3,5,7,9,… нечетным числам:
(27,51):3; (85,125):5; (175,231):7 ;(297, 369 ):9......(восточное направление); 51 =27 + 24; 125 = 85 +40;
231 = 175 + 56; 369=297 +72 прирост значений кратен числу 8 с кратностью-делителем чисел.
(21,45):3;(75,115):5; (161,217):7; (279,351): 9; …(южное направление).
     Описание всего бесконечного множества клеток магистралей оказывается более простым, чем для клеток вне магистралей. Одной координаты – номера контура k спирали достаточно, чтобы определить число в клетке магистрали, принадлежащее заданному номером k контуру. При этом используются следующие зависимости (см. таблицу).

Таблица. Расчетные характеристики клеток магистралей спирали Улама
Спираль Улама, области запрета простых чисел

     Формулы, приведенные в таблице, гарантируют при задании номера k контура неограниченное продолжение полос с сохранением отмеченных свойств полос и чисел в них. Особенно важным свойством представляется свойство делимости нечетных чисел в клетках, формирующих полосы. В каждом контуре при заданном его номере k по формулам из таблицы определяются значения чисел в шести клетках пересечения магистралей с контуром. Все эти числа, назовем их реперами , составные и их делители известны. Формулы, приведенные в таблице уже содержат описания каждого делителя.
     Другие числа k-го контура (вида репер &plusmn t∙делитель репера) также можно подвергнуть процедуре факторизации при выполнении некоторых условий.

     К таким условиям отнесем следующие. Испытуемое число отличается от репера на величину кратную меньшему или большему делителю. Для таких чисел факторизация выполняется без проблем. Важным представляется свойство делимости нечетных чисел в клетках, формирующих полосы. Следовательно, в каждом контуре найдется более 8 клеток, содержащих нечетные числа, которые не могут быть простыми, так как в выражении (репер &plusmn t∙делитель репера) общий делитель выносится за скобку.

     Помимо рассмотренных магистралей существуют линии (диагонали) нечетных чисел также не содержащие простых чисел. Во-первых, такая нечетная диагональ — диагональ нечетных квадратов. К ней до и после нее прижаты четные диагонали, которые с очевидностью простых чисел не содержат. В каждом контуре при этом появляются по три смежных клетки без простых чисел. Во-вторых, еще три смежные клетки без простых чисел в каждом контуре появляются по соседству с диагональю четных квадратов. Этой диагонали предшествует нечетная диагональ, в которой как мы сейчас покажем все клетки заняты составными числами. Значения в клетках этой диагонали равны четному квадрату (2k)&sup2 — 1 без единицы. Но такое соотношение всегда раскладывается в произведение двух скобок — сумма с единицей на разность с единицей первой степени четного квадрата контура, (2k +1)(2k — 1 ).
      Пример . Пусть задано число N = 4294967297 = F5. Требуется определить его положение в модели, т. е. (х1, х2) координаты клетки с этим числом, а также значения и положения шестерки чисел, принадлежащих этому контуру, на магистралях: С =?; В1 =?; В2 =?; Ю1 = ?; Ю2 = ?; З = ?;
     Решение. Извлекаем квадратный корень из числа N и округляем его до меньшего нечетного числа. Значение извлеченного квадратного корня равно 65536,0000076 Меньшее ближайшее целое число 65536 = 2k, (отсюда x1 = k = 32768) четное число, меньшее него нечетное число 65536 — 1 = 65535. Это число нечетное и клетка, содержащая его квадрат Гл(k) = 4294836225, является начальной клеткой контура, содержащего число
N = F5 = 4294967297. Вторая координата х2 = 4294967297 — 4294836225 = 131072. Итак, для числа F5 получена пара координат (х1, х2) = (32768,131072). Первая координата всех реперов одна и та же — это номер контура х1 = 32768. Вторые координаты х2 различны у всех реперов.
      Клетки контура, принадлежащие магистралям, гарантированно получают мультипликативное представление С = 4294934528 = 32768∙131072; З = 4295000064 = 32768∙131073; Ю1 = 4295065599 = 32769∙131071;
Ю2= 4295065600 = 32768∙131075; В1=429 486 8991 = 32767∙131073; В2 = 4294868992 = 32768∙131069.
     Клетки магистралей получают координаты: начало контура НК(х1, х2) = (32768, 0);
В1(х1, х2) = (32768, 32766); В2(х1, х2) = (32768, 32767); С(х1, х2) = (32768, 98303);
З(х1, х2) = (32768, 63839); Ю1(х1, х2) = (32768, 229374); Ю2(х1, х2) = (32768, 229375);
     Число в контуре перед четным квадратом (2k)&sup2 — 1 = (2k +1)(2k — 1 ) = 65535х65537 = 4294967295; гарантированно составное; число за четным квадратом также оказалось составным (2k)&sup2 + 1 = 641х6700417.

Автор: VAE

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js