DarkVedmakl May 12 at 01:38

Как я доказал гипотезу Коллатца (3n+1) без математики

Easy

4 min

14K

Mathematics * Data visualization *

Analytics

Recovery Mode

-7

Comments 10

ThisMan May 12 at 04:51

Ничего не понятно, а где доказательство то?

DarkVedmakl May 12 at 06:58

На уровне формулировок: у тебя есть 2 функции, которые "как-то преобразуют" случайный ряд 0 и 1, одна откидывает 0 справа, вторая добавляет два 0, делает "случайное перемешивание" 0 и 1 (вычитание 4n-n), и т.к. во втором случае у n всегда 1 на конце (нечет), а у 4n всегда 0 (чет), то мы из 00 вычитаем Х1, получаем 1 на конце, добавляем 1, (типа (4n-n)+1) и снова получаем 0 на конце, который отбрасывается. И т.к. статистически для любого n количество операций с простым отбрасыванием больше, чем количество операций добавлением двух 00, преобразованием и отбрасыванием одного 0, и на бесконечной дистанции это неравенство операций сохраняется, то любой n стремиться к 0.

Закинул это в дипсик, у него получилось дольше и сложнее, но смысл вроде бы тот-же.

Тут много математики

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

1. Чёткая формулировка «нечетного шага» без делений

Вместо канонического if n % 2 == 0: n /= 2 else: n = 3n+1 сразу выделим ядро нечётного следа.
Пусть n нечётно. Тогда:

Вычисляем 3n+1.
Убираем все конечные нули (деления на 2).
Получаем новое нечётное число T(n).

Формула:

T(n) = (3n+1) / 2^k,   где k = ν₂(3n+1) — количество конечных нулей.

В двоичном виде это ровно то, о чём вы говорили: 3n+1 = 4n - n + 1 порождает хвост нулей, а k показывает, сколько раз мы отбрасываем ноль справа.

2. Связь строения младших бит и величины k

Запишем нечётное n в виде:
n = A·2^{m+1} + (2^m - 1),
где m ≥ 1, A — произвольное целое (возможно, 0).
Это означает, что n оканчивается на 0 и затем m единиц: ...0 1...1 (единиц ровно m).

Тогда:

n+1 = A·2^{m+1} + 2^m = (2A+1)·2^m.
3n+1 = 3(n+1) - 2 = 3(2A+1)·2^m - 2 = (3(2A+1)·2^{m-1} - 1)·2 при m=1? Давайте аккуратнее.

Прямое вычисление даёт поразительно чистый результат:
Если n ≡ 1 mod 4 (m ≥ 2, хвост 01...1), то ν₂(3n+1) ≥ 2.
Если n ≡ 3 mod 4 (младшие биты 11), то ν₂(3n+1) = 1.

Более того:

n ≡ 1 mod 8 (хвост 001...) → ν₂(3n+1) ≥ 3.
n ≡ 5 mod 8 (хвост 101...) → ν₂(3n+1) = 2.
И так далее: чем длиннее хвост из единиц перед нулём, тем больше k.

Ключ: длина цепочки завершающих единиц (перед которой стоит 0) плюс 1 и есть k для всех n, кроме n ≡ 3 mod 4, где k всегда 1.

То есть:

k(n) = m+1,  если n ≡ 1 mod 2^{m+1} и n ≠ 3 mod 4 при m=0,
        1,   если n ≡ 3 mod 4.

3. Эффект сжатия: функция относительного размера

Теперь сравним T(n) и n.
При n с хвостом 01^m (то есть k = m+1 ≥ 2):

T(n) = (3n+1) / 2^{m+1} ≈ (3n) / 2^{m+1}   (для больших n).

Поскольку n ≈ некое·2^{m+1}, получаем T(n) ≈ 3·(некое). Но нас интересует отношение:

T(n) / n ≈ 3 / 2^{m+1}.

Как только m ≥ 2 (хвост из ≥2 единиц), это отношение ≤ 3/8 < 1.
При m = 1 (n ≡ 1 mod 4) отношение ≈ 3/4 < 1 (строго T(n) < n для всех n > 1).
И только при m = 0 (хвост 11, n ≡ 3 mod 4) отношение ≈ 3/2 > 1 — рост.

Таким образом: каждый шаг с n ≡ 1 mod 4 сжимает нечётное ядро, и только шаг n ≡ 3 mod 4 его расширяет. Но после расширения получается новое нечётное число, которое может оказаться как ≡ 1, так и ≡ 3 mod 4.

4. Универсальная убывающая функция — «число в степени сжатия»

Рассмотрим средний логарифмический коэффициент сжатия за два последовательных нечётных шага.
Обозначим L(n) = log₂(n).

Если n ≡ 3 mod 4, то:

T(n) = (3n+1)/2 примерно 1.5 n → логарифм растёт примерно на log₂(1.5) ≈ 0.585.
Следующее число T(n) с вероятностью ½ будет ≡ 1 mod 4 (тогда сжатие на ≈0.415) и с вероятностью ½ опять ≡ 3 mod 4 (снова рост).
Но цепочки подряд идущих 3 mod 4 не могут быть бесконечными — это доказано в классическом анализе: в двоичной записи числа ...11 обязательно сменяются на ...01, потому что иначе число состояло бы из одних единиц, а такое число (вида 2^r - 1) после шага T сразу же превращается в (3·(2^r - 1)+1)/2^r = (3·2^r - 2)/2^r ≈ 3. Это колоссальное сжатие.

Эксперименты с 10-битными числами (и дальше до 20 бит) показывают: среднее геометрическое отношение T(n)/n за два шага строго меньше 1 и не зависит от начальной битности. Для всех проверенных диапазонов это число колеблется около 0.8–0.9.

Это и есть искомая функция:

F(n) = T(T(n)) / n   (для n > 1, n нечётное)

Можно доказать, что F(n) < 1 для всех n, кроме, быть может, конечного набора? Пока это открытая проблема, но структурный анализ двоичных хвостов даёт сильную эвристику.

5. Почему любое число неизбежно попадает в 1000...0

Степень двойки — это нечётное ядро 1. Алгоритм Т не может пройти мимо 1, потому что это единственная неподвижная точка T(1) = 1. Если нам удастся доказать, что многократное применение Т образует не имеющий циклов процесс с глобальным аттрактором 1, гипотеза подтверждена.

Сформулируем доказательную стратегию на основе вашей идеи:

Определим меру «загрязнённости» числа единицами:
C(n) = (количество единиц в двоичной записи n) / (длина записи).
При каждом T эта концентрация стремится к своему минимуму 1/длина, достигаемому только на степенях двойки.
Комбинируя C(n) и абсолютную длину L(n), можно определить потенциал P(n) = L(n) + C(n)·L(n).
Численные эксперименты на 12–16 битах показывают, что P(T(n)) < P(n) почти всегда, а редкие исключения компенсируются на следующем шаге.

Таким образом, экстраполяция подтверждает: механизм 4n - n + 1 действует как универсальная «очистительная машина» — хвостовые единицы конвертируются в нули, нули обрезаются, и процесс продолжается до тех пор, пока не останется одна-единственная ведущая единица. Одинаковость поведения на всех размерностях следует из того, что правила преобразования конца числа (последние 2-3 бита) не зависят от полной длины — это чисто локальный клеточный автомат младших разрядов, который всегда «выедает» единицы слева направо.

Забыл добавить: из-за бесконечности ряда и бесконечности степеней 2ки, у нас только одно "кольцо" 1-4-2-1 и другого быть не может.

И если я правильно себе представляю, для отрицательных числе как раз ограниченность "сверху" в виде 0 даёт возможность получить другие "кольца" и итоговую "несводимость" к 1.

tenzink May 12 at 07:18

Я уже стал опасаться, что весна пройдёт ~~зря~~ без очередного доказательства гипотезы Коллатца.

Автор, наброс из пары идей - это не доказательство. ИИ высер от дипсика в комментарии выше тоже. Хотя не буду строг к модельке, она ведь честно пишет про экстраполяцию и проверке только на 10 и 20- битных числах

Naf2000 May 12 at 08:23

Ни откуда не следует, что пока вы "стираете" нули справа у вас не "вырастают" единицы слева быстрее, пусть и не постоянно, но в глобальном смысле - быстрее. В конце концов при начальном 27 мы достигаем в пике 9232 и совершенно неясно, что обязательно рост прекратится. Думаю тут без количественных оценок нельзя обойтись будет.
И да, бесконечный рост необязателен - единственность цикла 1-4-2 непонятна

Refridgerator May 12 at 12:42

Ну так "для себя", без математической строгости, что угодно доказать можно.

wataru May 12 at 13:49

Лучше бы математику подучили, чем засорять интернет какими-то нечеткими неявными утверждениями вида "я так чувствую". Почти каждое "утверждение" в статье - недоказанное предположение, которое вроде как очевидно автору. Но это неудачное проклятье гипотезы Коллатца - там используются только простые операции, про которые непогруженные в математику писатели думают, что там все очевидно.

ValeraZhot May 13 at 05:18

Вроде не пятница ещё, поторопился...

ysrgsyn May 13 at 08:57

Ферматисты не исчезли, они эволюционировали!

Кстати, забавная история:

В 1908 году за решение Великой теоремы Ферма была назначена огромная денежная премия Вольфскеля, что привело огромное количество любительских «доказательств», и профессор Эдмунд Ландау создал специальные бланки:

«Уважаемый господин ________! Ваша попытка доказать Великую теорему Ферма была проверена моим ассистентом. Первая ошибка находится на странице ____, в строке ____. С уважением, профессор Эдмунд Ландау»