Про простые проблемы Ландау.

Про простые проблемы Ландау.

К выводам, изложенным ниже, я пришел уже довольно давно, но считал их настолько очевидными и сами собой разумеющимися, что принял их к сведению и отложил в сторону. Вот простая интуитивная формулировка:

п.1. Не каждое число вида (6*k+1) или (6*k-1), где k – натуральное число, является простым, но только число вида (6*k+1) или (6*k-1) может оказаться простым.

п.2. Следствие 1 из п.1. Количество мест в ряду натуральных чисел, на которых могли бы располагаться простые числа, ограничено.

Именно этими позициями, (6*k+1) или (6*k-1), и ограничено.

п.3. Следствие 2 из п.1. Количество свободных мест в ряду натуральных чисел, на которых могли бы располагаться простые числа, уменьшается с увеличением значения k – натуральное число.

п.4. Вывод из следствия 2 из п.1. Расстояние, числовой промежуток, между соседними простыми числами имеет неравномерную тенденцию к увеличению, по причине уменьшения количества свободных мест в ряду натуральных чисел, на которых могли бы располагаться простые числа, с увеличением значения k – натуральное число. 

Учитывая, что количество натуральных чисел бесконечно, что количество простых чисел бесконечно, что разница между ними медленно и неравномерно увеличивается, то процесс увеличения разницы между соседними простыми числами не ограничен максимальным значением последнего существующего простого числа или окончанием числового ряда, что допускает существование отрезков ряда натуральных чисел с произвольно большим по максимальному размеру промежутком между соседними простыми числами То есть, расстояние между простыми числами увеличивается и не ограничено; что однозначно допускает существование таких участков натуральных чисел, где произвольное простое число p_i больше, чем удвоенное предыдущее ему простое число p_i-1; и количество участков ряда натуральных чисел с подобным соотношением простых чисел не ограничено.
Вот строгая формулировка.

п.1. Тезис. Не каждое число вида (6*k+1) или (6*k-1), где k – здесь и далее по тексту, натуральное число, является простым, но только число вида (6*k+1) или (6*k-1) может оказаться простым.

Доказательство тезиса. Числа, кратные простому числу 2, представляют собой арифметическую прогрессию с шагом 2 и первым членом прогрессии равным 2. Отсюда, если натуральное число n четное n=2*к, то числа (2*к-1) и (2*к+1) – однозначно не делятся на 2. Аналогичным образом, если натуральное число n делится на простое число 3, то есть n=3*к, то числа (3*к-1) и (3*к+1) – однозначно не делятся на 3. Тогда, если натуральное составное число n имеет в числе своих составляющих простых множителей хотя бы по одному простому числу 2 и простому числу 3, то есть, кратно шести n=6*к, то только натуральные числа (n-1)=(6*к-1) и (n+1)=(6*к+1) однозначно не делятся на простое число 2 и на простое число 3.
 Целью данной работы не является выведение формулы решета Эратосфена, или аналогичного построения, поэтому, во избежание излишнего усложнения доказательств, в формулы никаких дополнительных элементов, для исключения кратности другим простым числам, вводиться не будет. Равно как и любые другие преобразования ряда натуральных чисел производиться не будут.
 На основании вышесказанного, из-за того, что все натуральные числа, кроме тех, что можно представить в виде формул (6*к-1) или (6*к+1), однозначно делятся на простое число 2 или на простое число 3, то, по определению простого числа, только натуральные числа, которые можно представить в виде формул (6*к-1) или (6*к+1), могут оказаться соответствующими определению простоты числа: не каждое число вида (6*k+1) или (6*k-1) является простым, но только число вида (6*k+1) или (6*k-1) может оказаться простым. Что и требовалось доказать.

п.2. Следствие 1 из п.1. – простое следствие из тезиса. Количество натуральных чисел, которые, в общем случае, целесообразно рассматривать в качестве претендентов на соответствие определению простоты числа, ограничено.

Доказательство. Именно этими числами, которые можно представить в виде формулы (6*k+1) или (6*k-1), и ограничено, так как все остальные натуральные числа, которые нельзя представить в виде формулы (6*k+1) или (6*k-1), гарантировано кратны простому числу 2 или простому числу 3, и рассмотрение их в качестве претендентов на соответствие определению простоты, заведомо ошибочно.
 Введение в формулы дополнительных элементов, для исключения кратности исследуемых натуральных чисел другим простым числам, сократит количество натуральных чисел – претендентов на соответствие определению простоты числа, далее числа-претенденты, но подобные действия выходят за рамки данной работы. Здесь достаточно и того, что числа-претенденты составляют всего 1/3 часть от ряда натуральных чисел. Ведь, 1/2 часть натуральных чисел делится на простое число 2, 1/3 часть натуральных чисел делится на простое число 3. При этом половина натуральных чисел, кратных простому числу 3, также делятся и на простое число 2. Таким образом,
(1/3):2=(1/6),

то есть 1/6 часть натуральных чисел кратны простому числу 3, но не кратны простому числу 2. Тогда,
(1/2)+(1/6)=(3/6)+(1/6)=(4/6)=(2/3),
то есть 2/3 часть натуральных чисел кратны простому числу 2 и простому числу 3. Значит,
1-(2/3)=(1/3)
то есть 1/3 часть натуральных чисел не кратна ни простому числу 2, ни простому числу 3.
Совершенно аналогично рассчитывается часть подмножества натуральных чисел, кратных простому (р>3), но не кратных при этом ни числу 2 ни числу 3.

