Новый инвариант числа. Исследование натурального ряда чисел (НРЧ)

&nbsp &nbsp &nbsp &nbsp &nbsp В арифметике натуральных чисел иногда возникает необходимость поиска делителей составного числа N. Простая операция, обратная умножению чисел, на сегодняшний день неизвестна. Ее отсутствие создает определенные трудности при решении некоторых практических задач, особенно, если манипулировать приходится с числами высокой и очень высокой разрядности (сотни и даже тысячи цифр, представляющих числа).

&nbsp &nbsp &nbsp &nbsp &nbsp В работе «Фундаментальные структуры натурального ряда чисел» Ваулин А.Е., Пилькевич С.В.– Интеллектуальные системы. Труды Седьмого международного симпозиума. Под ред. К.А. Пупкова.– М.: РУСАКИ, 2006. – с.384-387. Приводятся сведения об оригинальной концепции моделирования натурального ряда чисел и отдельного числа с целью установления свойств, слабо зависящих или вообще не зависящих от разрядности чисел. Дальнейшему развитию и уточнению деталей этого подхода посвящена настоящая работа.

&nbsp &nbsp &nbsp &nbsp &nbsp Независимость некоторых свойств чисел от их разрядности явилась одной из основных идейных посылок предлагаемого аналитического подхода к моделированию чисел. Наличие таких свойств у чисел подтверждает существование признаков делимости чисел. Например, какой бы величины не было заданное число, если свертка (сумма) его цифр делится на три, то и исходное число делится на три. От разрядности числа делимость на три практически не зависит. Аналогично и для других признаков делимости. Это свидетельство того, что некоторые свойства чисел могут не зависеть от их разрядности. Поиск таких свойств и разработка теории их использования в различных направлениях, в частности, при разработке алгоритмов факторизации, установлении простоты числа, и других не менее трудных задач является актуальной и важной проблемой современной математики.

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

&nbsp &nbsp &nbsp &nbsp &nbsp Натуральный ряд. Будем далее рассматривать натуральный ряд чисел как математический объект, имеющий сложное строение. НРЧ можно рассматривать как совокупность различных рядов с разными свойствами, например, составленным из двух арифметических прогрессий четных и нечетных чисел. Эти прогрессии имеют совпадающие разности d, равные d=2, но с разными начальными элементами: а=1 для прогрессии нечетных чисел и а=2 для прогрессии четных чисел. Загрузим все числа НРЧ в ячейки (разряды) регистра и тогда НРЧ можно представить регистром с бесконечным числом ячеек. Обратим внимание на ряд нечетных чисел.

&nbsp &nbsp &nbsp &nbsp &nbsp Рассмотрим в НРЧ три смежных последовательных числа 2n–1, 2n, 2n+1, среднее из которых четное. Возведем их в квадрат. Между квадратами крайних нечетных чисел всегда лежит четное число разрядов регистра вида 8k, которое четным квадратом разбивается на два последовательных (смежных) нечетных числа вида 4k–1 слева и 4k+1 справа. Ячейку самого четного квадрата отнесем к правому числу.

&nbsp &nbsp &nbsp &nbsp &nbsp Таким образом, любое нечетное число вида N=4k±1, k>0 – произвольное натуральное число, в НРЧ лежит всегда между квадратами чисел N=x₁²–x₀² с разной четностью. В определенных ячейках НРЧ размещаются квадраты натуральных чисел. Такому размещению соответствует ряд закономерностей. Нечетные квадраты чередуются с четными квадратами. При этом, если больший квадрат x₁² четный, то N=4k–1 и N≡3(mod4), а если больший квадрат x₁² нечетный, то N=4k+1 и N≡1(mod4).

&nbsp &nbsp &nbsp &nbsp &nbsp Представим регистр НРЧ линейкой с движком по типу логарифмической. Для заданного числа N в движке создадим окно размером в N+1 позиций (разрядов). Путем перемещения движка вдоль НРЧ-линейки будем находить и фиксировать его положения парой чисел (x₀², x₁²), которые размещены в крайних позициях окна (x₀² – левая и x₁² – правая) и оба значения будут соответствовать числовым квадратам. Разность между квадратами в крайних позициях окна, очевидно, будет совпадать с числом N=x₁²–x₀².

