Расширенная гипотеза Коллатца, или проблема «nx+1» — часть I03.10.2023 20:17

Вероятно, все уже слышали про гипотезу »3х+1», или гипотезу Коллатца. Эта гипотеза по праву считается самой простой нерешенной проблемой.

Правила очень простые. Берём любое число. Если оно нечётное, умножаем его на 3 и добавляем 1. Если оно чётное, делим на 2. Повторяем то же самое действие с результатом. Обязательно ли в конце мы получим 1?

Например, берём число 7. Оно нечётное, поэтому умножаем его на 3 и добавляем 1. Получается 22. 22 чётное, поэтому его делим на 2 и получаем 11. Получается такая «цепочка»:

7 → 22 → 11 → 34 → 17 → 52 → 26 → 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4

4 повторилось 2-й раз, следовательно, мы пришли к циклу 1 → 4 → 2, который будет продолжаться бесконечно. Поскольку после каждого нечётного числа мы обязательно перейдём к чётному, мы можем пропустить чётные числа в нашей цепочки, сократив её примерно в 3 раза. (7 → 11 → 17 → 13 → 5 → 1).

В общем, в настоящее время все величайшие математики сходятся во мнении, что вне зависимости от того, какое число мы бы взяли, мы все равно придём к единице.

Данная задача показалась мне скучной, поэтому я решил видоизменить гипотезу Коллатца. Почему, если наше число нечётное, мы должны умножать его именно на 3? Ведь мы бы могли умножать число на любое нечётное.

Например, у нас есть нечётное число. Умножим его на 5, добавим 1, а затем будем его делить на 2, пока оно чётное. Сделаем тоже самое с результатом, и так далее. Придём ли мы в конце к единице?

На этот раз, ответ отрицательный. Например, если мы начнём с числа 13, то получим цикл из 3 чисел {33, 83, 13}, следовательно, мы никогда не придём к числу 1.

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

Для начала, давайте попробуем найти все циклы из 2 чисел для любых значений этого множителя.

Пусть x — это число в цикле, n — это множитель, на который мы умножаем (в стандартной гипотезе Коллатца он равен 3), а a и b — это количество двоек, которые содержатся в промежуточных числах. Тогда мы получаем следующее уравнение:

\frac{xn + 1}{2^a} *n + 1 = 2^b * x

(Мы берём число x, умножаем на n, добавляем 1, делим на несколько двоек, снова умножаем на n, добавляем 1 и получаем х, умноженный на ещё несколько двоек).

Попробуем теперь убрать дроби и преобразить это уравнение в произведение или дробь.

xn^2 + n + 2^a = x2^c, c = a+b

2^a + n = x(2^c - n^2)

x = \frac{2^a + n}{2^c - n^2}

Нам удалось выразить х через гораздо меньшие n, a и c, поэтому теперь задача стала значительно легче.

Стоит обратить внимание, что c > 2a, ведь в любой цикл, который мы ищём, входят 2 числа, которые оба подходят в уравнение с одинаковыми с и n, однако, с разными значениями a — у одного c > 2a, у другого c < 2a. Поскольку нас не интересует находить один и тот же цикл два раза, мы будем искать только меньшее из двух чисел в цикле.

Из этого следует, что для каждого 2^c может подходить не более одного n: 2^a < n (иначе (xn + 1) / 2^a будет меньше, чем x, а ведь наше число х — меньшее в цикле), следовательно, 2^a + n < 2n, следовательно, 2^c — n^2 также меньше чем 2n. Мы все знаем, что разница между соседними квадратами составляет 2n + 1, следовательно, (n+1)^2 больше, чем 2^c.

Последнее замечание: с — нечётное число, потому что иначе 2^с было бы полным квадратом, и, следовательно, 2^c — n^2 было бы равно 2n + 1, что уже больше 2n, и, следовательно, больше, чем числитель.

Учитывая все эти данные, а также, то, что n нечётное число, мы можем написать программу, которая будет перебирать всевозможные переменные: 

import math

for c in range(1, 10000, 2):
    n = math.isqrt(2**c)
    if (n%2==0): continue
    p = 2**c - n**2
    i = 2
    while (i < n):
       if ((n+i) % p == 0): print((n+i)/p, n)
       i = i * 2

Программа нашла всего лишь 3 цикла: это {1, 3} (n = 5), {27, 611} (n = 181) и {35, 99} (n = 181). Пока что неизвестно, что такого особенного в этих двух простых числах, однако, вероятно, дело в том, что их квадраты находятся очень близко к степеням двойки: 181^2 = 2^15 — 7, а 5^2 = 2^5 — 7.

C вероятностью, близкой к 100%, мы можем предполагать, что это все существующие циклы из 2 чисел.


Я собираюсь также написать и опубликовать вторую часть про циклы, длиною больше, чем 2.

Пока что гипотеза xn + 1, или расширенная гипотеза Коллатца звучит так: 5 и 181 — это единственные возможные множители, при которых существуют циклы, отличные от {1}.

© Habrahabr.ru