п.3. Следствие 2 из п.1. – сложное следствие из тезиса и простого следствия.

Чем больше произвольное натуральное число n, тем больше существует простых чисел p, меньших этого произвольного натурального числа n, в рамках закономерности распространения простых чисел, и тем большая часть чисел-претендентов, больших этого произвольного натурального числа n, являются составными числами. Чем большая часть чисел-претендентов, больших этого произвольного натурального числа n, являются составными числами, тем, соответственно, меньше часть чисел-претендентов, не являющихся составными числами, а именно, являющихся простыми.

Доказательство. Каждое простое число порождает бесконечное подмножество кратных себе натуральных чисел, из которых, если простое число p>3, только 2/3 часть кратны, помимо прочих простых чисел, простому числу 2 или простому числу 3, а оставшаяся 1/3 часть натуральных чисел подмножества кратных этому простому числу представляет собой натуральные числа, которые можно выразить в виде формулы (6*k+1) или (6*k-1), то есть, числа-претенденты, так как они не кратны ни простому числу 2, ни простому числу 3. Все составные натуральные числа, не кратные ни простому числу 2, ни простому числу 3, не являющиеся степенью какого-либо простого числа, всегда кратны двум, или более, простым числам, и принадлежат более чем одному подмножеству чисел, кратных простым множителям, составляющим это число. Из-за этого, 1/3 часть подмножества чисел, кратных простому числу p>3, неравномерно заполняет подмножество чисел-претендентов, не вызывая резкого увеличения числовых промежутков между соседними простыми числами. Составные числа, являющиеся натуральными степенями простых чисел p>3, кратны только одному простому числу и принадлежат только подмножеству чисел-претендентов, соответственно, более эффективно заполняя его, равномерно уменьшая часть чисел-претендентов, могущих оказаться простыми. Например, вторая степень любого простого числа p>3 всегда p²=(6m+1), где m – здесь и далее по тексту, натуральное число. Исследование остальных натуральных степеней простых чисел выходит за рамки данной работы. Таким образом, чем больше количество простых чисел, меньших произвольного натурального числа n, тем большая часть чисел-претендентов, больших этого произвольного натурального числа n, являются кратными этим простым числам. Чем большая часть чисел-претендентов, больших этого произвольного натурального числа n, являются составными числами, тем, соответственно, меньше оставшаяся часть чисел-претендентов, не являющихся составными числами, то есть, являющихся простыми. Помимо приведенных аналитических аргументов, данное следствие 2 из п.1 подтверждается и исследованиями простых чисел в ряду натуральных чисел, фиксирующими непрерывное асимптотическое уменьшение доли простых чисел в ряду натуральных чисел, с увеличением значений натуральных чисел на исследуемом числовом участке. Противоположных или спорных данному утверждению данных исследования не фиксировали.

п.4. Вывод из следствия 2 из п.1. Расстояние, числовой промежуток, между соседними простыми числами имеет не ограниченную неравномерную тенденцию к увеличению. Непрерывное асимптотическое уменьшение доли простых чисел в ряду натуральных чисел, с увеличением значений натуральных чисел на исследуемом числовом участке не прекратится по причине отсутствия условий прекращения и границ распространения этого явления. Ряд натуральных и ряд простых чисел бесконечны – отсутствуют границы среды распространения данного явления. По описанным выше причинам, числовой промежуток между простыми числами не станет постоянным или уменьшающимся – отсутствуют  условия прекращения данного явления. По этому, нет причин предполагать, что асимптотический рост числовых промежутков между простыми числами, с увеличением значений натуральных чисел на исследуемом числовом участке, имеет какие-либо ограничения.

 Просматривая недавно в Википедии статью о простых числах, наткнулся на подраздел об открытых вопросах теории чисел. В рамках данной статьи рассмотрены приведенные там проблемы Ландау, с 1912 года до настоящего времени признаваемые открытыми проблемами теории чисел.

Первая проблема Ландау, она же бинарная проблема Гольдбаха, она же проблема Эйлера: верно ли, что каждое четное число, больше двух, может быть представлено в виде суммы двух простых чисел.

Очевидно, что данное предположение было сделано на основании статистической обработки ограниченного количества данных и культивируется при игнорировании, либо непонимании, научных представлений, не вписывающихся в разрабатываемую модель. В доступной к исследованию части ряда натуральных чисел плотность расположения простых чисел сначала чрезмерная, потом высокая, с увеличением значений чисел плотность простых чисел в ряду натуральных чисел снижается. При этом, количество простых чисел не ограничено, бесконечно. Именно эти два, известных и научно признанных представления о простых числах, вместе делают первую проблему Ландау-Гольдбаха-Эйлера несостоятельной. Не ограниченное количество простых чисел с возрастанием расстояния между ними однозначно допускают существование таких участков натуральных чисел, где произвольное простое число p_i больше чем удвоенное предыдущее ему простое число p_(i-1):

p_i > 2 p_(i-1)

(p_i / 2) > p_(i-1)

Таким образом, четное число n=(p_i-1) будет больше, чем сумма двух самых больших предыдущих простых чисел p_(i-1) и p_(i-2), даже если они являются простыми числами-близнецами, то есть

p_(i-1) - p_(i-2) = 2

p_(i-2) = p_(i-1) - 2

Тогда:

p_(i-1) + p_(i-2) = p_(i-1) + p_(i-1) – 2 = 2p_(i-1) – 2 = 2(p_i / 2) – 2 = (p_i -2) < n=(p_i-1)

И количество участков ряда натуральных чисел с подобным соотношением простых чисел p_i и p_(i-1) ничем не ограничено.

Вторая проблема Ландау: бесконечно ли множество «простых близнецов» - пар простых чисел, разность между которыми равна 2.

При отсутствии наличия у нас полной закономерности расположения простых чисел, с учетом уменьшения плотности их распространения, неограниченности количества простых чисел, их привязанности к четным числам кратным шести (подробнее об этом в рассмотрении следующей проблемы), вероятность того, что множество «простых близнецов» бесконечно, мало существенна, но допустима как проявление неравномерности распределения простых чисел, и, на данный момент, быть математически рассчитана не может. Ведь, уменьшение плотности распространения простых чисел в целом, должно приводить и к пропорциональному уменьшению плотности распространения «простых близнецов», являющихся, всё-таки, простыми. В связи с этим несколько абсурдно выглядят упоминаемые, в том числе в Википедии, заявления о каких-либо, якобы научных, и даже математических, доказательствах существования бесконечного количества «простых близнецов», расстояние между которыми не превышает какое-то конкретное число. То есть, расстояние между простыми числами увеличивается и не ограничено, а расстояние между парами простых чисел, разность между которыми равна 2, научно-доказательно ограничено трехзначным числом. Чувствуется очень тонкий математический юмор в одновременном признании обоих утверждений. 

Возможны три очевидных варианта объяснения их происхождения:

1) это совершенно обычные простые числа, их поведение полностью вписывается в неизвестные нам законы и правила происхождения и существования простых чисел;

2) одно из них является совершенно обычным простым числом, а другое – аномалией, исключением из неизвестных нам правил и законов происхождения и существования простых чисел;

3) они оба являются аномалией, исключением из неизвестных нам правил и законов происхождения и существования простых чисел.

И в оценке результатов работ граждан, указанных в Википедии, я исходил из невозможности аналитического выражения закономерности и ограничения их появления ни в одном из возможных вариантов: закона появления всех простых чисел пока нет, аномалия не контролируется по определению; а статистическая обработка ограниченного набора данных ненадежна. Значит, подобные работы не могли выдержать объективную критику. Даже без учета моего мнения о возможном поведении числовых отрезков между соседними простыми числами, несмотря на то, что в них нет конкретных числовых значений и внутренних противоречий.

То есть, считается признанным, что плотность распространения простых чисел снижается. Но, что плотность распространения отдельных, аномально сближенных, простых чисел  ограничена трехзначным, да и любым другим, числом – то тоже можно признать. Вероятно, в доказательствах так много букв-цифр, что мало кто станет вникать, а авторы, наверно, хорошие люди, не жалко же.

Третья проблема Ландау, она же гипотеза Лежандра: верно ли, что для всякого натурального числа n между (n²) и (n+1)² всегда найдется простое число.

В данной проблеме имеется та же логическая ошибка, что и в известной с конца 20-го века статистической шутке: 20% англичан знают французский язык и 20% англичан лысые, значит, изучение французского языка англичанами ведет к их облысению. Следует понять и смириться, что закономерность появления квадратов чисел и закономерность появления простых чисел никак между собой не связаны. Квадраты натуральных чисел – это бесконечный ряд чисел, представляющий собой арифметическую прогрессию второго порядка с шагом в виде арифметической прогрессии первого порядка с шагом 2, начиная с 1. Квадраты натуральных чисел вполне естественно располагаются в массиве натуральных чисел и не влияют на появление простых чисел. Они просто существуют в одно время и в одном месте, как лысые и франкоязычные англичане из шутки. Простые числа имеют единственную доказуемую закономерность появления в ряду натуральных чисел, но о ней в Википедии упоминается вскользь: каждое простое число может быть представлено в виде (6к + 1) или (6к – 1). Начиная с двух, каждое второе натуральное число кратно двум, а начиная с трех – каждое третье натуральное кратно трем. Значит, если на любом произвольном непрерывном участке ряда натуральных чисел больше четырех ,подчеркнуть одной линией все кратные двум и трем числа, а кратные и двум и трем одновременно (кратные шести) подчеркнуть двойной линией, то не подчеркнутыми останутся только нечетные числа сразу перед кратными шести и сразу после кратных шести. На этих, не подчеркнутых, местах располагаются как простые числа, так и кратные всем остальным. Но если каждое второе число, кратное произвольному простому числу, является четным, а каждое третье – кратно трем, и так далее, и могут располагаться на любом месте в зависимости от своей кратности, то простые числа располагаются только на не подчеркнутых, примыкающим к кратным шести, местам, и только на них, потому что они не кратны ни двум ни трем. То есть, полной закономерности расположения простых чисел эта схема не дает, но однозначно указывает, что простые числа могут соседствовать только с теми квадратами чисел, которые кратны шести. Так же, как и англичане, интересующиеся французским языком, могут быть лысыми, но это не взаимосвязано. Отсутствие зависимости между квадратами натуральных чисел и простыми числами подтверждается допустимостью, принятыми представлениями о структуре распространения простых чисел (о бесконечности количества простых чисел и снижения плотности их расположения с увеличением значений чисел в ряду натуральных чисел), существования отрезков ряда натуральных чисел с произвольно большим по максимальному размеру промежутком между соседними простыми числами. В том числе и таким, на котором произвольное простое число p_i больше квадрата предыдущего простого числа p_(i-1):

