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

    У арифметиці натуральних чисел іноді виникає необхідність пошуку дільників складеного числа 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 = x 1 2 -x 0 2 з різною парністю. У певних осередках НРЧ розміщуються квадрати натуральних чисел. Такому розміщенню відповідає ряд закономірностей. Непарні квадрати чергуються з парними квадратами. При цьому, якщо більший квадрат x 1 2 парний, то N = 4k-1 і N ≡ 3 (mod4) , а якщо більший квадрат x 1 2 непарний, то N = 4k +1 і N ≡ 1 (mod4) .
 
Уявімо регістр НРЧ лінійкою з движком по типу логарифмічною. Для заданого числа N в движку створимо вікно розміром в N +1 позицій (розрядів). Шляхом переміщення движка уздовж НРЧ-лінійки будемо знаходити і фіксувати його положення парою чисел (x 0 2 , x 1 2 ) , які розміщені в крайніх позиціях вікна (x 0 2 — ліва і x 1 2 — права) і обидва значення відповідатимуть числовим квадратах. Різниця між квадратами в крайніх позиціях вікна, очевидно, буде збігатися з числом N = x 1 2 -x 0 2 .
 
Контури НРЧ . Відстань між квадратами двох послідовних непарних чисел назвемо контуром . Відстань між осередками з квадратами несуміжних чисел назвемо інтервалом в НРЧ. Якщо сума суміжних непарних чисел кратна числу 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) = 3 2 -1 2 = 1 • 8 , другий контур — L (2) = 5 2 -3 2 = 2 • 8 = 16 , і т.д. Довжини контурів утворюють арифметичну прогресію з різницею d = 8 і а = 8 .
 
Заповнення всіх позицій вікна числами (інтервалів) у кожному з фіксованих парою чисел (x 0 2 , x 1 2 ) положень володіє закономірністю і характеризується деяким числовим інваріантом, встановлюваним в роботі. Так як пар (x 0 2 , x 1 2 ) може бути більше однієї, то будемо постачати її числа індексом i .
 

Приклад 1

Для N = 105 (розмір вікна — 1) є 4 положення (4 пари квадратів різної парності), які фіксуються. Контролювати будемо положення лівого кордону вікна. Починаємо переміщення движка від 1 вправо. Перше положення (зупинення) виникає з появою на лівій межі вікна числа x 0 2 = 4 , але права межа при цьому дорівнює 109 — НЕ квадрат, потім на лівій межі вікна виявляється квадрат x 0 2 = 9 , але справа число 114 — НЕ квадрат, після проходу позиції з числом 15 у вікні зліва з'являється число x 0 2 = 16 — квадрат. Зупиняємося і перевіряємо число на правій межі вікна. Там бачимо число x 1 2 = 121 — теж квадрат. Фіксуємо це положення з контролем різниці між квадратами: x 11 2 -x 01 2 = 11 2 -4 2 = 105 .
Продовжуємо рух до приходу лівого краю вікна у позиції 25 , 36 , 49 і бачимо, що для них права межа на квадрат не потрапляє. Але коли у вікні зліва з'являється число 64 , праворуч бачимо число 169 — квадрат. Фіксуємо це положення і виконуємо контроль x 12 2 -x 02 2 = 13 2 -8 2 = 105 .
Наступне фиксируемое положення вікна: зліва число x про 2 = 256 , а праворуч x 1 2 = 361 , обидва квадрати. Фіксуємо і виконуємо контроль різниці між квадратами x 13 2 -x 03 2 = 19 2 -16 2 = 105 .
І, нарешті, четверте положення вікна дає різницю квадратів рівну x 14 2 -x 04 2 = 53 2 -52 2 = 105 .
Подальший рух припиняється, оскільки більше не існує пари квадратів, різниця між якими дорівнює числу N = 105 , різниця всіх пар буде більше 105 . Четверту пару x 14 2 , x 04 2 назвемо граничної парою.
 
 
 
