Гипотеза Коллатца: свободные верхние / нижние границы? [закрыто]
Это проблема из моего учебника.Гипотеза Коллатца (или проблема «3n + 1») работает следующим образом (учитывая некоторое натуральное числоn):
while n > 1 do
if n is even then
n = n / 2
else
n = 3n + 1
end if
end while
Я просмотрел несколько статей по этой гипотезе, но все они оказались у меня над головой. Я пытаюсь получить общее представление о сложности алгоритма. Можно ли прокомментировать верхнюю или нижнюю границу для количества выполненных операций (в худшем случае)?
Единственное, что мне удалось вывести, это то, что входные данные в лучшем случае должны иметь вид n = 2 ^ k (что приведет к наименьшему числу операций). Исходя из этого, справедливо ли сказать, что наихудший случай - это не степень двойки?
Я пытался осмыслить грубую верхнюю или нижнюю границу. Для любогоnкажется, что слишком много переходов от нечетного к четному (что приводит к увеличению в 3 раза или к уменьшению в 2 раза), чтобы прокомментировать наименьшее / наибольшее количество выполненных вычислений.
Любая помощь приветствуется.