Два специальных разбиения натурального числа N могут быть использованы при построении алгоритма факторизации. В предшествующих постах об этом шла речь и автору были заданы вопросы.В работах о факторизации оговаривалось, что при рассматриваемом подходе появляется принципиальная возможность решать задачу факторизации больших чисел (ЗФБЧ) за малое время при наличии программы, генерирующей специальные разбиения. В этой работе автор раскрывает более подробно специфику специальности разбиений. Поскольку участники сообщества Хабра в своем большинстве являются программистами, то предлагаю тому, кто проявит интерес к ЗФБЧ, решаемой за приемлемое время (не годами, не месяцам, и даже не десятками часов), попробовать свои силы и приложить умения к разработке программы генератора спцразбиений. Разбивать как следует из текста ниже необходимо ф-инвариант числа N, свойство, не зависящее от разрядности числа, либо само число N. В комментариях приводится таблица всех разбиений числа 13, среди которых только 4 являются специальными, к факторизации приводит любое из трех первых специальных разбиений.
Задача о разбиении натурального числа
Разбиением натурального числа N называется конечная невозрастающая последовательность натуральных чисел k0, k1, k2, k3,…,kt, меньших N, для которой сумма k0+k1+k2+k3+,…,+kt = N, числа ki, i = 0(1)t, называются блоками (частями) разбиения. Разбиения чисел бывают упорядоченными и неупорядоченными. Существуют разбиения чисел [1, 2] на нечетные и отдельно на четные части, разбиения чисел на одинаковые и различные части и т.п. Для наших целей будем использовать графическое представление разбиений чисел на разные части с ограничением на различие (∆ = 1) одной части разбиения от другой, для чего воспользуемся точечным графом Феррера.
В задаче разбиения числа N, связываемой с задачей факторизации чисел, имеют дело с двумя специальными случаями разбиений не самого числа N, а его ф-инварианта, числа kп(N)/2, т. е. половины номера предельного контура для N. Кроме того, будем различать разбиения числа kп(N)/2, соответствующие целым и дробным числам, а также соответствующие левым (Nл) и правым (Nп) нечетным натуральным числам. Графическое представление множества разбиений разбиений чисел kп(N)/2 имеет вид трапеции как составной части треугольной точечной диаграммы Феррера, образованной из ее подряд следующих строк. Одно из оснований трапеции (верхнее или нижнее) всегда включает только половину своих точек. Основная специализация рассматриваемых здесь двух типов разбиений заключается в том, что отличие частей разбиения числа одной от другой составляет лишь единицу ∆ = 1, и только крайние части (строки, являющиеся основаниями трапеции графического представления) разбиения числа могут отличаться от соседних на величину большую, чем единица. Крайняя строка (верхняя — для Nл, нижняя — для Nп) всегда разбивается пополам. Дополнительно о слагаемых в разбиениях можно прочитать (Здесь). Если разбиваемая пополам строка содержит четное число точек, то все части разбиения числа N – целые числа, если число точек в такой строке нечетное, то крайняя часть разбиения и само kп(N)/2 – дробное число. Отметим также некоторые другие особенности этих специальных разбиений. Эти особенности легко и наглядно воспринимаются при рассмотрении числовых примеров, которые в сущности и являются основным содержанием работы.
Во-первых, для Nп (правого числа) представление kп(N)/2 разбиением всегда формируется только разными слагаемыми, причем от меньшего контура в сумму включается только половина его номера.
Во-вторых, для Nл (левого числа) представление половины номера предельного контура (числа kп(N)/2) разбиением всегда сформировано различными частями, если kп(N)/2 – дробное число.
В-третьих, для Nл, если kп(N)/2 – целое, то два слагаемых в сумме могут совпадать, причем, одно слагаемое из такой пары – это половина номера большего контура в сумме. Поясним эти понятия числовым примером.
Пример 1. Задано левое нечетное число Nл = 119, так как 119 = 3(mod4). Предельный контур для этого числа имеет длину 119 + 121 = 240. Номер предельного контура kп(119) = 240/8 = 30. Ф-инвариант для числа 119 равен kп(119)/2 = 30/2 = 15. Разбиение ф-инварианта для числа N имеет вид 15 = 3 + 4 + 5 + 6/2 = 3+4+5+3. В итоговой сумме получились два одинаковых слагаемых, равных тройке. Чтобы убедиться, что разбиение ф-инварианта приводит к факторизации числа N = 119, восстановим N по разбиению, все слагаемые которого – это номера контуров. Умножаем слагаемые на 8:
3•8 + 4•8 + 5•8 + 6•8 = 24 + 32 + 40 + 48.
Последнее (большее) слагаемое должно давать в сумму только свой левый полуконтур 23 + 25 = 48, т.е. 23. Итак, устанавливаем длину интервала для Nл = 119 (проверяем) 24 + 32 + 40 + 23 = 119.
Остается вспомнить, что границами контуров и полуконтуров в НРЧ всегда являются квадраты и получить их значения у крайних слагаемых интервала:
меньшая граница Гм(3) для контура с номером 3, Гм(3) = (2•3-1)2 = 25 = 52;
большая граница интервала Гб(6) для контура с номером 6, Гб = Гц(6) = (2•6)2= 144 = 122 – правая граница левого полуконтура шестого контура.
Последний штрих: N представляем разностью квадратов, т.е. разностью границ интервала
N = 122 – 52 = (12 – 5)(12 + 5) = 7•17 = 119 и получаем разложение на множители.
Натуральные нечетные числа N(x1, xо) = 3t кратные трем всегда формируются только тремя смежными полуконтурами, два из которых – целый контур. Для таких чисел нумерационная модель совсем простая. Находим k — номер полного контура для числа N.
Для левых нечетных чисел
kп(N)/2 = (k + 1)/2 + k => kп(N) = 3k + 1 => k = (kп(N) – 1)/3.
Для правых нечетных чисел
kп(N)/2 = (k –1)/2 + k => kп(N) = 3k — 1 => k = (kп(N) + 1)/3.
Пример 2. Задано правое нечетное число Nп = 129, так как 129 = 1(mod4). Предельный контур для этого числа имеет длину 127 + 129 = 256. Номер предельного контура kп(129) = 256/8 = 32. Ф-инвариант для числа 129 равен kп(129)/2 = 32/2 = 16. Подставляем в формулу найденные значения k = (32 + 1)/3 = 11. Это номер большего контура из двух полуконтуров 43 + 45 = 88 = 11•8. Для формирования интервала включаем в сумму полуконтур из предшествующего контура с номером 11-1 = 10, т.е. М = 4k +1 = 41.
И окончательно, сумма полуконтуров 41+ 43 + 45 = 129. Остается найти границы интервала и выполнить факторизацию числа N = 129.
Все слагаемые в сумме разбиений, кроме одного крайнего слагаемого, всегда различаются на единицу, т. е. это числа ki, следующие в натуральном ряде одно за другим kп(N)/2 = ∑ti=pki ± k/2,
где р – индекс номера целого начального (меньшего) контура;
t – индекс номера целого конечного (большего) контура;
± – знак в сумме определяется видом (левое k > kt, правое k < kр) числа N;
k – номер крайнего контура (без индекса), от которого в сумме участвует только половина номера. Тот факт, что сумма в разбиении числа kп(N)/2 формируется натуральными числами, возрастающими на 1, имеет решающее значение для нумерационной модели натурального числа.
Все разбиения такого типа (все суммы kп(N)/2) оказываются представленными в треугольной точечной диаграмме Феррера (графического представления разбиения) и могут быть получены из нее.
Приведем таблицу 1 с такой диаграммой, сопроводив ее дополнительными сведениями об интервальной и нумерационной моделях числа N.
Таблица 1 — Характеристики интервальной и нумерационной моделей числа N
В средней части таблицы помещено значение графического разбиения предельного полуконтура kп(N)/2) для числа 231 = 3∙77 = 7∙33 = 11∙21 на разные части (строки с точками), отличающиеся одна от другой на единицу. Меньший делитель всегда показывает сколько полуконтуров образуют интервал числа N.
Интервальная модель – это интервал из позиций (длин) контуров/полуконтуров, сумма которых равна N.
Так для N = 231, имеем:
1-я интервальная модель 1 контур + полуконтур 152+79 = 75+77+79 – три подряд следующих полуконтура, которые различаются длиной в две единицы.
2-я интервальная модель 3 контура + полуконтур 56+64+72+39 = 27+29+31+33+35+37 +39 – семь подряд следующих полуконтуров, которые различаются длиной в две единицы.
3-я интервальная модель 5 контуров + полуконтур
24+32+40+48+56+31 = 11+13 + 15 +17 +19 +21 +23+25 +27+29 +31
– одиннадцать подряд следующих полуконтуров, которые различаются длиной в две единицы.
Нумерационная модель – это совокупность номеров контуров и полуконтура, которые описывают число N, сумма которых равна значению ф-инварианта.
Так для числа N =231 ф-инвариант равен kп(N)/2 = kп(231)/2 = 29.
kп(N)/2 = kп(231)/2 = 19 + 20/2 = 7 + 8 + 9 + 10/2 = 3 + 4 + 5 + 6 + 7 + 8/2.
Суммы в равенстве – это три нумерационные модели. Слагаемые соответствуют строкам k диаграммы.
Оба типа моделей тесно связаны и могут быть преобразованы одна в другую при необходимости.
Для нечетных натуральных чисел N в пределах первой тысячи на основе этой диаграммы может быть проведена факторизация их на два фактора. Первые четыре колонки таблицы содержат характеристики интервальной модели (характеристики контуров). Колонка справа от точечной диаграммы – номера контуров. Две последние колонки – характеристики нумерационной модели. Уровнем названа n-я снизу строка таблицы. Значения характеристики в строках приведены с нарастанием от нижней строки вверх. В последнем столбце суммы точек из предшествующих строк суммируются с половиной количества точек текущей строки. В предпоследнем столбце суммы точек полных строк
Для левых Nл чисел такие суммы kп/2, соответствующие интервалам длины Nл, всегда содержат определенное число точек и строк из треугольника и в верхней части лишь половину количества точек строки. Очевидно, если зафиксировать строку из суммы, которой соответствует значение равное kп/2 или ближайшее большее, но также содержащее половину верхней строки, то для решения о номере нижней строки в сумме остается определить только номер нижнего (меньшего) контура или соответствующей строки, формирующей сумму kп/2. Это значение определяется разностью между суммой точек для уровня фиксированной верхней строки и значением kп/2. Если такая разность присутствует в рассматриваемой колонке, то строка ей соответствующая и строки, ниже нее не учитываются в сумме.
Поиск разности С2k+1 – kп /2 начинаем от значения С2k+1 > kп /2, а вычисленную разность сравниваем с k2/2, до тех пор, пока они не совпадут. При несовпадении увеличиваем значение k.
Пример 3. Для правого числа N(x1, xо) = 621 выполнить факторизацию, определить значение длины предельного контура чисел kп(Nп) = kп(621) = (621–1)/4 = (619 + 621)/8 = 155. Затем определяем значение kп(621)/2 = 77,5 и находим значение разности С2k+1 – kп /2, ближнюю к началу НРЧ. В столбце С2k+1 таблицы 1 находим при k = 12 значение 78, превышающее kп(621)/2 = 77,5.
Тогда искомая разность С2k+1 – kп /2 = 78 – 77,5 = 0,5. Проверяем, совпадает ли найденная разность со значением k2/2 при некотором значении k. Совпадение имеет место со значением 0,5 в нижней строке таблицы.
Отсюда определяется номер меньшего контура kп2 /2 = 0,5 => k = 1, формируемого интервала. Интервал, представляющий число N = 621, начинается точкой среднего квадрата (четной) первого контура и доходит до 12-го контура включительно. Известно, что через значения границ длина интервала для числа N представляется выражением N = Гп – Гл = х1i2 – хоi2. Зная номера контуров на границах интервала, находим его граничные точки. Границами интервала будут:
• левая граница при k = 1, Гл = (2k)2 = (2•1)2 = 4,
• правая при k = 12 есть Гп = (2k + 1)2 = (2•12 + 1)2 = 625.
Тогда N = Гп – Гл = х1i2 – хоi2 = 625 – 4 = 621. С другой стороны, при наличии границ-квадратов легко выполняется факторизация числа N = х1i2 – хоi2 = (25 + 2)(25 – 2) = 27•23.
Рассмотренная в примере схема решения задачи факторизации обеспечивает нахождение и других альтернативных пар границ. Поиск разности С2k+1 – kп /2, совпадающей с k2 /2 приводит к получению такого совпадения при большем k = 19. Имеем равенство С2k+1 – kп /2 = 190 – 77,5 = 112,5 из которого находим меньшее, т.е. k = √2×112.5 = √225 = 15. Теперь можно приступить к поиску границ интервала и факторизации N.
Границами интервала будут:
• левая граница при k =15, Гл = (2k)2 = (2•15)2 = 900,
• правая при k = 19 есть Гп = (2k + 1)2 = (2•19 + 1)2 = 392 = 1521,
• N = Гп – Гл = х1i2 – хоi2 = 1521 – 900 = 621 и
• N = х1i2 – хоi2 = (39 + 30)(39 – 30) = 69•9.
Пример 4. ( Разбиение левого числа, где половина номера (не целое число) в сумму берется от большего контура).
Пусть задано число N = 235, число N = 235 ≡ 3(mod4) левое.
Длина предельного контура Ln = 235 + 237 = 472, его номер kп = L/8 = 472/8 = 59, kп /2 = 29.5, значения границ предельного контура: правая Гп = (2kп)2 = 1182, левая Гл = (2kп –1)2 = 1172 им соответствует тривиальное разложение числа N = 235∙1.
Из нумерационной модели следует, что kп/2 = 29.5. Для N = 235 (см. пример ранее) kп(235)/2 = 29.5
Ближайшее значение в столбце k2/2 = 40.5 лежит в строке k = 9.
Ему соответствует разность k2/2 – kп/2 = 40.5 – 29.5 = 11, которая отсутствует в столбце «сумма».
Следующий уровень k = 11 и k2/2 = 60.5, ему соответствует разность k2/2 – kп/2 = 60.5 – 29.5 = 31, которая также отсутствует в столбце «сумма». Следующий уровень k = 13 и k2/2 = 84.5, ему соответствует разность
k2/2 – kп/2 = 84.5 – 29.5 = 55, которая присутствует в столбце «сумма» в строке с номером k = 10.
Отсюда следует вывод о том, что все строки, начиная с номера 10 и ниже, не включаются в сумму kп/2. Следовательно, kп/2 = 29.5 = 11+ 12 + 13/2.
Выполним факторизацию заданного числа. Найдены номера контуров, образующие нумерационную модель числа: k = 11, 12 и 13. От k = 13 в формулу входит лишь левая половина этого контура.
Вычислим длины контуров L(11) = 8•11 = 88; L(12) = 8•12 = 96; L(13) = 8•13 = 104; левая половина 13-го контура m(13) = 104/2 –1 = 51. Интервальная модель 88 + 96 + 51 = 43+45+47+49+51 = 235.
Определим границы интервальной модели:
• Гп(13) = (2•13)2 = 262 = 676;
• Гл(11) = (2•11–1)2 = 212 = 441.
Теперь число N = 235 можно факторизовать
N(x1, xо) = 235 = (x1 + xо)(x1 – xо) = (26+21)(26–21) = 47•5 = 235.
Пример 5. (Разбиение правого числа, где половина номера (не целое число) в сумму берется от меньшего контура).
Пусть N = 357 Это правое число N = 357 ≡ 1(mod4).Длина предельного контура Ln = 357 + 355 = 712, его номер kп = L/8 =712/8 = 89, kп/2 =44.5, границы предельного контура:
• левая Гл = (2kп –1)2 = 1772,
• средняя Гц = (2kп )2 = 1782,
• правая Гп = (2kп + 1)2 = 1792 им соответствует тривиальное разложение числа N = 357∙1.
а ) х1 = 19; хо = 2; N = Гп (2∙58) – Гл (58∙2 – 1) = х1i2 – хоi2 = 192 – 22 = 361 – 4 =(19 + 2)∙(19 – 2) = 21∙17 = 357, kп/2 = ½ + 2 + 3 + 4 +5 + 6 + 7 + 8 + 9 = 44.5
б ) х1 = 61; хо =58; N = Гп (2∙58) – Гл (58∙2 – 1) = х1i2 – хоi2 = 612 – 582 = 3721 – 3364 = (61 + 58)∙(61 – 58) = 119∙3 = 357; kп/2 = 29/2 + 30 = 44.5.
Длина произвольных контура и интервала натурального ряда чисел между нечетными квадратами кратна числу 8. Вычет нечетного квадрата по mod 8 равен 1. Разность значений квадратов нечетных простых чисел ≥ 5 всегда кратна 24 (72 – 52 = 24). Это можно показать следующим образом. Рассмотрим квадраты двух нечетных простых чисел, а затем найдем их разность. Из трех смежных чисел 2n – 1, 2n, 2n + 1 одно всегда кратно трем. В нашем случае – это число n=3t, так как крайние числа простые по условию.
• Нч12 = (2n – 1)2 = 4n2 – 4n + 1 = 1 + 4n(n – 1) = 1 + 8 Cп2,
• Нч22 = (2n + 1)2 = 4n2 + 4n + 1 = 1 + 4n(n + 1) = 1 + 8 С2n+1,
• Нч22 – Нч12 = 8( С2n+1 – Cп2)= 4n(n + 1 – n + 1) = 8n = 8·3t =24t.
Если число N кратно 3, оно в интервальной модели образовано тремя полуконтурами, стоящими рядом. Другими словами, если число правое, то полуконтур от меньшего контура. Для N = 357 = 119•3, kп/2 = 44.5. Значение номера полуконтура определяется формулой (kп/2 –1)/3 = (44/5 – 1)/3 = 14.5. Следовательно, номер меньшего контура 14.5•2 = 29, а номер следующего 30. Действительно, 29/2 +30 = 44.5 = kп/2. Если число N кратно 5 (образовано пятью полуконтурами), то номер (kп/2 – 6)/5.
Пример 6. (Взаимосвязь характеристик интервальной и нумерационной моделей числа кратного трем)
Для левого числа N(x1, xо) = 183 и правого числа N(x1, xо) = 189 выполнить факторизацию, определить номер и длину предельного контура чисел kп(Nл) = kп(183) = (183 + 185)/8 = 46, и kп(Nп) = kп(189) = (187 + 189)/8 = 47. Далее составим уравнение для номера предельного полуконтура в нумерационной модели kп(183)/2 = (k + 1)/2 + k, откуда kп = 3k + 1 и k = (kп – 1)/3 = 45/3 = 15.
• Большая граница интервала для N = 183 правая четная Гц(16) = (2·16)2 = 322 = 1024
• меньшая левая граница Гл(15) = (2•15 – 1)2 = 292 = 841.
Факторизация числа N = 183 = 322 – 292 = (32 + 29)(32 – 29) = 61•3.
Связь правых чисел вида Nп(x1, xо) = 3t с суммой номеров контуров интервальной модели следующая:
половина номера контура плюс номер следующего контура интервала равны половине номера предельного контура kп(Nп)/2 исследуемого числа.
Для правого числа N(x1, xо) =189 значение предельного полуконтура kп(189)/2 = (k–1)/2+k,
откуда kп = 47 = 3k – 1 и k = (kп + 1)/3 = 48/3 = 16. Меньшая граница интервала для N = 189 левая четная лежит в 15 контуре Гц(15) = (2•15)2 = 302 = 900 и Гп(16) = (2•16 + 1)2 = 332 = 1089.
Факторизация числа N = 189 = (33 + 30)(33 – 30) = 63•3
Аналогичные расчеты могут быть выполнены для чисел левых и правых кратных 5, 7, 9 и т.д.
Список использованных источников
[1] Холл М. Комбинаторика. -М.: Мир, 1970. — 424 с.
[2] Эндрюс Г. Теория разбиений. -М.: Наука ГРФМЛ,1982. — 256 с.
Задача о разбиении натурального числа
Разбиением натурального числа N называется конечная невозрастающая последовательность натуральных чисел k0, k1, k2, k3,…,kt, меньших N, для которой сумма k0+k1+k2+k3+,…,+kt = N, числа ki, i = 0(1)t, называются блоками (частями) разбиения. Разбиения чисел бывают упорядоченными и неупорядоченными. Существуют разбиения чисел [1, 2] на нечетные и отдельно на четные части, разбиения чисел на одинаковые и различные части и т.п. Для наших целей будем использовать графическое представление разбиений чисел на разные части с ограничением на различие (∆ = 1) одной части разбиения от другой, для чего воспользуемся точечным графом Феррера.
В задаче разбиения числа N, связываемой с задачей факторизации чисел, имеют дело с двумя специальными случаями разбиений не самого числа N, а его ф-инварианта, числа kп(N)/2, т. е. половины номера предельного контура для N. Кроме того, будем различать разбиения числа kп(N)/2, соответствующие целым и дробным числам, а также соответствующие левым (Nл) и правым (Nп) нечетным натуральным числам. Графическое представление множества разбиений разбиений чисел kп(N)/2 имеет вид трапеции как составной части треугольной точечной диаграммы Феррера, образованной из ее подряд следующих строк. Одно из оснований трапеции (верхнее или нижнее) всегда включает только половину своих точек. Основная специализация рассматриваемых здесь двух типов разбиений заключается в том, что отличие частей разбиения числа одной от другой составляет лишь единицу ∆ = 1, и только крайние части (строки, являющиеся основаниями трапеции графического представления) разбиения числа могут отличаться от соседних на величину большую, чем единица. Крайняя строка (верхняя — для Nл, нижняя — для Nп) всегда разбивается пополам. Дополнительно о слагаемых в разбиениях можно прочитать (Здесь). Если разбиваемая пополам строка содержит четное число точек, то все части разбиения числа N – целые числа, если число точек в такой строке нечетное, то крайняя часть разбиения и само kп(N)/2 – дробное число. Отметим также некоторые другие особенности этих специальных разбиений. Эти особенности легко и наглядно воспринимаются при рассмотрении числовых примеров, которые в сущности и являются основным содержанием работы.
Во-первых, для Nп (правого числа) представление kп(N)/2 разбиением всегда формируется только разными слагаемыми, причем от меньшего контура в сумму включается только половина его номера.
Во-вторых, для Nл (левого числа) представление половины номера предельного контура (числа kп(N)/2) разбиением всегда сформировано различными частями, если kп(N)/2 – дробное число.
В-третьих, для Nл, если kп(N)/2 – целое, то два слагаемых в сумме могут совпадать, причем, одно слагаемое из такой пары – это половина номера большего контура в сумме. Поясним эти понятия числовым примером.
Пример 1. Задано левое нечетное число Nл = 119, так как 119 = 3(mod4). Предельный контур для этого числа имеет длину 119 + 121 = 240. Номер предельного контура kп(119) = 240/8 = 30. Ф-инвариант для числа 119 равен kп(119)/2 = 30/2 = 15. Разбиение ф-инварианта для числа N имеет вид 15 = 3 + 4 + 5 + 6/2 = 3+4+5+3. В итоговой сумме получились два одинаковых слагаемых, равных тройке. Чтобы убедиться, что разбиение ф-инварианта приводит к факторизации числа N = 119, восстановим N по разбиению, все слагаемые которого – это номера контуров. Умножаем слагаемые на 8:
3•8 + 4•8 + 5•8 + 6•8 = 24 + 32 + 40 + 48.
Последнее (большее) слагаемое должно давать в сумму только свой левый полуконтур 23 + 25 = 48, т.е. 23. Итак, устанавливаем длину интервала для Nл = 119 (проверяем) 24 + 32 + 40 + 23 = 119.
Остается вспомнить, что границами контуров и полуконтуров в НРЧ всегда являются квадраты и получить их значения у крайних слагаемых интервала:
меньшая граница Гм(3) для контура с номером 3, Гм(3) = (2•3-1)2 = 25 = 52;
большая граница интервала Гб(6) для контура с номером 6, Гб = Гц(6) = (2•6)2= 144 = 122 – правая граница левого полуконтура шестого контура.
Последний штрих: N представляем разностью квадратов, т.е. разностью границ интервала
N = 122 – 52 = (12 – 5)(12 + 5) = 7•17 = 119 и получаем разложение на множители.
Натуральные нечетные числа N(x1, xо) = 3t кратные трем всегда формируются только тремя смежными полуконтурами, два из которых – целый контур. Для таких чисел нумерационная модель совсем простая. Находим k — номер полного контура для числа N.
Для левых нечетных чисел
kп(N)/2 = (k + 1)/2 + k => kп(N) = 3k + 1 => k = (kп(N) – 1)/3.
Для правых нечетных чисел
kп(N)/2 = (k –1)/2 + k => kп(N) = 3k — 1 => k = (kп(N) + 1)/3.
Пример 2. Задано правое нечетное число Nп = 129, так как 129 = 1(mod4). Предельный контур для этого числа имеет длину 127 + 129 = 256. Номер предельного контура kп(129) = 256/8 = 32. Ф-инвариант для числа 129 равен kп(129)/2 = 32/2 = 16. Подставляем в формулу найденные значения k = (32 + 1)/3 = 11. Это номер большего контура из двух полуконтуров 43 + 45 = 88 = 11•8. Для формирования интервала включаем в сумму полуконтур из предшествующего контура с номером 11-1 = 10, т.е. М = 4k +1 = 41.
И окончательно, сумма полуконтуров 41+ 43 + 45 = 129. Остается найти границы интервала и выполнить факторизацию числа N = 129.
Все слагаемые в сумме разбиений, кроме одного крайнего слагаемого, всегда различаются на единицу, т. е. это числа ki, следующие в натуральном ряде одно за другим kп(N)/2 = ∑ti=pki ± k/2,
где р – индекс номера целого начального (меньшего) контура;
t – индекс номера целого конечного (большего) контура;
± – знак в сумме определяется видом (левое k > kt, правое k < kр) числа N;
k – номер крайнего контура (без индекса), от которого в сумме участвует только половина номера. Тот факт, что сумма в разбиении числа kп(N)/2 формируется натуральными числами, возрастающими на 1, имеет решающее значение для нумерационной модели натурального числа.
Все разбиения такого типа (все суммы kп(N)/2) оказываются представленными в треугольной точечной диаграмме Феррера (графического представления разбиения) и могут быть получены из нее.
Приведем таблицу 1 с такой диаграммой, сопроводив ее дополнительными сведениями об интервальной и нумерационной моделях числа N.
Таблица 1 — Характеристики интервальной и нумерационной моделей числа N
В средней части таблицы помещено значение графического разбиения предельного полуконтура kп(N)/2) для числа 231 = 3∙77 = 7∙33 = 11∙21 на разные части (строки с точками), отличающиеся одна от другой на единицу. Меньший делитель всегда показывает сколько полуконтуров образуют интервал числа N.
Интервальная модель – это интервал из позиций (длин) контуров/полуконтуров, сумма которых равна N.
Так для N = 231, имеем:
1-я интервальная модель 1 контур + полуконтур 152+79 = 75+77+79 – три подряд следующих полуконтура, которые различаются длиной в две единицы.
2-я интервальная модель 3 контура + полуконтур 56+64+72+39 = 27+29+31+33+35+37 +39 – семь подряд следующих полуконтуров, которые различаются длиной в две единицы.
3-я интервальная модель 5 контуров + полуконтур
24+32+40+48+56+31 = 11+13 + 15 +17 +19 +21 +23+25 +27+29 +31
– одиннадцать подряд следующих полуконтуров, которые различаются длиной в две единицы.
Нумерационная модель – это совокупность номеров контуров и полуконтура, которые описывают число N, сумма которых равна значению ф-инварианта.
Так для числа N =231 ф-инвариант равен kп(N)/2 = kп(231)/2 = 29.
kп(N)/2 = kп(231)/2 = 19 + 20/2 = 7 + 8 + 9 + 10/2 = 3 + 4 + 5 + 6 + 7 + 8/2.
Суммы в равенстве – это три нумерационные модели. Слагаемые соответствуют строкам k диаграммы.
Оба типа моделей тесно связаны и могут быть преобразованы одна в другую при необходимости.
Для нечетных натуральных чисел N в пределах первой тысячи на основе этой диаграммы может быть проведена факторизация их на два фактора. Первые четыре колонки таблицы содержат характеристики интервальной модели (характеристики контуров). Колонка справа от точечной диаграммы – номера контуров. Две последние колонки – характеристики нумерационной модели. Уровнем названа n-я снизу строка таблицы. Значения характеристики в строках приведены с нарастанием от нижней строки вверх. В последнем столбце суммы точек из предшествующих строк суммируются с половиной количества точек текущей строки. В предпоследнем столбце суммы точек полных строк
Для левых Nл чисел такие суммы kп/2, соответствующие интервалам длины Nл, всегда содержат определенное число точек и строк из треугольника и в верхней части лишь половину количества точек строки. Очевидно, если зафиксировать строку из суммы, которой соответствует значение равное kп/2 или ближайшее большее, но также содержащее половину верхней строки, то для решения о номере нижней строки в сумме остается определить только номер нижнего (меньшего) контура или соответствующей строки, формирующей сумму kп/2. Это значение определяется разностью между суммой точек для уровня фиксированной верхней строки и значением kп/2. Если такая разность присутствует в рассматриваемой колонке, то строка ей соответствующая и строки, ниже нее не учитываются в сумме.
Поиск разности С2k+1 – kп /2 начинаем от значения С2k+1 > kп /2, а вычисленную разность сравниваем с k2/2, до тех пор, пока они не совпадут. При несовпадении увеличиваем значение k.
Пример 3. Для правого числа N(x1, xо) = 621 выполнить факторизацию, определить значение длины предельного контура чисел kп(Nп) = kп(621) = (621–1)/4 = (619 + 621)/8 = 155. Затем определяем значение kп(621)/2 = 77,5 и находим значение разности С2k+1 – kп /2, ближнюю к началу НРЧ. В столбце С2k+1 таблицы 1 находим при k = 12 значение 78, превышающее kп(621)/2 = 77,5.
Тогда искомая разность С2k+1 – kп /2 = 78 – 77,5 = 0,5. Проверяем, совпадает ли найденная разность со значением k2/2 при некотором значении k. Совпадение имеет место со значением 0,5 в нижней строке таблицы.
Отсюда определяется номер меньшего контура kп2 /2 = 0,5 => k = 1, формируемого интервала. Интервал, представляющий число N = 621, начинается точкой среднего квадрата (четной) первого контура и доходит до 12-го контура включительно. Известно, что через значения границ длина интервала для числа N представляется выражением N = Гп – Гл = х1i2 – хоi2. Зная номера контуров на границах интервала, находим его граничные точки. Границами интервала будут:
• левая граница при k = 1, Гл = (2k)2 = (2•1)2 = 4,
• правая при k = 12 есть Гп = (2k + 1)2 = (2•12 + 1)2 = 625.
Тогда N = Гп – Гл = х1i2 – хоi2 = 625 – 4 = 621. С другой стороны, при наличии границ-квадратов легко выполняется факторизация числа N = х1i2 – хоi2 = (25 + 2)(25 – 2) = 27•23.
Рассмотренная в примере схема решения задачи факторизации обеспечивает нахождение и других альтернативных пар границ. Поиск разности С2k+1 – kп /2, совпадающей с k2 /2 приводит к получению такого совпадения при большем k = 19. Имеем равенство С2k+1 – kп /2 = 190 – 77,5 = 112,5 из которого находим меньшее, т.е. k = √2×112.5 = √225 = 15. Теперь можно приступить к поиску границ интервала и факторизации N.
Границами интервала будут:
• левая граница при k =15, Гл = (2k)2 = (2•15)2 = 900,
• правая при k = 19 есть Гп = (2k + 1)2 = (2•19 + 1)2 = 392 = 1521,
• N = Гп – Гл = х1i2 – хоi2 = 1521 – 900 = 621 и
• N = х1i2 – хоi2 = (39 + 30)(39 – 30) = 69•9.
Пример 4. ( Разбиение левого числа, где половина номера (не целое число) в сумму берется от большего контура).
Пусть задано число N = 235, число N = 235 ≡ 3(mod4) левое.
Длина предельного контура Ln = 235 + 237 = 472, его номер kп = L/8 = 472/8 = 59, kп /2 = 29.5, значения границ предельного контура: правая Гп = (2kп)2 = 1182, левая Гл = (2kп –1)2 = 1172 им соответствует тривиальное разложение числа N = 235∙1.
Из нумерационной модели следует, что kп/2 = 29.5. Для N = 235 (см. пример ранее) kп(235)/2 = 29.5
Ближайшее значение в столбце k2/2 = 40.5 лежит в строке k = 9.
Ему соответствует разность k2/2 – kп/2 = 40.5 – 29.5 = 11, которая отсутствует в столбце «сумма».
Следующий уровень k = 11 и k2/2 = 60.5, ему соответствует разность k2/2 – kп/2 = 60.5 – 29.5 = 31, которая также отсутствует в столбце «сумма». Следующий уровень k = 13 и k2/2 = 84.5, ему соответствует разность
k2/2 – kп/2 = 84.5 – 29.5 = 55, которая присутствует в столбце «сумма» в строке с номером k = 10.
Отсюда следует вывод о том, что все строки, начиная с номера 10 и ниже, не включаются в сумму kп/2. Следовательно, kп/2 = 29.5 = 11+ 12 + 13/2.
Выполним факторизацию заданного числа. Найдены номера контуров, образующие нумерационную модель числа: k = 11, 12 и 13. От k = 13 в формулу входит лишь левая половина этого контура.
Вычислим длины контуров L(11) = 8•11 = 88; L(12) = 8•12 = 96; L(13) = 8•13 = 104; левая половина 13-го контура m(13) = 104/2 –1 = 51. Интервальная модель 88 + 96 + 51 = 43+45+47+49+51 = 235.
Определим границы интервальной модели:
• Гп(13) = (2•13)2 = 262 = 676;
• Гл(11) = (2•11–1)2 = 212 = 441.
Теперь число N = 235 можно факторизовать
N(x1, xо) = 235 = (x1 + xо)(x1 – xо) = (26+21)(26–21) = 47•5 = 235.
Пример 5. (Разбиение правого числа, где половина номера (не целое число) в сумму берется от меньшего контура).
Пусть N = 357 Это правое число N = 357 ≡ 1(mod4).Длина предельного контура Ln = 357 + 355 = 712, его номер kп = L/8 =712/8 = 89, kп/2 =44.5, границы предельного контура:
• левая Гл = (2kп –1)2 = 1772,
• средняя Гц = (2kп )2 = 1782,
• правая Гп = (2kп + 1)2 = 1792 им соответствует тривиальное разложение числа N = 357∙1.
а ) х1 = 19; хо = 2; N = Гп (2∙58) – Гл (58∙2 – 1) = х1i2 – хоi2 = 192 – 22 = 361 – 4 =(19 + 2)∙(19 – 2) = 21∙17 = 357, kп/2 = ½ + 2 + 3 + 4 +5 + 6 + 7 + 8 + 9 = 44.5
б ) х1 = 61; хо =58; N = Гп (2∙58) – Гл (58∙2 – 1) = х1i2 – хоi2 = 612 – 582 = 3721 – 3364 = (61 + 58)∙(61 – 58) = 119∙3 = 357; kп/2 = 29/2 + 30 = 44.5.
Длина произвольных контура и интервала натурального ряда чисел между нечетными квадратами кратна числу 8. Вычет нечетного квадрата по mod 8 равен 1. Разность значений квадратов нечетных простых чисел ≥ 5 всегда кратна 24 (72 – 52 = 24). Это можно показать следующим образом. Рассмотрим квадраты двух нечетных простых чисел, а затем найдем их разность. Из трех смежных чисел 2n – 1, 2n, 2n + 1 одно всегда кратно трем. В нашем случае – это число n=3t, так как крайние числа простые по условию.
• Нч12 = (2n – 1)2 = 4n2 – 4n + 1 = 1 + 4n(n – 1) = 1 + 8 Cп2,
• Нч22 = (2n + 1)2 = 4n2 + 4n + 1 = 1 + 4n(n + 1) = 1 + 8 С2n+1,
• Нч22 – Нч12 = 8( С2n+1 – Cп2)= 4n(n + 1 – n + 1) = 8n = 8·3t =24t.
Если число N кратно 3, оно в интервальной модели образовано тремя полуконтурами, стоящими рядом. Другими словами, если число правое, то полуконтур от меньшего контура. Для N = 357 = 119•3, kп/2 = 44.5. Значение номера полуконтура определяется формулой (kп/2 –1)/3 = (44/5 – 1)/3 = 14.5. Следовательно, номер меньшего контура 14.5•2 = 29, а номер следующего 30. Действительно, 29/2 +30 = 44.5 = kп/2. Если число N кратно 5 (образовано пятью полуконтурами), то номер (kп/2 – 6)/5.
Пример 6. (Взаимосвязь характеристик интервальной и нумерационной моделей числа кратного трем)
Для левого числа N(x1, xо) = 183 и правого числа N(x1, xо) = 189 выполнить факторизацию, определить номер и длину предельного контура чисел kп(Nл) = kп(183) = (183 + 185)/8 = 46, и kп(Nп) = kп(189) = (187 + 189)/8 = 47. Далее составим уравнение для номера предельного полуконтура в нумерационной модели kп(183)/2 = (k + 1)/2 + k, откуда kп = 3k + 1 и k = (kп – 1)/3 = 45/3 = 15.
• Большая граница интервала для N = 183 правая четная Гц(16) = (2·16)2 = 322 = 1024
• меньшая левая граница Гл(15) = (2•15 – 1)2 = 292 = 841.
Факторизация числа N = 183 = 322 – 292 = (32 + 29)(32 – 29) = 61•3.
Связь правых чисел вида Nп(x1, xо) = 3t с суммой номеров контуров интервальной модели следующая:
половина номера контура плюс номер следующего контура интервала равны половине номера предельного контура kп(Nп)/2 исследуемого числа.
Для правого числа N(x1, xо) =189 значение предельного полуконтура kп(189)/2 = (k–1)/2+k,
откуда kп = 47 = 3k – 1 и k = (kп + 1)/3 = 48/3 = 16. Меньшая граница интервала для N = 189 левая четная лежит в 15 контуре Гц(15) = (2•15)2 = 302 = 900 и Гп(16) = (2•16 + 1)2 = 332 = 1089.
Факторизация числа N = 189 = (33 + 30)(33 – 30) = 63•3
Аналогичные расчеты могут быть выполнены для чисел левых и правых кратных 5, 7, 9 и т.д.
Список использованных источников
[1] Холл М. Комбинаторика. -М.: Мир, 1970. — 424 с.
[2] Эндрюс Г. Теория разбиений. -М.: Наука ГРФМЛ,1982. — 256 с.