p_i > p²_(i-1)

Равно как и такого отрезка, на котором произвольное простое число больше куба предыдущего простого числа:

p_i > p³_(i-1)

И даже:

p_i > p⁴_(i-1)

Значит, на числовом отрезке, где:

p_i > p^к_(i-1)

где к – произвольное натуральное число больше 2;

условие третьей проблемы Ландау-Лежандра не выполняется.

Четвертая проблема Ландау: бесконечно ли множество простых чисел вида (n² + 1), где n – натуральное число.

При отсутствии наличия у нас полной закономерности расположения простых чисел, с учетом уменьшения плотности их распространения, неограниченности количества простых чисел, их привязанности к четным кратным шести, а также, что каждый шестой квадрат натурального числа кратен шести, вероятность того, что для произвольного простого числа вида p_i = (6к + 1), окажется, что 6к = n², где к и n – натуральные числа, довольно существенна, но, на данный момент, быть математически рассчитана не может.

01.12.2007 – 01.12.2009.

По утверждению Чебышева, что p_n+1 - p_n < 2*p_n

Весь ряд натуральных чисел от нуля до бесконечности можно условно разделить на три части:

1) участок ряда натуральных чисел от нуля (или трёх, не помню от какого значения начинает работать эта формула ) до некоторого простого числа k1_i считается участком с нормальной плотностью распределения простых чисел, если для всех простых чисел до порогового k1_i включительно, утверждение Чебышева выполняется, а для простого числа k1_i+1 не выполняется.

2) участок ряда натуральных чисел от простого числа k1_i+1 до простого числа k2_i считается участком с пониженной плотностью распределения простых чисел, если для простого числа k2_i утверждение Чебышева выполняется, а для всех простых чисел более k2_i, от k2_i+1 включительно, не выполняется. Из-за неравномерности изменения размеров числовых отрезков между соседними простыми числами, на участке ряда натуральных чисел с пониженной плотностью распределения простых чисел от порогового простого числа k1_i+1 до порогового простого числа k2_i, утверждение Чебышева выполняется не для всех простых чисел этого участка.

3) участок ряда натуральных чисел, от простого числа k2_i+1 включительно до плюс бесконечности, считается участком с низкой плотностью распределения простых чисел, если ни для одного простого числа, более или равного пороговом числу k2_i+1, утверждение Чебышева не выполняется.

 Для каждой гипотезы или утверждения существует свое условное деление и свои пороговые простые числа k1_i, k1_i+1, k2_i, k2_i+1, или другие, зависит от содержания утверждения.

Так вот, доказанная мной лемма не вываливает конкретные значения k1_i, k1_i+1, k2_i, k2_i+1, как магическая шкатулка, это не формула по поиску простых чисел, нет. Она позволяет доказать существование этих условных отрезков ряда натуральных чисел, описывая поведение простых чисел. По аналогии с утверждением Чебышева, и для трёх проблем Ландау - у них свои условия истинности, свои пороговые значения k1, k2.

факторизация: теория к Ферма и + новый. к Мысли2

моя теория к методу факторизации Ферма. 
плюс еще один метод факторизации.

Любое произвольное число можно выразить в виде:

z = x * y                                                                                                                     (1)

Принимаю: x, y, z – натуральные числа, x ≥ y, x ≠ 0, y ≠ 0, отсюда x ϵ ( ( √z ) ; z ), y ϵ ( 1 ; ( √z ) ), кроме этого, дополнительно ограничиваю, что z – не четное, не кратное 5, так как искать минимальный простой множитель для чётных, или заканчивающихся на 5 или 0, математически скучно, следовательно и множители x и y тоже нечетные. Также принимаю, что z не имеет целого корня квадратного. В таких условиях задача разложения числа z на множители сводится к поиску минимального простого числа, являющегося младшим множителем y > 1 методом перебора по формуле:

            x = z / y                                                                                                                    (2)

Так как количество простых чисел, например, менее 1 миллиона, составляет 78498 штук, то есть 7,85%, и с возрастанием значения чисел процентное содержание простых чисел уменьшается, а максимальное возможное значение меньшего простого множителя y = ( √z ), то теоретическая максимальная вычислительная сложность задачи поиска меньшего простого множителя в худшем случае составляет (0,08√z) раз выполнить деление по формуле2, с последовательным перебором в качестве делителя y простых чисел в диапазоне от 3 до √z включительно. Следует учесть, что деление не является вычислительно простым действием, а состоит из последовательного вычитания, и с увеличением значения y, количество базовых действий  для выполнения следующего деления увеличивается.

В общем случае принятых ограничений больший множитель x может являться как простым числом, так и составным. В последнем случае, для полученного не простого x, поиск составляющих простых множителей повторяется по выше описанной методике. Не существует зависимости количества составляющих простых множителей для числа от его размера или от количества составляющих его знаков.

Дополнительная практическая не вычислительная сложность использования не только данного метода при разложении на множители, но и любых других действий над большими числами заключается ещё и в  количестве составляющих знаков разбираемого числа. Не только простые действия с, например, 500-значными числами требуют значительных затрат времени, у меня вычисление корня квадратного из 600-значного числа занимает более часа времени, но и просто запись такого числа требует времени и усилий. Определение вычислительной сложности не меняется, и продолжает составлять всё те же менее (0,08√z). Но и 8% от такого числа является довольно ощутимым значением.