&nbsp &nbsp &nbsp &nbsp &nbsp Контуры НРЧ. Расстояние между квадратами двух последовательных нечетных чисел назовем контуром. Расстояние между ячейками с квадратами несмежных чисел назовем интервалом в НРЧ. Если сумма смежных нечетных чисел кратна числу 8, то она образует длину интервала, называемого контуром, а значение k является номером этого контура. Так смежные числа 11 и 13 образуют контур (11+13=24=3•8) с номером k=3 и длиной L(k)=24=k•8, а смежные нечетные числа 13 и 15 контур не образуют (13+15=28≠k•8).

&nbsp &nbsp &nbsp &nbsp &nbsp Расстояния между нечетными квадратами-границами смежных чисел всегда образуют контуры и содержат число регистровых ячеек, равное 8k. Контуры в НРЧ образуют непрерывную последовательность с номерами k=1(1)∞, т.е. НРЧ образован заполненными числами ячейками последовательности контуров, длины которых кратны числу 8. Первый контур имеет длину L(1)=3²–1²=1•8, второй контур – L(2)=5²–3²=2•8=16, и т.д. Длины контуров образуют арифметическую прогрессию с разностью d=8 и а=8.

&nbsp &nbsp &nbsp &nbsp &nbsp Заполнение всех позиций окна числами (интервалов) в каждом из фиксированных парой чисел (x₀², x₁²) положений обладает закономерностью и характеризуется некоторым числовым инвариантом, устанавливаемым в работе. Так как пар (x₀², x₁²) может быть больше одной, то будем снабжать ее числа индексом i.

&nbsp &nbsp &nbsp &nbsp &nbsp

Пример 1

&nbsp &nbsp &nbsp &nbsp &nbsp Для N=105 (размер окна — 1) имеется 4 положения (4 пары квадратов разной четности), которые фиксируются. Контролировать будем положение левой границы окна. Начинаем перемещение движка от 1 вправо. Первое положение (остановка) возникает с появлением на левой границе окна числа x₀²=4, но правая граница при этом равна 109 – не квадрат, затем на левой границе окна оказывается квадрат x₀²=9, но справа число 114 – не квадрат, после прохода позиции с числом 15 в окне слева появляется число x₀²=16 – квадрат. Останавливаемся и проверяем число на правой границе окна. Там видим число x₁²=121 – тоже квадрат. Фиксируем это положение с контролем разности между квадратами: x₁₁²–x₀₁²=11²–4²=105.
&nbsp &nbsp &nbsp &nbsp &nbsp Продолжаем движение до прихода левого края окна в позиции 25, 36, 49 и видим, что для них правая граница на квадрат не попадает. Но когда в окне слева появляется число 64, справа видим число 169 – квадрат. Фиксируем это положение и выполняем контроль x₁₂²–x₀₂²=13²–8²=105.
&nbsp &nbsp &nbsp &nbsp &nbsp Следующее фиксируемое положение окна: слева число x_о²=256, а справа x₁²=361, оба квадраты. Фиксируем и выполняем контроль разности между квадратами x₁₃²–x₀₃²=19²–16²=105.
&nbsp &nbsp &nbsp &nbsp &nbsp И, наконец, четвертое положение окна дает разность квадратов равную x₁₄²–x₀₄²=53²–52²=105.
&nbsp &nbsp &nbsp &nbsp &nbsp Дальнейшее движение прекращается, так как больше не существует пары квадратов, разность между которыми равна числу N=105, разность всех пар будет больше 105. Четвертую пару x₁₄², x₀₄² назовем предельной парой.

&nbsp &nbsp &nbsp &nbsp &nbsp Полуконтуры. Место каждого четного квадрата вида (2k)² во внутренней ячейке k-го контура. Эта ячейка делит длину L(k) контура на два m(k)=4k–1 и М(k)=4k+1 смежных нечетных числа (левое и правое), называемых полуконтурами. Заметим, что контуры и полуконтуры – это множества ячеек, заполненных натуральными числами, а m(k) и M(k) – мощности этих множеств. Множества ячеек последовательно следующих полуконтуров формируют НРЧ. Все множество нечетных чисел образуют два класса: левые числа N≡3(mod4) и правые числа N≡1(mod4). Длины полуконтуров первого контура, левое нечетное число 4•1–1=3 и правое нечетное число 4•1+1=5, в сумме образуют длину L(k=1)=3+5=8 контура с номером k=1.

