кокозательство сиракузной херни

Утверждение:
Рассмотрим произвольное натуральное число n.
Если n четное, поделим его на 2 (n/2).
Если n нечетное, умножим его на 3 и добавим 1 (3n + 1).
Продолжим выполнять шаги 2 и 3 для полученных чисел.
Гипотеза Коллатца утверждает, что, несмотря на начальное число n, рано или поздно последовательность достигнет значения 1 и будет циклически повторяться {4, 2, 1}.

Доказательство:
1. Упростим схему Коллатца:

1.1. Определим две операции с условиями их выполнения:
A: N/2		(условие выполнения: для четных чисел N)
B: (3N+1)	(условие выполнения: для нечётных чисел N )

1.2. Так как B выполняется только для нечетных, то её результат - всегда число четное,
а для четных, затем - применяется операция A.

1.3. Значит, за B, всегда следует A, в последовательности Коллатца, как BA, и не может быть двух последовательных операций BB.

1.4. Таким образом, определим комбинированную операцию, с условием её выполнения:
C = BA: (3N+1)/2 (условиее выполнения: только для нечётных чисел N).

1.4.1. Условие операции C - это условие операции B, с которой она начинается, и которое поэтому - применяется тоже для C.

1.5. Таким образом, в схеме Коллатца, не может быть последовательных операций BB и BC тоже, а только АC, ACA, ACC, и так далее...

1.6. Cледовательно, в схеме Коллатца, любая последовательность операций A и B: (ABABABAAA...),
согласно условиям, сводится к последовательности только двух операций A и C: (ACCAA...).

1.7. Следовательно, в дальнейшем, можно рассматривать только последовательности операций A и C.

2. Представим N в виде 3q+r.

2.0. Любое N можно представить в виде aq+r.

2.1. Любое N можно представить в виде 3q+r

2.3. И чётные, и нечётные числа N, могут иметь вид 3q+0, 3q+1, 3q+2, в зависимости от четности-нечётности q.

2.4. Иллюстрация множеств различных четных и нечётных чисел вида 3q+r:
3q+1	нечетные	1	7	13	19	25	31 ... 3q+r + 6 = 3(q+2) + r; r = 1
3q+2	четные		2	8	14	20	26	32 ... 3q+r + 6 = 3(q+2) + r; r = 2
3q+0	нечетные	3	9	15	21	27	33 ... 3q+r + 6 = 3(q+2) + r; r = 0
3q+1	четные		4	10	16	22	28	34 ... 3q+r + 6 = 3(q+2) + r; r = 1
3q+2	нечетные	5	11	17	23	29	35 ... 3q+r + 6 = 3(q+2) + r; r = 2
3q+0	четные		6	12	18	24	30	36 ... 3q+r + 6 = 3(q+2) + r; r = 0

2.5. Таким образом, все 6 множеств, содержат все натуральные числа от 1 до N, так как содержат все комбинации представлений 3q+r.

3. Определим термины, для доказательства:

3.1. Длина числа:
Это количество разрядов представления числа в n-ричной системе счисления.
Чем больше количество разрядов, тем длиннее число.

3.2. Информационная сложность числа (в теории информации):
Это мера степени неопределенности или неожиданности в последовательности цифр,
измеряемая с использованием энтропии.
Чем выше энтропия, тем больше информационная сложность.
Энтропия для дискретной случайной переменной XX определяется как:
H(X)=−∑ P(x_i) log_2 P(x_i)
где P(x_i) - вероятность появления символа x_i в последовательности.

3.3. Рост информационной сложности числа:
Это увеличение неожиданности в последовательности цифр числа.
Когда последовательность цифр становится менее предсказуемой или более разнообразной,
информационная сложность числа растет.

3.4. Снижение информационной сложности числа:
Это снижение неожиданности в последовательности цифр с уменьшением длины числа.
Когда последовательность цифр становится более упорядоченной или менее разнообразной, информационная сложность числа снижается.

3.5. Неувеличение информационной сложности числа:
Это сохранение той же степени неожиданности в последовательности цифр, даже при росте длины числа.
Когда увеличивается количество разрядов числа, но структура и разнообразие последовательности цифр остаются примерно такими же,
информационная сложность числа не увеличивается значительно.

4. Рассмотрим влияние операций на термины.

