В предыдущей части мы с вами расширили всем известную гипотезу Коллатца.

Так, расширенная гипотеза Коллатца утверждает, что множество чисел , для которых есть циклы, отличные от {1}, равно {5, 181}.
Объясню, если мы

Возьмём любое нечётное число ;
Умножим на другое нечётное число и добавим 1;
Будем делить результат на 2, пока оно делится;
Повторим шаг 2,

и в какой-то момент этого алгоритма придём к стартовому числу , то это называется циклом. Так вот, множество чисел , для которых существует хотя бы один цикл, содержащий в себе хотя бы одно число, большее чем 1, конечно и равно {5, 181}.
В предыдущей статье мы рассмотрели формулу для нахождения таких циклов длины 2, и нашли все циклы для $x < 2^{50000}$ . В этой статье, мы расширим эту формулу для любой длины, а также напишем программу, которая находит все циклы без исключений.

Составляем формулу

Давайте немного изменим наш алгоритм, про который мы говорили выше. Мы уберём оттуда деление на 2, зато после умножения на мы будем добавлять не 1, а максимальную степень двойки, на которую делится . То есть, последовательность {15, 19, 3, 1, 3, ...}(x = 5) превратится в {15, 76=19*4, 384=3*128, 2048=1*2048, 12288=3*4096, ...}. Теперь, чтобы число было частью цикла, необходимо лишь соблюдения условия , где - это число , с которого мы начали. Зная, что $a_{j+1} = a_j * x + 2^{b_j}$ , получим

$(((a_0 * x + 2^{b_1})*x + 2^{b_2})*...) * x + 2^{b_{k-1}} = a_0 * 2^{b_k}$

Перенеся все на одну сторону, получим конечную формулу:

$a_0 = \frac{x^{k-1} + x^{k-2} * 2^{b_1}+...+2^{b_{k-1}}}{2^{b_k} - x^k}$

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

Утверждение: для каждого $2^{b_k}$ и может подходить не более одного .

Доказательство: давайте установим наибольшее значение $2^{b_i}$ . Так, $2^{b_1}$ не может быть больше, чем . Ведь иначе $a_1 = \frac{a_0 * x + 1}{2^{b_1}}$ будет меньше первоначального числа, и оно, следовательно, не будет наименьшим! Аналогично покажем, что $2^{b_i} \leq (x+1)^i. Действительно, 1 \leq a_i$ при любых , следовательно, $a_i * x + 1 \leq a_i * x + a_i = a_i*(x+1) \leq a_{i-1}*(x+1)*(x+1) ... \leq a_0*{(x+1)^i}$ . Следовательно, $2^{b_i} \leq \frac{a_0*{(x+1)^i}}{a_0} \leq (x+1)^i$ .

Ну и последний шаг. Как следствие, $2^{b_k} \leq (x+1)^k$ , следовательно, наше первоначальное утверждение доказано.

"Бонус" : в тех случаях, когда и $2^{b_k} = (x+1)^k$ , для всех будет выполняться , следовательно, мы всегда получим один и тот же цикл {1} при разных . Так что, этот случай проверять нам не нужно.

Программа

Нам осталось только написать программу, которая будет выполнять за нас всю оставшеюся работу. Вот код:

#include <iostream>
#include <cmath>

int check(unsigned long long n, int i, unsigned long long s, unsigned long long z) {
    if (s % z) return 0;
    std::cout<<"x = "<<s/z<<", n = "<<n<<", i = "<<i<<std::endl;
    return 0;
}

int recur(unsigned long long n, unsigned long long c, unsigned long long z, int i, int k, unsigned long long p, unsigned long long s) {
    if ((p < c) && (k == i)) check(n, i, s, z);
    if (k > i) return 0;
    if (p >= c) return 0;
    unsigned long long sn = pow(n, (i-k-1));
    unsigned long long p2 = p*2;
    while (p2 <= pow(n+1, k)) {
          recur(n, c, z, i, k+1, p2, s + sn*p2);
          p2 *= 2;
    }
    return 0;
}

int func(int c, int i) {
    unsigned long long n = floor(pow(2, c/(i+0.)));
    if (n % 2 == 0) return 0;

    unsigned long long z = pow(2, c) - pow(n, i);
    if (z == 0) return 0;

    recur(n, pow(2, c), z, i, 1, 1, pow(n, i-1));
    return 0;
}

int main() {
    int c = 3;
    while (1) {
	for (int i = 2; i < c; i++) {
            if (pow(5, i) > pow(2, c)) break;
            if (c % i == 0) continue;
            func(c, i);
//    	    std::cout<<c<<" "<<i<<std::endl;
	};
	c += 1;
    };
    return 0;
}

Как вы, возможно, заметили, программа не будет перебирать и . Дело в том, что при числе 1 никаких циклов, кроме {1} не существует (предлагаю это доказать читателям), а трогать число 3 не надо: учёные проверили все до 9 789 690 303 392 599 179 037 (мы же все помним нашу главную формулу? Там представляется в виде дроби, значение которой при никогда не становится больше этого огромного числа).

Моя программа полностью перебрала все значения , меньшие 45. Вот таблица циклов, которые она обнаружила:

длина	x = 5	x = 181
2	{1, 3}	{27, 611}{35, 99}
3	{13, 33, 83}{17, 43, 27}	-

Кроме этих 5 циклов, программа больше ничего не нашла. Существуют ли другие циклы? - вот вопрос, который остаётся открытым.

А в следующей части мы поговорим про частный случай рассматриваемой проблемы - когда .

Экскурсия в натуральные числа или Расширенная Гипотеза Коллатца, часть II