&nbsp &nbsp &nbsp &nbsp &nbsp Границы контура. При заданном номере k контура он полностью определяется, полуконтуры с длиной m(k)=4k–1 левый и М(k)=4k+1 правый, границы этого контура левая Г_л(k)=(2k–1)² и правая Г_п(k)=(2k+1)². Длина контура L(k)=m(k)+M(k)=Г_п(k)–Г_л(k)=8k. Четный квадрат Г_ч(k)=(2k)² — общая граница полуконтуров.
&nbsp &nbsp &nbsp &nbsp &nbsp Действительно, разность границ Г_п(k)–Г_л(k)=(2k+1)²–(2k–1)²=4k²+2•2k+1–4k²+2•2k–1=8k.

&nbsp &nbsp &nbsp &nbsp &nbsp Предельный контур. Любое нечетное число N можно представить как полуконтур в некотором контуре с номером k_п. Такой контур единственный, так как контур слева от предельного имеет полуконтуры меньшие N, а справа — большие N. Число N левое или правое определяется с использованием четного квадрата предельного контура. Для левогоN=x₁²–x₀², и x₁ четное, для правого N=x₁²–x₀² и x₁ нечетное. Здесь роль границ полуконтуров играют значения x₁² и x₀². Эти границы определяются из выражений x₁=(N+1)/2 и x_о=(N–1)/2. Длина предельного контура с номером k_п для числа N определяется по формуле

&nbsp &nbsp &nbsp &nbsp &nbsp Номер k_п предельного контура числа N вычисляется через длину предельного контура k_п=L(k_п)/8. Теперь самое время пояснить введенные понятия числовым примером. Это специально подобранный пример, очень простой, способствующий лучшему пониманию изучаемого явления.

&nbsp &nbsp &nbsp &nbsp &nbsp

Пример 2

&nbsp &nbsp &nbsp &nbsp &nbsp Пусть задано составное нечетное натуральное число (сннч) N=105=3•5•7. Для этого числа требуется найти предельный контур, его границы и определить его номер k_п. Указать все пары квадратов (x_i1², x_i0²), i=1(1)... разной четности, разность между которыми равна числу N=105.

&nbsp &nbsp &nbsp &nbsp &nbsp Решение. Для лучшего усвоения содержания примера рекомендуется воспользоваться карандашом и бумагой. Известно, что сннч лежит между квадратами разной четности N=x₁²–x₀². Определим левое или правое число заданного N=105≡1(mod4). Число N правое, т.е. это больший полуконтур в предельном контуре. Определим границы предельного контура через значение N, x₁=(N+1)/2=(105+1)/2=53 и x_о=(N–1)/2=(105–1)/2=52. Квадраты чисел 52 и 53 являются границами полуконтура.
&nbsp &nbsp &nbsp &nbsp &nbsp Длина контура L(k_п)=2•105–2=208=8•k_п, откуда k_п=208/8=26. Меньший (левый) полуконтур имеет длину m(k_п)=L(k_п)–М(k_п)=208–105=103, является простым числом.
&nbsp &nbsp &nbsp &nbsp &nbsp Находим через k_п границы предельного контура: левая Г_л(k_п)=(2k_п–1)²=(2•26–1)²=51²=2601 и правая Г_п(k_п)=(2k_п+1)²=(2•26+1)²=53²=2809. Длина контура через его границы определяется выражением L(k_п)=Г_п(k_п)–Г_л(k_п)=2809–2601=208=8k_п.
&nbsp &nbsp &nbsp &nbsp &nbsp Поскольку заданное сннч N=105 является полуконтуром в предельном контуре, то будем полагать, что ему соответствует лишь половина номера предельного контура, т.е. k_п(N)/2=26/2=13.

&nbsp &nbsp &nbsp &nbsp &nbsp Инвариант числа. Характеристику числа N в форме k_п(N)/2 назовем инвариантом числа N, а дальше покажем, почему выбрано такое название. Инвариант может быть целым или дробным числом в зависимости от четности номера k_п предельного контура.

&nbsp &nbsp &nbsp &nbsp &nbsp Интервалы НРЧ для числа N. Далее рассмотрим возможности представления сннч N=105 разностями других пар квадратов разной четности. Число 105, как впрочем, и любое другое нечетное число можно представить суммой нечетного количества меньших смежных нечетных чисел. Полезность такого представления N следует из того, что границы всех нечетных чисел в НРЧ – квадраты, следовательно, и непрерывный интервал, представляющий N=105 из смежных нечетных чисел, будет иметь на границах квадраты. Количество слагаемых в сумме должно быть нечетным числом.

