Новый инвариант числа. Исследование натурального ряда чисел (НРЧ)
В арифметике натуральных чисел иногда возникает необходимость поиска делителей составного числа N. Простая операция, обратная умножению чисел, на сегодняшний день неизвестна. Ее отсутствие создает определенные трудности при решении некоторых практических задач, особенно, если манипулировать приходится с числами высокой и очень высокой разрядности (сотни и даже тысячи цифр, представляющих числа). В работе «Фундаментальные структуры натурального ряда чисел» Ваулин А.Е., Пилькевич С.В.– Интеллектуальные системы. Труды Седьмого международного симпозиума. Под ред. К.А. Пупкова.– М.: РУСАКИ, 2006. — с. 384–387. Приводятся сведения об оригинальной концепции моделирования натурального ряда чисел и отдельного числа с целью установления свойств, слабо зависящих или вообще не зависящих от разрядности чисел. Дальнейшему развитию и уточнению деталей этого подхода посвящена настоящая работа.
Независимость некоторых свойств чисел от их разрядности явилась одной из основных идейных посылок предлагаемого аналитического подхода к моделированию чисел. Наличие таких свойств у чисел подтверждает существование признаков делимости чисел. Например, какой бы величины не было заданное число, если свертка (сумма) его цифр делится на три, то и исходное число делится на три. От разрядности числа делимость на три практически не зависит. Аналогично и для других признаков делимости. Это свидетельство того, что некоторые свойства чисел могут не зависеть от их разрядности. Поиск таких свойств и разработка теории их использования в различных направлениях, в частности, при разработке алгоритмов факторизации, установлении простоты числа, и других не менее трудных задач является актуальной и важной проблемой современной математики.
В работе описывается новый обнаруженный признак-свойство чисел. Этот признак оказывается полезным для разработки алгоритмов решения как новых, так и традиционных задач теории и практики. Приведем вначале качественные содержательные рассуждения о сущности предлагаемой работы.
Натуральный ряд. Будем далее рассматривать натуральный ряд чисел как математический объект, имеющий сложное строение. НРЧ можно рассматривать как совокупность различных рядов с разными свойствами, например, составленным из двух арифметических прогрессий четных и нечетных чисел. Эти прогрессии имеют совпадающие разности d, равные d=2, но с разными начальными элементами: а=1 для прогрессии нечетных чисел и а=2 для прогрессии четных чисел. Загрузим все числа НРЧ в ячейки (разряды) регистра и тогда НРЧ можно представить регистром с бесконечным числом ячеек. Обратим внимание на ряд нечетных чисел.
Рассмотрим в НРЧ три смежных последовательных числа 2n–1, 2n, 2n+1, среднее из которых четное. Возведем их в квадрат. Между квадратами крайних нечетных чисел всегда лежит четное число разрядов регистра вида 8k, которое четным квадратом разбивается на два последовательных (смежных) нечетных числа вида 4k–1 слева и 4k+1 справа. Ячейку самого четного квадрата отнесем к правому числу.
Таким образом, любое нечетное число вида N=4k±1, k>0 — произвольное натуральное число, в НРЧ лежит всегда между квадратами чисел N=x12–x02 с разной четностью. В определенных ячейках НРЧ размещаются квадраты натуральных чисел. Такому размещению соответствует ряд закономерностей. Нечетные квадраты чередуются с четными квадратами. При этом, если больший квадрат x12 четный, то N=4k–1 и N≡3(mod4), а если больший квадрат x12 нечетный, то N=4k+1 и N≡1(mod4).
Представим регистр НРЧ линейкой с движком по типу логарифмической. Для заданного числа N в движке создадим окно размером в N+1 позиций (разрядов). Путем перемещения движка вдоль НРЧ-линейки будем находить и фиксировать его положения парой чисел (x02, x12), которые размещены в крайних позициях окна (x02 — левая и x12 — правая) и оба значения будут соответствовать числовым квадратам. Разность между квадратами в крайних позициях окна, очевидно, будет совпадать с числом N=x12–x02.
Контуры НРЧ. Расстояние между квадратами двух последовательных нечетных чисел назовем контуром. Расстояние между ячейками с квадратами несмежных чисел назовем интервалом в НРЧ. Если сумма смежных нечетных чисел кратна числу 8, то она образует длину интервала, называемого контуром, а значение k является номером этого контура. Так смежные числа 11 и 13 образуют контур (11+13=24=3•8) с номером k=3 и длиной L (k)=24=k•8, а смежные нечетные числа 13 и 15 контур не образуют (13+15=28≠k•8).
Расстояния между нечетными квадратами-границами смежных чисел всегда образуют контуры и содержат число регистровых ячеек, равное 8k. Контуры в НРЧ образуют непрерывную последовательность с номерами k=1(1)∞, т.е. НРЧ образован заполненными числами ячейками последовательности контуров, длины которых кратны числу 8. Первый контур имеет длину L (1)=32–12=1•8, второй контур — L (2)=52–32=2•8=16, и т.д. Длины контуров образуют арифметическую прогрессию с разностью d=8 и а=8.
Заполнение всех позиций окна числами (интервалов) в каждом из фиксированных парой чисел (x02, x12) положений обладает закономерностью и характеризуется некоторым числовым инвариантом, устанавливаемым в работе. Так как пар (x02, x12) может быть больше одной, то будем снабжать ее числа индексом i.
Пример 1 Для N=105 (размер окна — 1) имеется 4 положения (4 пары квадратов разной четности), которые фиксируются. Контролировать будем положение левой границы окна. Начинаем перемещение движка от 1 вправо. Первое положение (остановка) возникает с появлением на левой границе окна числа x02=4, но правая граница при этом равна 109 — не квадрат, затем на левой границе окна оказывается квадрат x02=9, но справа число 114 — не квадрат, после прохода позиции с числом 15 в окне слева появляется число x02=16 — квадрат. Останавливаемся и проверяем число на правой границе окна. Там видим число x12=121 — тоже квадрат. Фиксируем это положение с контролем разности между квадратами: x112–x012=112–42=105. Продолжаем движение до прихода левого края окна в позиции 25, 36, 49 и видим, что для них правая граница на квадрат не попадает. Но когда в окне слева появляется число 64, справа видим число 169 — квадрат. Фиксируем это положение и выполняем контроль x122–x022=132–82=105. Следующее фиксируемое положение окна: слева число xо2=256, а справа x12=361, оба квадраты. Фиксируем и выполняем контроль разности между квадратами x132–x032=192–162=105. И, наконец, четвертое положение окна дает разность квадратов равную x142–x042=532–522=105. Дальнейшее движение прекращается, так как больше не существует пары квадратов, разность между которыми равна числу N=105, разность всех пар будет больше 105. Четвертую пару x142, x042 назовем предельной парой.
Полуконтуры. Место каждого четного квадрата вида (2k)2 во внутренней ячейке 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.
Границы контура. При заданном номере k контура он полностью определяется, полуконтуры с длиной m (k)=4k–1 левый и М (k)=4k+1 правый, границы этого контура левая Гл (k)=(2k–1)2 и правая Гп (k)=(2k+1)2. Длина контура L (k)=m (k)+M (k)=Гп (k)–Гл (k)=8k. Четный квадрат Гч (k)=(2k)2 — общая граница полуконтуров. Действительно, разность границ Гп (k)–Гл (k)=(2k+1)2–(2k–1)2=4k2+2•2k+1–4k2+2•2k–1=8k.
Предельный контур. Любое нечетное число N можно представить как полуконтур в некотором контуре с номером kп. Такой контур единственный, так как контур слева от предельного имеет полуконтуры меньшие N, а справа — большие N. Число N левое или правое определяется с использованием четного квадрата предельного контура. Для левогоN=x12–x02, и x1 четное, для правого N=x12–x02 и x1 нечетное. Здесь роль границ полуконтуров играют значения x12 и x02. Эти границы определяются из выражений x1=(N+1)/2 и xо=(N–1)/2. Длина предельного контура с номером kп для числа N определяется по формуле
Номер kп предельного контура числа N вычисляется через длину предельного контура kп=L (kп)/8. Теперь самое время пояснить введенные понятия числовым примером. Это специально подобранный пример, очень простой, способствующий лучшему пониманию изучаемого явления.
Пример 2 Пусть задано составное нечетное натуральное число (сннч) N=105=3•5•7. Для этого числа требуется найти предельный контур, его границы и определить его номер kп. Указать все пары квадратов (xi12, xi02), i=1(1)… разной четности, разность между которыми равна числу N=105. Решение. Для лучшего усвоения содержания примера рекомендуется воспользоваться карандашом и бумагой. Известно, что сннч лежит между квадратами разной четности N=x12–x02. Определим левое или правое число заданного N=105≡1(mod4). Число N правое, т.е. это больший полуконтур в предельном контуре. Определим границы предельного контура через значение N, x1=(N+1)/2=(105+1)/2=53 и xо=(N–1)/2=(105–1)/2=52. Квадраты чисел 52 и 53 являются границами полуконтура. Длина контура L (kп)=2•105–2=208=8•kп, откуда kп=208/8=26. Меньший (левый) полуконтур имеет длину m (kп)=L (kп)–М (kп)=208–105=103, является простым числом. Находим через kп границы предельного контура: левая Гл (kп)=(2kп–1)2=(2•26–1)2=512=2601 и правая Гп (kп)=(2kп+1)2=(2•26+1)2=532=2809. Длина контура через его границы определяется выражением L (kп)=Гп (kп)–Гл (kп)=2809–2601=208=8kп. Поскольку заданное сннч N=105 является полуконтуром в предельном контуре, то будем полагать, что ему соответствует лишь половина номера предельного контура, т.е. kп (N)/2=26/2=13.
Инвариант числа. Характеристику числа N в форме kп (N)/2 назовем инвариантом числа N, а дальше покажем, почему выбрано такое название. Инвариант может быть целым или дробным числом в зависимости от четности номера kп предельного контура.
Интервалы НРЧ для числа N. Далее рассмотрим возможности представления сннч N=105 разностями других пар квадратов разной четности. Число 105, как впрочем, и любое другое нечетное число можно представить суммой нечетного количества меньших смежных нечетных чисел. Полезность такого представления N следует из того, что границы всех нечетных чисел в НРЧ — квадраты, следовательно, и непрерывный интервал, представляющий N=105 из смежных нечетных чисел, будет иметь на границах квадраты. Количество слагаемых в сумме должно быть нечетным числом.
Допустим, что таких слагаемых будет три. Очевидно, 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=(2•9+1)2=192=x12=361. Меньшая граница интервала совпадает с левой границей меньшего из трех полуконтура, т.е. числа 33, находящегося в контуре с номером k=8, его граница — это четный квадрат удвоенного номера контура Гч (k)=Гл (k)=(2k)2=(2•8)2=x02=256. Проверка: N=Гп (9)–Гл (8/2)=361–256=105.Теперь для N=105 можем записать факторы N=x12–x02=(19+16)(19–16)=35•3=105.
Пусть представление 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=(2•6+1)2=132=x12=169. Меньшая левая граница интервала совпадает с левой границей меньшего полуконтура, т.е. числа 17, находящегося в контуре с номером k=4. Меньшая граница — это четный квадрат удвоенного номера контура Гч (k)=Гл (k)=(2k)2=(2•4)2=x02=64.Проверка на разность квадратов: N=Гп (6)–Гч (4)=169–64=105. Теперь для N=105 можем записать факторы N=x12–x02=(13+8)(13–8)=21•5=105.
Пусть слагаемых в представляющей число 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=(2•5+1)2=112=x12=121. Меньшая граница интервала совпадает с левой границей меньшего полуконтура, т.е. числа 9, находящегося в контуре с номером k=2, это четный квадрат удвоенного номера контура Гч (k)=Гл (k)=(2k)2=(2•2)2=x02=16.Проверка: N=Гп (5)–Гч (2)=121–16=105.Теперь для N=105 можем записать факторы N=x12–x02=(11+4)(11–4)=15•7=105.
Рассмотренный пример показывает, что для числа N=105 существуют четыре пары квадратов разной четности, расстояние в НРЧ между которыми равно 105. Каждая из найденных пар квадратов позволяет решить задачу факторизации сннч N=105, исключая предельную пару — она дает тривиальное разложение на множители.
Остается открытым очень важный вопрос, где брать, как получать для произвольного числа N пары (xо2, x12) квадратов?
Анализ результатов примера 2 показывает, что разные пары квадратов (xоi2, x1i2), 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; инвариант целое число; Таким образом, из рассмотренных фактов следует алгоритм решения задачи факторизации чисел:
Для заданного сннч N найти инвариант kn/2. Инвариант представить разбиением специального вида kn/2=a+(a+1)+(a+2)+…+(a+t-1)+kд/2, где kд — дополнительный номер крайнего контура, левый или правый. Для крайних слагаемых вычислить границы: левую Гл=x02 и правую Гп=x12. Разность границ представить произведением скобок N=x12–x02=(x1+x0)(x1–x0)=pq. Рассмотренный материал позволяет сделать следующие выводы.
Модель составного нечетного натурального числа, представляемого в понятиях контуров — полуконтуров НРЧ позволяет установить инвариант такого числа, как функцию номеров представляющих число контуров. Инвариант kп (N)/2 сохраняет значение независимо от того разностью какой пары квадратов (при наличии нескольких пар квадратов) представляется сннч N=xi12–xi02, i=1(1)t, где t — число представляющих пар. N=105=xi12–xi02=532–522=192–162=132–82=112–42 Значение инварианта устанавливается элементарной обработкой заданного числа N при установлении номера предельного контура. Инвариант может быть как целым, так и дробным числом. Относительно предельного контура сформулированы и доказаны теоремы, которые в посте не приводятся, но используются. Предлагаемая модель НРЧ в терминах и понятиях контуров — полуконтуров открывает возможность формулирования и исследования задачи факторизации нечетных чисел за приемлемое для практических приложений время.