Полуконтури . Місце кожного парного квадрата виду (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 = 4k 2 +2 • 2k + 1 4k 2 +2 • 2k-1 = 8k .
 
Граничний контур . Будь-яке непарне число N можна представити як полуконтур в деякому контурі з номером k п . Такий контур єдиний, так як контур зліва від граничного має полуконтури менші N , а праворуч — великі N . Число N ліве або праве визначається з використанням парного квадрата граничного контуру. Для лівого N = x 1 2 -x 0 2 , і x 1 парне, для правого N = x 1 2 -x 0 2 і x 1 непарне. Тут роль кордонів полуконтуров грають значення x 1 2 і x 0 2 . Ці межі визначаються з виразів x 1 = (N +1) / 2 і x про = (N-1) / 2 . Довжина граничного контуру з номером k п для числа N визначається за формулою
 
 
  
Номер k п граничного контуру числа N обчислюється через довжину граничного контуру k п = L (k п ) / 8 . Тепер саме час пояснити введені поняття числовим прикладом. Це спеціально підібраний приклад, дуже простий, що сприяє кращому розумінню досліджуваного явища.
 

Приклад 2

Нехай задано складене непарне натуральне число (сннч) N = 105 = 3 • 5 • 7 . Для цього числа потрібно знайти граничний контур, його межі і визначити його номер k п . Вказати всі пари квадратів (x i1 2 , x i0 2 ) , i = 1 (1)… різної парності, різниця між якими дорівнює числу N = 105 .
 
Рішення. Для кращого засвоєння змісту прикладу рекомендується скористатися олівцем і папером. Відомо, що сннч лежить між квадратами різної парності N = x 1 2 -x 0 2 . Визначимо ліве або праве число заданого N = 105 ≡ 1 (mod4) . Число N праве, тобто це більший полуконтур в граничному контурі. Визначимо кордону граничного контуру через значення N , x 1 = (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 = 51 2 = 2601 і права Г п (k п ) = (2k п +1) 2 = (2 • 26 +1) 2 = 53 2 = 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 = 19 2 = x 1 2 = 361 . Менша межа інтервалу збігається з лівого кордоном меншого з трьох полуконтура, тобто числа 33 , що знаходиться в контурі з номером k = 8 , його межа — це парний квадрат подвоєного номера контуру Г год (k) = Г л (k) = (2k) 2 = (2 • 8) 2 = x 0 2 = 256 . Перевірка: N = Г п (9)-Г л (8/2) = 361-256 = 105 .
Тепер для N = 105 можемо записати фактори N = x 1 2 -x 0 2 = (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 = 13 2 = x 1 2 = 169 . Менша ліва межа інтервалу збігається з лівого кордоном меншого полуконтура, тобто числа 17 , що знаходиться в контурі з номером k = 4 . Менша кордон — це парний квадрат подвоєного номера контуру Г год (k) = Г л (k) = (2k) 2 = (2 • 4) 2 = x 0 2 = 64 . Перевірка на різницю квадратів: N = Г п (6)-Г год (4) = 169-64 = 105 . Тепер для N = 105 можемо записати фактори N = x 1 2 -x 0 2 = (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 = 11 2 = x 1 2 = 121 . Менша межа інтервалу збігається з лівого кордоном меншого полуконтура, тобто числа 9 , що знаходиться в контурі з номером k = 2 , це парний квадрат подвоєного номера контуру Г год (k) = Г л (k) = (2k) 2 = (2 • 2) 2 = x 0 2 = 16 . Перевірка: N = Г п (5)-Г год (2) = 121-16 = 105 .
Тепер для N = 105 можемо записати фактори N = x 1 2 -x 0 2 = (11 +4) (11-4) = 15 • 7 = 105 .


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

& Nbsp & nbsp & nbsp & nbsp & nbsp Залишається відкритим дуже важливе питання, де брати, як отримувати для довільного числа N пари (x про 2 , x 1 2 ) квадратів?

& Nbsp & nbsp & nbsp & nbsp & nbsp Аналіз результатів прикладу 2 показує, що різні пари квадратів (x Оi 2 , x 1i 2 ) , 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 знайти інваріант k n / 2 .
Інваріант уявити розбиттям спеціального виду k n / 2 = a + (a +1) + (a +2) +… + (a + t-1) + k д / 2 , де k д — додатковий номер крайнього контуру, лівий або правий.
Для крайніх доданків обчислити кордону: ліву Г л = x 0 2 і праву Г п = x 1 2 .
Різниця кордонів уявити твором дужок N = x 1 2 -x 0 2 = (x 1 + x 0 ) (x 1 -x 0 ) = pq .


Розглянутий матеріал дозволяє зробити наступні висновки. Модель складеного непарного натурального числа, репрезентованої в поняттях контурів — полуконтуров НРЧ дозволяє встановити інваріант такого числа, як функцію номерів представляють число контурів. Інваріант k п (N) / 2 зберігає значення незалежно від того різницею якої пари квадратів (при наявності декількох пар квадратів) представляється сннч N = x i1 2 -x i0 2 , i = 1 (1) t , де t — число представляють пар. N = 105 = x i1 2 -x i0 2 = 53 2 -52 2 = 19 2 -16 2 = 13 2 -8 2 = 11 2 -4 2
Значення інваріанта встановлюється елементарної обробкою заданого числа N при встановленні номера граничного контуру. Інваріант може бути як цілим, так і дробовим числом. Щодо граничного контуру сформульовані і доведені теореми, які в пості не наводяться, але використовуються.
Пропонована модель НРЧ в термінах і поняттях контурів — полуконтуров відкриває можливість формулювання і дослідження задачі факторизації непарних чисел за прийнятний для практичних додатків час.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.