Для любого произвольного числа, помимо составляющих его простых множителей, всегда существует минимум одна пара связаных слагаемых a и b, удовлетворяющая требованиям:

            x = a + b

            y = a - b                                                                                                                    (3)

соответственно:

            a = ( x + y ) / 2

            b = ( x – y ) / 2                                                                                                          (4)

где x ≥ a > b; a ≠ b; a ≥ y.

Следовательно:

            z = x * y = ( a + b ) * ( a – b ) = a² - b²                                                                     (5)

В рамках установленных ограничений из формул(4):

            a = ( x + y ) / 2 = ( нечетное целое + нечетное целое ) / 2 = ( четное целое ) / 2 = целое

            b = ( x – y ) / 2 = ( нечетное целое - нечетное целое ) / 2 = ( четное целое ) / 2 = целое

То есть, для любого нечетного числа всегда существует как минимум одна пара целых связаных слагаемых. Каждая пара связаных слагаемых определяет (задаёт, характеризует, генерирует) только одно число. Для некоторых четных целых чисел не всегда существует пара целых связаных слагаемых,  а только дробные, но, повторюсь, в рамках рассматриваемой задачи четные числа меня не интересуют.

Исходя из формул(4) можно определить диапазон изменения связаных слагаемых a и b: 
a ϵ ( √z ; (( z + 1 ) / 2 ) ), b ϵ ( 0 ; (( z – 1 ) / 2 ) ); 
x_min = y_max = a_min = √z, b_min = 0, если √z имеет целое значение; 
x_max = z, y_min = 1, a_max = ( ( z + 1 ) / 2 ), b_max = ( ( z – 1 ) / 2 ), если z простое число.
 Отсюда очевидно, что диапазоны изменения связаных слагаемых a и b значительно превышают диапазон изменения меньшего простого множителя y, что делает вычислительную сложность поиска их значений методом перебора не конкурентной, по сравнению с перебором возможных значений y.

Исходя из формулы(5), возможна реализация поиска значений связаных слагаемых для исследуемого числа графическим способом на основании теоремы Пифагора. Данный вариант осложнен условием, что в общем случае (√z) не является целым числом, но проверить несколько найденных пар потенциальных значений проще и быстрее, чем последовательный перебор всех значений. Кроме того, лично я не представляю, как оценивать и сравнивать вычислительную сложность данного метода при реализации его инструментами разных графических приложений и программ.

Общеизвестно, что все числа можно условно разделить на ряды кратности какому-либо числу, на которое они делятся нацело. Но целые числа, так же условно, можно разделить на несколько более сложно зависимые ряды условной кратности по связаным слагаемым – ряды чисел с одинаковым меньшим (или большим) связаным слагаемым. Ряд чисел с одинаковым меньшим связаным слагаемым b представляет собой бесконечную арифметическую прогрессию второго порядка: шаг прогрессии (h) у нее не постоянный, а является арифметической прогрессией с постоянным шагом 2. При этом:

            n = 2b + 1                                                                                                                 (6)

            b = ( n – 1 ) / 2,

где n – первый член z₁ арифметической прогрессии второго порядка Z для исследуемого меньшего связаного слагаемого b, то есть первый член ряда кратных меньшему связаному слагаемому.

            d = 2 b + 3 = n + 2,                                                                                                   (7)

где d – первый член h₁ арифметической прогрессии H, являющейся шагом арифметической прогрессии второго порядка Z для исследуемого меньшего связаного слагаемого b.

Приведу примеры, исходя из формул(3) и ограничения (a > b).

Для b = 0

a	x	y	z	h
1	1	1	1
2	2	2	4	3
3	3	3	9	5
4	4	4	16	7
5	5	5	25	9
6	6	6	36	11
7	7	7	49	13

Для b = 1

a	x	y	z	h
2	3	1	3
3	4	2	8	5
4	5	3	15	7
5	6	4	24	9
6	7	5	35	11
7	8	6	48	13
8	9	7	63	15

Для b = 2

a	x	y	z	h
3	5	1	5
4	6	2	12	7
5	7	3	21	9
6	8	4	32	11
7	9	5	45	13
8	10	6	60	15
9	11	7	77	17

Для b = 3

a	x	y	z	h
4	7	1	7
5	8	2	16	9
6	9	3	27	11
7	10	4	40	13
8	11	5	55	15
9	12	6	72	17
10	13	7	91	19

Отсюда: каждое нечетное число, и некоторые из четных, можно разложить на конечный ряд H последовательных нечетных чисел, меньший член которого равен n, количество членов этого ряда равно меньшему простому составляющему множителю y. Для нечетных чисел (а возможно, и для некоторых четных) составляющий множитель x является членом этой прогрессии с номером
            j = ( ( y – 1 ) / 2 )                                                                                                      (8)

при этом:

            x = n + 2j = n + y – 1                                                                                                (9)

При обычном делении из делимого z y раз вычитается число  x, то есть число z дробится на y частей одинакового размера x. По аналогии, с учетом, что любое нечетное число можно раздробить на y последовательно возрастающих частей, при ступенчатом делении, произвольное нечетное число z делится на y нечетных последовательно увеличивающихся частей, меньшая часть из которых равна n. Данный факт можно использовать для графической реализации поиска конечного ряда H последовательных нечетных чисел с помощью «ломаных» или «столбиков», но, повторюсь, лично я не представляю, как оценивать и сравнивать вычислительную сложность данного метода при реализации его инструментами разных графических приложений и программ. Аналитически данный способ факторизации чисел будет рассмотрен в Варианте_2.

