Жалкое подобие последовательности Колатца :)

[bot]

Эта задачка (впрочем несложная даже для школьников) не должна быть широко известной в узких кругах. Придумал я её лет 10 или более назад и практически никому не показывал.
Преамбула для тех, кто не в курсе.
Есть очень известная проблема под названием 3х+1:
Пусть n - натуральное. Если оно чётное, то положим T(n)=n/2, иначе T(n)=3n+1. Предположение Колатца (Collatz), высказанное им в 1928 г. состоит в том, что стартуя с произвольного n, итерационная последовательность n, T(n), T(T(n)),... завершится циклом (1,4,2).
Рассказывают, что сам Колатц любил демонстрировать эту проблему таким образом:
- Возьмём для иллюстрации не очень большое число, гм, ну, скажем, 27...
Первоначально Колатц предлагал 100 $ из своего кармана за решение. Контрпример оценивал дешевле - баксов в 20.

Аналогично, можно поставить вопрос для 3х-1 или, что то же самое для 3х+1 в отрицательной части Z. Здесь всяк легко найдёт циклы с их образующими 5 и 17. На этом известные достижения заканчиваются.

По простоте формулировки эта проблема может соперничать с проблемой Ферма и уже множится армия дилетантов, бьющихся над её решением.

Итак,
Жалкое подобие последовательности 3х+1:
На множестве натуральных чисел определим отображение t следующим образом: в числе 3n+1 выделяем максимальный делитель, являющийся степенью двойки. Прибавив этот делитель к n, получим t(n). Стартовав с произвольного натурального n можем организовать последовательность: n, t(n), t(t(n)), ...
Пример: 94 95 97 101 117 149 213 341 ...

Описать поведение этой последовательности. Я намеренно даю формулировку в такой форме. Сформулировать, что именно нужно доказывать - это начальный этап задачи.

Аналогично организуется жалкое подобие последовательности 3х-1 с тем же вопросом.

ЗЫ. Возможно я и ошибаюсь в оценке простоты задачки - уже неделю безответно (если не считать зашифрованного ответа от преподавателя) на двух форумах висит, впрочем малолюдных в виду сессии.

[маткиб]

Ну некоторое описание дать можно. Опишем функцию t(n). Будем записывать двоичные записи начиная с младших разрядов к старшим (то есть не как обычно, а наоборот). Пусть k - максимальное число такое, что k младших разрядов числа n образуют последовательность 10101010.... . И пусть n=AB, где A-k младших разрядов n, а B-все остальные. Тогда t(n)=A(B+1). Здесь B+1 - это двоичная запись числа (1+число, двоичная запись которого есть B). То есть начиная с k-ого разряда находится последовательность вида 11...110 (возможно, количество единиц равно нулю) и заменяется на 00...001. Это и будет t(n). Все это доказывается простейшими теоретико-числовыми рассуждениями (даже выписывать неохота). Можно заметить, что значение k от члена к члену строго возрастает и начиная с некоторого номера наступит некоторая стабилизация, то есть каждый следующий член будет отличаться от предыдущего добавленной единицей на месте старшего разряда + 2.

И еще. Пусть последовательность есть t_0,t_1,\ldots,\quad t_{n+1}=t_n+2^{k_n}, тогда k_n монотонно возрастает и множество значений, которые она принимает можно описать с помощью конечного автомата с 4 состояниями, которому на вход подается двоичная запись t_0 начиная с младшего разряда. Если нужно, могу выписать.

[маткиб]

А автомат такой (пока не забыл).
У него 4 состояния: A00, A01, A10, A11.
Переходы при подаче 0:
A00->A10, выдать
A01->A10
A10->A00
A11->A01, выдать
Переходы при подаче 1:
A00->A10
A01->A11, выдать
A10->A01, выдать
A11->A01
Инициальное состояние - A00.
Если при подаче k-ой цифры автомат сказал "выдать", то k принадлежит множеству значений последовательности k_n.
Можно отметить, что этот автомат минимальный.

[bot]

Можно ещё и так сказать, что начиная с некоторого номера (который легко вычисляется) эта жалкая последовательность является хвостом последовательности

1, 11, 111, 1111, ...

Некоторое сходство всё же есть - отсюда и название. Подправим T(n) в определении последовательности Колатца (m - нечётное):

$ T(2^k m)=2^k(3m+1)$

Тогда предположение Колатца состоит в том, что стартующая с любого n итерационная последовательность является хвостом одной из двух последовательностей

1, 10, 100, 1000, 10000, ...
2, 20, 200, 2000, 20000, ...

[незваный гость]

Жалкое подобие последовательности 3 х+1 быстро сходиться к $\frac{2^{2n}-1}{3}$;
жалкое подобие последовательности 3 х-1 быстро сходиться к $\frac{2^{2 n -1}+1}{3}$.
"Быстро" в данном случае означает не медленее чем ${\rm O}(\log_2 x)$.
Вероятно, это тоже самое утверждение, что и bot'а.

[bot]

Ну ещё могу добавить, что можно вычислить точный номер стабилизации - точнее написать реккуррентную формулу. Двоичная запись числа представляется как чередование частоколов из единичек и дырок из нулей. Самый старший забор отщепляем и в зависимости от величины дыры до следующего по старшинству забора и чётности оставшихся символов получим реккуррентную формулу. Вот только проще ли это будет, чем сам алгоритм? Да и формула - это тоже алгоритм.
Так что это не та задача, которой стоит заниматься.