Collatz Sequence

Problem #48

Tags: arithmetic classical

Who solved this?

Back to English version

Гипотеза Коллатца - одна из наиболее таинственных загадок математики 20 века. Её описание понятно даже школьнику, но даже выдающиеся ученые не знают её доказательства. Зато она может служить отличным упражнением для программистов.

Пусть мы выбрали некое исходное число X и строим от него последовательность значений по следующим правилам:

если X четное (т.е. X mod 2 = 0) тогда
    Xследующее = X / 2
иначе
    Xследующее = 3 * X + 1

Таким образом если X нечетно, последовательность растет - а если четно, то убывает. Например, с X = 15 мы получим:

15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1

После достижения 1 последовательность зацикливается 1 4 2 1 4 2 1....

Интрига заключается в том, что для любого начального X получаемая последовательность, по-видимому, рано или поздно достигает 1 - однако хотя это предположение было высказано как гипотеза Коллатца еще в 1937, до сих пор никто не смог ни доказать её, ни найти контрпример (т.е. число для которого последовательность либо входит в другой цикл, нежели 1 4 2 1 - либо растет бесконечно). Может быть повезет вам?

Ваша задача - для заданного исходного X посчитать сколько шагов требуется чтобы дойти до 1.

Входные данные содержат количество тестов в первой строке.
Вторая строка содержит сами тесты - т.е. исходные значения для которых нужно определить длину получаемых последовательностей.
Ответ должен содержать для каждого исходного значения полученное количество шагов (через пробел).

Например:

входные данные:
3
2 15 97

ответ:
1 17 118
You need to login to get test data and submit solution.