Ряд условной кратности чисел Z большему связаному слагаемому a является конечным, ограниченным условиями (a > b), (a > 0).

Для a=1, z_min=z_max= a² = 2a-1

b	x	y	z	h
0	1	1	1

Для a=2

b	x	y	z	h
0	2	2	4
1	3	1	3	1

Для a=3

b	x	y	z	h
0	3	3	9
1	4	2	8	1
2	5	1	5	3

Для a=4

b	x	y	z	h
0	4	4	16
1	5	3	15	1
2	6	2	12	3
3	7	1	7	5

Для a=5

b	x	y	z	h
0	5	5	25
1	6	4	24	1
2	7	3	21	3
3	8	2	16	5
4	9	1	9	7

Для a=6

b	x	y	z	h
0	6	6	36
1	7	5	35	1
2	8	4	32	3
3	9	3	27	5
4	10	2	20	7
5	11	1	11	9

Для a=7

b	x	y	z	h
0	7	7	49
1	8	6	48	1
2	9	5	45	3
3	10	4	40	5
4	11	3	33	7
5	12	2	24	9
6	13	1	13	11

Исходя из существующих ограничений, количество членов ряда условной кратности чисел Z большему связаному слагаемому равно i = a, z ϵ ( a² ; 2a - 1). Сам ряд представляет собой прогрессию второго порядка и изменяется от максимального, равного z = a² при b = 0, до минимального, равного z = ( 2a - 1) при b = (a - 1), с шагом в виде арифметической прогрессии с h = 2, минимальный член которой всегда равен 1. В отличие от ряда условной кратности меньшему связаному слагаемому b, где минимальный член зависит от b. Это дает возможность не искать перебором, а высчитать связаное слагаемое a для любого нечетного числа, зная только само число. К чему, собственно и пришел Ферма, только с более простой аргументацией.
   Вариант_1 - оказался методом факторизации Ферма.
Для этого необходимо выполнить определенный набор действий, не зависящий от величины числа:
 - вычислить c, равное a_min, равное целой части корня квадратного  от исследуемого числа z;

 - сформировать таблицу квадратов чисел на промежутке от c = a_min= (целая часть корня квадратного от z) до a_max = (( z + 1 ) / 2), либо берем часть уже существующей таблицы;

 - последовательно наплюсовываем к z последовательные нечетные числа, начиная с 1. Каждую полученную сумму проверяем на наличие целого корня квадратного, сравнивая с данными в таблице квадратов. Наплюсованная сумма с целым корнем квадратным и является a², сумма наплюсованных слагаемых – это и есть b²;

 - смотрим в таблице квадратов значение корня квадратного из вычисленного b²;

 - по формулам(3) определяем составляющие множители; 
  - всё, расчет закончен.

Вероятно, формирование таблицы квадратов и наплюсовывание к z последовательных нечетных чисел имеет смысл производить на разных вычислительных машинах параллельно. Для формирования таблицы квадратов можно пользоваться только действием сложения, не используя умножения.
   Вариант_2 - чужое авторство данного способа мне не известно. Прошу уведомить меня, если данный способ факторизации уже описан.

Задача разложения исследуемого числа z на составляющие его простые множители, исходя из свойств меньшего связаного слагаемого b, представляет собой поиск подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z. У данной задачи есть три случая развития решения.

1) Если исследуемое число z имеет целое значение корня квадратного √z=i=x=y. В этом случае, в соответствии со свойствами связаных слагаемых, b=0 и меньший член подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, всегда равен единице. Тогда, решение задачи сведется к суммированию последовательных нечетных чисел, начиная с единицы, до достижения z=k=1+3+5+…+ n_i. Это вычислительно самый простой частный случай, алгоритм решения которого содержит наименьшее количество действий.

Блок_1 . . . . . . . . . . . . . . . m=1,n=3,i=2,z,l=1

. .переход к блоку_2

Блок_2 . . . . . . . . . . . . . . . k=m+n

. .переход к блоку_3

Блок_3 . . . . . . . . . . . . . . . если z=k, то переход «да» к блоку_6, иначе переход «нет» к блоку_4

. .переход «нет» от блока_3 к блоку_4

Блок_4 . . . . . . . . . . . . . . . i=i+1,n=n+2

. .переход к блоку_5

Блок_5 . . . . . . . . . . . . . . . k=k+n

. .переход от блока_5 к блоку_3

. .переход «да» от блока_3 к блоку_6

Блок_6 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

            Рис.1 - Блок-схема к варианту_1