1. Допустим, что таких слагаемых будет три. Очевидно, 105:3=35 и первое слагаемое будет равно 35–2=33, второе 35, а третье 35+2=37. Числа 33, 35, 37 образуют непрерывную последовательность нечетных смежных чисел, а 35 и 37 являются полуконтурами одного контура, так как их сумма 35+37=72 кратна 8. Этот контур имеет номер k=72/8=9. Число 33 принадлежит другому предшествующему контуру с номером k=8 и в нем является правым, т.е. большим. Этому числу 33 соответствует половина номера его контура, т.е. k/2=8/2=4. Интервалу из трех примыкающих друг к другу нечетных чисел длиной в 105 ячеек в НРЧ соответствует сумма номеров контуров в виде k_п(N)/2=8/2+9=4+9=13.

   Для этого интервала определим границы. Большая граница интервала совпадает с правой границей большего контура с номером k=9, т.е. Г_п(k)=(2•k+1)²=(2•9+1)²=19²=x₁²=361. Меньшая граница интервала совпадает с левой границей меньшего из трех полуконтура, т.е. числа 33, находящегося в контуре с номером k=8, его граница – это четный квадрат удвоенного номера контура Г_ч(k)=Г_л(k)=(2k)²=(2•8)²=x₀²=256. Проверка: N=Г_п(9)–Г_л(8/2)=361–256=105.
   Теперь для N=105 можем записать факторы N=x₁²–x₀²=(19+16)(19–16)=35•3=105.

2. Пусть представление N имеет полуконтурами в сумме пять нечетных слагаемых. Очевидно, 105:5=21 и первое слагаемое будет равно 21–4=17, второе 21–2=19, третье 21, четвертое 21+2=23 и, наконец, пятое 21+4=25. Числа 17, 19, 21, 23, 25 образуют непрерывную последовательность нечетных смежных чисел, а 19, 21 и 23, 25 из них являются полуконтурами двух смежных контуров, так как их сумма 19+21=40=5•8 и 23+25=48=6•8 кратна 8. Эти контуры имеют номера k=40/8=5 и k=48/8=6.

   Число 17 является большим (правым) полуконтуром предшествующего контура с номером k=(15+17)/8=4. Этому числу соответствует половина номера меньшего контура k/2=4/2=2. Интервалу из пяти примыкающих друг к другу нечетных чисел длиной в 105 ячеек в НРЧ соответствует сумма номеров контуров k_п(N)/2=4/2+5+6=2+5+6=13.

   Для этого интервала определим границы. Большая граница интервала совпадает с правой границей большего контура с номером k=6, т.е. Г_п(k)=(2•k+1)²=(2•6+1)²=13²=x₁²=169. Меньшая левая граница интервала совпадает с левой границей меньшего полуконтура, т.е. числа 17, находящегося в контуре с номером k=4. Меньшая граница – это четный квадрат удвоенного номера контура Г_ч(k)=Г_л(k)=(2k)²=(2•4)²=x₀²=64.Проверка на разность квадратов: N=Г_п(6)–Г_ч(4)=169–64=105. Теперь для N=105 можем записать факторы N=x₁²–x₀²=(13+8)(13–8)=21•5=105.

3. Пусть слагаемых в представляющей число N сумме будет семь. Очевидно, 105:7=15 и первое слагаемое будет равно 15–6=9, второе 15–4=11, третье 15–2=13, четвертое 15, пятое 15+2=17, шестое 15+4=19 и, наконец, седьмое 15+6=21. Числа 9, 11, 13, 15, 17, 19, 21 образуют непрерывную последовательность нечетных смежных чисел, а 11, 13; 15, 17 и 19, 21 являются полуконтурами трех смежных контуров, так как их суммы 11+13=24=3•8; 15+17=32=4•8 и 19+21=40=5•8 кратны 8. Эти контуры имеют номера k=24/8=3, k=32/8=4 и k=40/8=5.

   Число 9 является большим (правым) полуконтуром предшествующего контура с номером k=(7+9)/8=2. Этому числу соответствует половина номера меньшего контура, т.е. k/2=2/2=1. Интервалу из семи примыкающих друг к другу нечетных чисел длиной в 105 ячеек в НРЧ соответствует сумма номеров контуров k_п(N)/2=2/2+3+4+5=1+3+4+5=13.

   Для этого интервала определим границы. Большая граница интервала совпадает с правой границей большего контура с номером k=5, т.е. Г_п(k)=(2•k+1)²=(2•5+1)²=11²=x₁²=121. Меньшая граница интервала совпадает с левой границей меньшего полуконтура, т.е. числа 9, находящегося в контуре с номером k=2, это четный квадрат удвоенного номера контура Г_ч(k)=Г_л(k)=(2k)²=(2•2)²=x₀²=16.Проверка: N=Г_п(5)–Г_ч(2)=121–16=105.
   Теперь для N=105 можем записать факторы N=x₁²–x₀²=(11+4)(11–4)=15•7=105.

