На данный момент есть недоказанная гипотеза Коллатца, которая формулируется очень просто: "Берем любое натуральное число, если оно четное, то делим на 2, если нет, то умножаем на 3 и прибавляем 1. Далее опять смотрим на четность, если нечетное умножаем, прибавляем и т.д. В итоге все должно свестись к единице". Пока не нашли числа, которое не сводится к 1 таким образом. Вероятно, эта гипотеза работает для любых натуральных чисел, но доказать ее еще так и не смогли.
Хочу поделится своим наблюдением, вдохновленным этой гипотезой.
Пусть операция "умножить на 3 и прибавить 1" будет операцией "А", операция "поделить на 2" - операцией "Б".
Любое нечетное число после операции А станет четным и нужно будет выполнить Б. Но что если проигнорировать это правило и посмотреть на то, какие числа после нескольких операций А сводятся к степени двойки.
В такой системе нужно выполнять ТОЛЬКО А, пока не получим степень двойки, а потом выполнять Б, что сведет все к единице
Посмотрим, что происходит с числом v после выполнения нескольких операций A:
3...(3(3(3(v) + 1) + 1) + 1)...
1 операция: 3v+1
2 операции: 3(3v+1)+1 = 9v+3+1 = 3²v + 3¹ +1
3 операции: 3(3(3v+1)+1)+1 = 3³v + 3² + 3¹ + 1
a операций: (3^a)v + 3^(a-1) + ... + 3² + 3¹ + 1 -- вот в это превратится наше число v после a операций А
Теперь нам нужно выполнить Б k раз, т.е. поделить его на 2 k раз, т.е. поделить на 2^k, и оно сведется к единице.
Имеем 1= ((3^a)v + 3^(a-1) + ... + 3² + 3¹ + 1)/(2^k). Заметим, что в числителе есть геометрическая прогрессия 3^(a-1) + ... + 3² + 3¹ + 3⁰ со знаменателем 3, начальным членом 1 = 3⁰, количеством элементов равным а (от 0 до а-1). Тогда эта сумма равна (1-3^a)/(1-3) = ((3^а) - 1)/2.
Тогда 1= ((3^a)v + 3^(a-1) + ... + 3² + 3¹ + 1)/(2^k)
1= ((3^a)v + ((3^а) - 1)/2)/(2^k)
2^k = (3^a)v + ((3^а) - 1)/2
2^(k+1) = 2(3^a)v + (3^а) - 1
2^(k+1) = (3^а)(2v +1) - 1
Теперь выразим v:
2^(k+1) = (3^а)(2v +1) - 1
1 + 2^(k+1) = (3^а)(2v +1)
(1 + 2^(k+1))/(3^a) = 2v + 1
(1 + 2^(k+1))/(3^a) -1 = 2v
((1 + 2^(k+1))/(3^a) - 1)/2 = v
((1 + 2^(k+1) - (3^a)) /(3^a))/2 = v
(1 + 2^(k+1) - (3^a)) /2(3^a) = v
v = 1/2(3^a) + (2^k)/(3^a) - 1/2
Я шел равносильными переходами, тогда
v = 1/2(3^a) + (2^k)/(3^a) - 1/2 <=> 1= ((3^a)v + 3^(a-1) + ... + 3² + 3¹ + 1)/(2^k)
Если число v представимо в виде v = 1/2(3^a) + (2^k)/(3^a) - 1/2, где а и k некоторые натуральные числа, то такое число сводится к единице, если выполнить а операций А и k операций Б.
Но как проще узнать, представимо ли в такой форме число?
Преобразуем наше выражение с v:
v = 1/2(3^a) + (2^k)/(3^a) - 1/2
v = (1+ (2^(k+1)))/2(3^a) - 1/2
v =1/2( (1+ (2^(k+1)))/(3^a) - 1)
v -- натуральное, если (1+ (2^(k+1)))/(3^a) - 1 -- четное число, тогда
(1+ (2^(k+1)))/(3^a) -- нечетное число. Но если это натуральное число, то оно всегда нечетно (т.к. 2 в степени k+1 -- четное, прибавим 1, получим нечетное, поделим на 3 несколько (а) раз, получим нечетное)! А значит, нам достаточно того, что число (2^(k+1)) + 1 кратно степени числа 3 (вариант, когда (2^(k+1)) + 1 = 3^a смысла не имеет, т.к. тогда v=0, т.е. не натуральное). Тогда v =1/2( (1+ (2^(k+1)))/(3^a) - 1) сведется к единице после а операций А и k операций Б. Если 2^(k+1) + 1 кратно 3³, то мы можем поделить его как на 3, так и на 3² и получить целое число (два варианта для а на одно k), т.е. мы нашли уже два сводимых таким образом числа v.
Например, k=2, тогда 2^(k+1) + 1 = 9 = 3², т.е. а=1 (в а=2 нет смысла). Тогда
v=1. Действительно, 1 -(A)> 3+1=4 -(Б)> 2 -(Б)> 1
Заметим, что даже получив желаемую степень двойки в процессе "3х + 1" мы можем продолжить делать эту операцию и дальше, и если в итоге сведем опять к степени двойки, то мы найдем два способа представить одно и тоже натуральное число v в указанном выше виде.
Итог: если 2^(k+1) + 1 кратно 3^а и 3^а ≠ 2^(k+1) + 1, то число
I. сводится к единице сначала за а операций домножения на 3 и прибавления 1, и потом k операций деления на 2.
II. сводится к числу 2^k за а операций умножения на 3 и прибавления 1.
I и II - один и тот же вывод, но по-разному сформулированный.
Рассуждения проделаны самостоятельно, но я не исключаю, что это уже было известно определенному кругу людей.