2) Общий случай: исследуемое число z не имеет целого значения корня квадратного и неизвестно, является ли оно простым числом. В этом случае, в блок-схему алгоритма решения добавляется еще один критерий оценки состояния переменной k по отношению к исследуемому числу z и блок вычислений из трех действий. Суммирование последовательных нечетных чисел, начиная с единицы, продолжается до достижения z<k=1+3+5+…+ n_i, после чего происходит последовательное уменьшение суммы последовательных нечетных чисел на меньший член подмножества или прибавление следующего нечетного числа, в зависимости от проверки соотношения значений исследуемого числа z и переменной k после каждого блока вычислений. Вычисления будут продолжаться до тех пор, пока значение переменной k не станет равным числу z и переменная i, являющаяся счетчиком количества суммированных последовательных нечетных чисел, примет значение, равное y – меньшему составляющему простому множителю исследуемого числа z. Этот вариант решения задачи разложения исследуемого числа z на составляющие его простые множители содержит больше вычислительных действий, чем в первом варианте, когда исследуемое число имеет целое значение корня квадратного. В худшем случае, вычисления будут продолжаться до i=3, n_max=((z/3)+2), так как, в соответствии с формулой(9): при y=3, x=(z/3)=n+y-1=n+3-1=n+2, тогда n=((z/3)-2)=n₁, n₂=n+2=(z/3), n₃= n₂+2=n_max=((z/3)+2).

Блок_1 . . . . . . . . . . . . . . . m=1,n=3,i=2,l=1,z

. .переход к блоку_2

Блок_2 . . . . . . . . . . . . . . . k=m+n

. .переход к блоку_3

Блок_3 . . . . . . . . . . . . . . . если z=k, то переход «да» к блоку_9, иначе переход «нет» к блоку_4

. .переход «нет» от блока_3 к блоку_4

Блок_4 . . . . . . . . . . . . . . . если z>k, то переход «да» к блоку_7, иначе переход «нет» к блоку_5

. .переход «нет» от блока_4 к блоку_5

Блок_5 . . . . . . . . . . . . . . . k=k-l,i=i-1

. .переход к блоку_6

Блок_6 . . . . . . . . . . . . . . . l=l+2

. .переход от блока_6 к блоку_3

. .переход «да» от блока_4 к блоку_7

Блок_7 . . . . . . . . . . . . . . . i=i+1,n=n+2

. .переход к блоку_8

Блок_8 . . . . . . . . . . . . . . . k=k+n

. .переход от блока_8 к блоку_3

. .переход «да» от блока_3 к блоку_9

Блок_9 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

Рис.2 - Блок-схема к варианту_2

3) Если исследуемое число z является простым числом, то вычисление алгоритма не останавливается при i=3, n_max=((z/3)+2) и продолжается до i=1, n_max=z. Вычислительно это самый сложный вариант решения задачи, поскольку проверяется в 3 раза больше значений переменной k. При добавлении после блока_7 критерия проверки n=((z/3)+4), с остановкой выполнения алгоритма при его выполнении и выведением соответствующего сообщения, отсекаются лишние бессодержательные повторения вычислительных действий, уравниваются вычислительная сложность худшего случая решения задачи в общем случае и вычислительная сложность решения задачи, когда число z является простым числом. 

Блок_1 . . . . . . . . . . . . . . . m=1,n=3,i=2,l=1,z

. .переход к блоку_2

Блок_2 . . . . . . . . . . . . . . . k=m+n

. .переход к блоку_3

Блок_3 . . . . . . . . . . . . . . . если z=k, то переход «да» к блоку_10, иначе переход «нет» к блоку_4

. .переход «нет» от блока_3 к блоку_4

Блок_4 . . . . . . . . . . . . . . . если z>k, то переход «да» к блоку_7, иначе переход «нет» к блоку_5

. .переход «нет» от блока_4 к блоку_5

Блок_5 . . . . . . . . . . . . . . . k=k-l,i=i-1

. .переход к блоку_6

Блок_6 . . . . . . . . . . . . . . . l=l+2

. .переход от блока_6 к блоку_3

. .переход «да» от блока_4 к блоку_7

Блок_7 . . . . . . . . . . . . . . . i=i+1,n=n+2

. .переход к блоку_8

Блок_8 . . . . . . . . . . . . . . . если n<((z/3)+4), то переход «да» к блоку_9, иначе переход «нет» к блоку_11 

. .переход «да» от блока_8 к блоку_9

Блок_9 . . . . . . . . . . . . . . . k=k+n

. .переход от блока_9 к блоку_3

. .переход «да» от блока_3 к блоку_10

Блок_10 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

. .переход «нет» от блока_8 к блоку_11

Блок_11 . . . . . . . . . . . . . . . вывод данных, конец алгоритма

          Рис.3 - Блок-схема к варианту_3

Конечным искомым решения задачи является определение количества i членов подмножества последовательных нечетных чисел, дающих в сумме значение исследуемого числа z, либо выведение сообщения о том, что оно является простым.

Решение задачи поиска подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, можно реализовать и при помощи табличного приложения, например Excel.  Создаются два столбца. В одном столбце, например А, ячейки заполняются сверху вниз последовательными нечетными числами по возрастанию от 1 до ((z/3)+4) – для предотвращения лишних итераций когда число z является простым числом. В соседнем столбце, например В, в ячейки, кроме верхней, вписываются формулы. Так, пусть ячейка А1 – пустая, в ячейке В1 записывается значение z. Тогда, А2=1, А3=3, А4=5 и так далее. В остальные ячейки столбца В записывается формула «=(ячейка сверху)минус(ячейка слева)». В ячейке В2 записывается формула «=В1-А2», в ячейке В3 записывается «=В2-А3», и так далее. После формирования столбцов выполняются формулы и проверяется, принимает ли какая-либо ячейка в столбце В значение «ноль». Если «да», то вычисления закончены - это случай_1 развития решения задачи,- определяется количество не пустых ячеек в столбце А от строки, в которой формула в ячейке столбца В приняла значение «ноль», и в вверх до ячейки А1 включительно. Иначе, продолжается поиск последовательных нечетных чисел, сумма которых равна исследуемому числу z. Для этого удаляется самое верхнее, наименьшее нечетное число в столбце А и проверяется, принимает ли какая-либо ячейка в столбце В значение «ноль». Если «да», то вычисления закончены, если «нет», то удаление верхнего нечетного в столбце А и проверка столбца В повторяется до тех пор, пока какая-либо ячейка в столбце В примет значение «ноль» либо до удаления последнего нечетного числа в столбце А, равного ((z/3)+4) – что значит, что число z является простым числом. С помощью макросов весь описанный процесс в табличном приложении Excel полностью программируется и выполняется автоматически.

