Двоично-троечная система исчисления и задача Коллатца

Смешанные системы исчисления так же используются в программировании и в математике. Например, в войсках дивизии состоят из n1 полков, полки из n2 батальонов, батальоны из n3 рот, роты из n4 взводов, взводы из n5 отделений, в отделении n6 солдат. Тогда зная номера полка, батальона, ... мы определим искомого солдата дивизии. В программировании такое не обязательно равные деления используется для представления элементов тензора (матрицы).

Стараюсь быть понятым и старшеклассниками. Однако, не удержусь, скажу некоторые вещи понятные только имеющим университетское математическое образование. Преобразование Фурье порядка

n=n1*n2*...*nk,

используемое при умножении больших чисел, произведение которых имеет не более n разрядов выполняется экономнее через k кратное преобразование Фурье порядков n1,n2,...,nk. Однако, в этой задаче и в других подобных задачах возможно только в случае, когда n1,n2,...,nk взаимно просты. В этом случае, выполняется соотношение (Китайская теорема об остатках)

Z_n=Z_{n1}+Z_{n_2}+...+Z_{nk}. (1)

Для преобразования Фурье (1) используется как изоморфизм коммутативных групп. В модулярных вычислениях (1) используется как изоморфизм кольца с прямой суммой подколец.

В задаче Коллатца используется представление другого типа смешанное представление. Коллатц 1 июля 1932г. сформулировал гипотезу о том, что рекуррентно определенная последовательность n(i+1)=f(n(i)), где

f(n)=3n+1 if n-odd, f(n)=n/2, if n -even,

сходится к циклу 1-->4-->2-->1, при любом начальном n(0).

Сейчас эта гипотеза проверена для n(0) до 10^(100) (согласно Википедии).

Отметим, что в случае нечетного n, число 3n+1 всегда четное. Поэтому, более правильно определить f(n)=(3n+1)/2=n+(n+1)/2=2n-n/2 if n-odd. Тогда можно сказать, что за один ход с вероятностью 0.5 число увеличится примерно в полтора раза и с вероятностью 0.5 уменьшится в два раза, т.е. за два хода в среднем уменьшится до (3/4) своего значения. Естественно, вероятностные соображения ничего не доказывают, а являются только поводом для выдвижения гипотез о поведении последовательности.

Для исследования лучше определить последовательность только на нечетных натуральных числах больше 1 по рекуррентному соотношению:

f(n)=(3n+1)*2^{-ord_2(3n+1)}, n-odd.

Здесь 2^{-ord_2(3n+1)} деление на ту степень двойки, при котором получается нечетное число. Так мы сократили количество операций в несколько раз. Через l шагов от числа n получится число m:

m=n*3^l*2^{-k1-...-kl}+3^{l-1}2^{-k1-...-kl}+3^{l-2}*2^{-k2-...-kl}+2^{-kl}. (2)

При этом n выражается через m формулой:

n=-3^{-1}-2^{k1}*3^{-2}-2^{k1+k2}*3^{-3}-...-2^{k1+...k(l-1)}*3^{-l}+2^{k1+...+kl}3^{-l}m (3)

Гипотеза Коллатца эквивалентно тому, что при любом n существует представление m=1 формулой (2) или представление n формулой (3) в такой смешанной двоично-троичной системе исчисления.

Отметим, что если m нечетное число, делящееся на 3, то не существует предыдущего числа n , что m=f(n). Если нечетное число m=6a+-1, то таких предыдущих чисел бесконечно много n=(2^lm-1), где l - любое четное натуральное число при m=6a+1 и нечетное при m=6a-1.

Определив минимальное поднятие b, получаем серию других, каждое следующее по формуле 4b+1.

Можно распределить нечетные натуральные числа n больше 1 по этажам l, если через l шагов опускаемся до 1. Для доказательства гипотезы имеются несколько путей. Одно из них заключается в подсчете количества чисел n<N, лежащих на этажах не выше l. Вообще решение задачи проясняется из представления чисел в такой смешанной двоично-троичной системе исчисления.