&nbsp &nbsp &nbsp &nbsp &nbsp Рассмотренный пример показывает, что для числа N=105 существуют четыре пары квадратов разной четности, расстояние в НРЧ между которыми равно 105. Каждая из найденных пар квадратов позволяет решить задачу факторизации сннч N=105, исключая предельную пару – она дает тривиальное разложение на множители.

&nbsp &nbsp &nbsp &nbsp &nbsp Остается открытым очень важный вопрос, где брать, как получать для произвольного числа N пары (x_о², x₁²) квадратов?

&nbsp &nbsp &nbsp &nbsp &nbsp Анализ результатов примера 2 показывает, что разные пары квадратов (x_оi², x_1i²), i=1(1)4, получаются при разных представлениях инвариантаk_п(N)/2=13 в виде суммы с разным числом слагаемых. Сами такие суммы можно рассматривать как разбиения числа 13 специального вида. Все слагаемые суммы представляют собой отрезок НРЧ, в котором одно из крайних слагаемых в сумму включается лишь своей половиной. Определение такого слагаемого диктуется принадлежностью числа N к классу левых или правых нечетных чисел.

Если N – левое, то половина берется от большего слагаемого:

• N=183 – левое нечетное, 183≡3(mod4), половина берется от большего слагаемого в представлении инварианта суммой k_п(183)/2=23=15+16/2; инвариант целое число;
• N=203 – левое нечетное, 203≡3(mod4), половина берется от большего слагаемого в представлении инварианта суммой k_п(203)/2=25.5=6+7+8+9/2; инвариант не целое число;

Если N – правое, то половина берется от меньшего слагаемого:

• N=213 – правое нечетное, 213≡1(mod4), половина берется от меньшего слагаемого в представлении инварианта суммой k_п(213)/2=26.5=17/2+18; инвариант не целое число;
• N=217 – правое нечетное, 217≡1(mod4), половина берется от меньшего слагаемого в представлении инварианта суммой k_п(217)/2=27=6/2+7+8+9; инвариант целое число;

Таким образом, из рассмотренных фактов следует алгоритм решения задачи факторизации чисел:

1. Для заданного сннч N найти инвариант k_n/2.
2. Инвариант представить разбиением специального вида k_n/2=a+(a+1)+(a+2)+...+(a+t-1)+k_д/2, где k_д – дополнительный номер крайнего контура, левый или правый.
3. Для крайних слагаемых вычислить границы: левую Г_л=x₀² и правую Г_п=x₁².
4. Разность границ представить произведением скобок N=x₁²–x₀²=(x₁+x₀)(x₁–x₀)=pq.

Рассмотренный материал позволяет сделать следующие выводы.

1. Модель составного нечетного натурального числа, представляемого в понятиях контуров – полуконтуров НРЧ позволяет установить инвариант такого числа, как функцию номеров представляющих число контуров. Инвариант k_п(N)/2 сохраняет значение независимо от того разностью какой пары квадратов ( при наличии нескольких пар квадратов ) представляется сннч N=x_i1²–x_i0², i=1(1)t, где t – число представляющих пар. N=105=x_i1²–x_i0²=53²–52²=19²–16²=13²–8²=11²–4²
2. Значение инварианта устанавливается элементарной обработкой заданного числа N при установлении номера предельного контура. Инвариант может быть как целым, так и дробным числом. Относительно предельного контура сформулированы и доказаны теоремы, которые в посте не приводятся, но используются.
3. Предлагаемая модель НРЧ в терминах и понятиях контуров – полуконтуров открывает возможность формулирования и исследования задачи факторизации нечетных чисел за приемлемое для практических приложений время.

Автор: VAE

Источник ^[1]