Также этот алгоритм можно выполнять в табличном приложении Excel в более развернутом виде.

Для удобства пользователя, верхние три строки закрепляются. Сначала, ставим рабочие пометки: в ячейке C1 пишем «z», в ячейке E1 пишем «-», в ячейке G1 пишем «+», в ячейке I1 пишем «z-+». Затем:

- в ячейку C2 записываем исследуемое число z;

- в ячейку E2 записываем формулу «=сумм(D:D)» - формула возвращает сумму всех чисел в ячейках столбца D;

- в ячейку G2 записываем формулу «=сумм(F:F)» - формула возвращает сумму всех чисел в ячейках столбца F;

- в ячейку I2 записываем формулу «=C2-E2+G2» - формула уменьшает исследуемое число на величину суммы чисел в ячейках столбца D и увеличивает полученную разницу на величину суммы чисел в ячейках столбца F – основной вычислительный процесс;

- в ячейку E3 записываем формулу «=счёт(D:D)» - формула возвращает количество не пустых ячеек столбца D – перебор величины связаного слагаемого a;

- в ячейку G3 записываем формулу «=счёт(F:F)» - формула возвращает количество не пустых ячеек столбца F – перебор величины связаного слагаемого b;

- в ячейку I3 записываем формулу «=E3-G3» - формула считает разницу между количеством не пустых ячеек столбца D и количеством не пустых ячеек столбца F – разницу между текущей величиной связаного слагаемого a и текущей величиной связаного слагаемого b, то есть перебор величины меньшего составляющего множителя y;

- в ячейку K3 записываем формулу «=E3+G3» - формула считает суммарное количество не пустых ячеек столбца D и не пустых ячеек столбца F – сумму текущей величины связаного слагаемого a и текущей величины связаного слагаемого b, то есть перебор величины большего составляющего множителя x.

 Данный вариант реализации алгоритма решения исследуемой задачи более информативен, чем рассматриваемый ранее, и позволяет, как избежать постоянного перемещения от начала подмножества последовательных нечетных чисел в его конец, опять в начало и так далее, так и отсечь, при необходимости, вспомогательные вычислительные действия. Для выполнения решения, в ячейки столбца D в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке I2 не появится ноль, либо отрицательное число. Если на данном этапе выполнения решения в ячейке I2 появится ноль, значит, исследуемое число z имеет целое значение корня квадратного, и значения в ячейках будут иметь следующий вид: E3=a=I3=y=K3=x – они будут равны значению корня квадратного из числа z, в ячейке G3=b=0. Если же на данном этапе выполнения решения в ячейке I2 появится отрицательное число, то в ячейки столбца F в порядке сверху вниз вносятся последовательные нечетные числа, в порядке возрастания, начиная с единицы, до тех пор, пока в ячейке I2 не появится ноль, либо положительное число. Теперь получение нуля ячейке I2 будет свидетельствовать о нахождении таких значений E3=a и G3=b, что ((E3=a)-(G3=b)=(I3=y)) и ((E3=a)+(G3=b)=(K3=x)), при которых ((I3=y)*(K3=x)=(C2=z)=(E2-G2)). В дальнейшем решении выполняется правило: если в ячейке I2 появляется отрицательное число, то вносим в следующую по порядку ячейку столбца F следующее по порядку нечетное число, если в ячейке I2 появится положительное число, то вносим в следующую по порядку ячейку столбца D следующее по порядку нечетное число. Так должно продолжаться до появления в ячейке I2 нуля, свидетельствующего об окончании вычислений, или до появления в ячейке I3=y значения 2, свидетельствующего о том, что исследуемое число z является простым, и дальнейшие вычисления нецелесообразны.

Как видно из описания выполняемых действий, вычислительная сложность решения задачи поиска подмножества последовательных нечетных чисел, сумма которых равна исследуемому числу z, она же задача разложения исследуемого числа z на составляющие множители, по сути, одинакова для различных вариантов развития решения:

1) Если исследуемое число z имеет целое значение корня квадратного. В этом случае от исследуемого числа z будет (E3=a=I3=y=K3=x=√z)-раз произведено вычитание.

2) Если исследуемое число z не имеет целое значение корня квадратного. В этом случае от исследуемого числа z будет (K3=x)-раз произведено вычитание и сложение.

3) В случаях, если исследуемое число z оказывается простым числом, продолжительность вычислений, количество вычислительных действий, зависит от того, как настроен стоп-маркер. Это может быть значение c=((z/3)+4), либо появление в ячейке I3=y значения 2, либо что-либо еще. В любом случае, вычислительная сложность данного варианта решения будет порядка ((z/3)+2). 

01.2008г. - 21.07.2018г.