Расширенная гипотеза Коллатца, или проблема "nx+1"

Вероятно, все уже слышали про гипотезу "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 — это количество двоек, которые содержатся в промежуточных числах. Тогда мы получаем следующее уравнение:

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

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

Нам удалось выразить х через гораздо меньшие 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}.