4.1. В последовательности операций гипотезы Коллатца, может применяться операция A (1.6.).
Она уменьшает и количество информации, и информационную энтропию числа, а значит уменьшает и информацию о изначальном числе.
Для четных чисел, вида:
3q+0, q - четное
3q+2, q - четное
3q+1, q - нечетное
и в первых двух случаях, когда q - четное, в результате этой операции /2 - уменьшается информация q тоже,
так как q' = q/2, и это двоичный свдиг вправо, на один бит, для q.
В третьем случае - просто уменьшается число, двоичным сдвигом вправо, что тоже уменьшает и количество информации, и информационную энтропию.

4.2. Рассмотрим операцию C
Пусть N - нечетное, согласно условию выполнения операции C (1.3)
(3N+1)/2 = (3(N-1) + 3 + 1)/2 = (3(N-1) + 4)/2 = 3(N-1)/2 + 2 = 3((N-1)/2) + 2 = 3q+2; q = (N-1)/2
При этом, результат операции - всегда число вида 3q+2, где q - как четное, так и нечётное.

4.2.2. Таким образом, операция С эквивалентна операции 3((N-1)/2) + 2, где q = (N-1)/2.

4.2.3. Рассмотрим внимательнее, что происходит при этой операции 3((N-1)/2) + 2:
1) вычисляется q = (N-1)/2, битовым сдвигом N, вправо, в двоичной системе счисления.
2) вычисляется результат: 3q+2, тритовым сдвигом влево, с установкой младшего трита в 2

4.2.4. Рассмотрим, как компоненты этой операции влияют на информацию результата:
4.2.4.1. 1) Вычисление q - битовый сдвиг вправо, уменьшает и количество информации и информационную энтропию числа, что очевидно.

4.2.4.2. 2) Вычисление 3q+2 - тритовый сдвиг влево с установкой младшего бита, хоть и увеличивает количество информации,
но он не увеличивает информационную энтропию числа.

Если информационная сложность числа измеряется энтропией, и операция 3q+2 сохраняет остаток по модулю 3,
то она не вносит дополнительной неожиданности или структурной сложности в число.
Таким образом, можно утверждать, что эта операция не увеличивает информационную сложность числа.

4.2.5. Операция С, во двумя подоперациями - уменьшает информационную энтропию результата.

4.3. Значит, обе операции C и A - уменьшают информацию о изначальном числе.

5. Таким образом, из-за уменьшении информации, любая последовательность операций C и A, за исключением цикла {4, 2, 1},
всегда уменьшает информацию о изначальном числе.

6. Это значит, что не существует бесконечных последовательностей по схеме Коллатца, за исключением цикла, который является исключением.

7. Значит, результатом любой последовательности операций, в том числе и в цикле,
результатом будет число 1 = 3*q+1, где q = 0, и не содержит никакой информациию.

8. Изначальное утверждение - доказано. Гипотеза Коллатца - доказана.


P.S. Про неувеличение информационной сложности:
Это потому, что в троичной системе, число вида 3q+2 = abсabc...2, где q = abcabc..., и сами триты числа - существенно не меняются.
Это значит, что подоперация 3q+2, внутри операции C содержащаяся,
хоть и увеличивает количество информации,
однако она не увеличивает информационную энтропию числа-результата - но в троичной системе счисления, что тоже очевидно, из представления "abcabc...2"
Там, триты q (abcabc...) - остаются те же самые, и просто происходит сдвиг q влево на один троичный разряд, и добавляется двойка в младший разряд.
Вообще эту подоперацию 3q+2 можно интерпретировать даже не как изменение свойств самого числа, и его информации, и информационной энтропии,
а как сдвиг самого множества чисел, и/или - поворот этого множества.
То есть информация в самом числе-результате, она не увеличивается, в результате этой подоперации 3q+2, что очевидно, но в троичной системе счисления.

Хотя длина числа увеличивается на один разряд в троичной, но сама информация существенно не изменяется.
q как было в троичной, так и осталось - те же триты,
просто оно сдвинулось на разряд, и добавилась константная двойка, в младший разряд.
Это не увеличивает количество информации внутри числа q,
в то время как другие подоперации и операции тоже постоянно уменьшают не только саму длину q (количество информации в q),
но и количество единичных бит в нём (уменьшение числа единичных бит, внутри него).
То есть, тот факт, что после 3q+2, число выглядит "более непредсказуемым" в двоичной,
вовсе не означает, что на самом деле, информация внутри числа увеличивается, что очевидно - но в троичной.

Результат будет иметь тот же остаток по модулю 3, что и исходное число N, и, следовательно, эта операция не меняет информационную сложность числа.