AT_abc116_b [ABC116B] Collatz Problem

题目描述

数列 $a=\{a_1,a_2,a_3,\ldots\}$ 按如下方式定义：

• 首项 $s$ 由输入给出。
• 定义函数 $f(n)$：若 $n$ 为偶数，则 $f(n)=n/2$；若 $n$ 为奇数，则 $f(n)=3n+1$。
• 当 $i=1$ 时，$a_i=s$；当 $i>1$ 时，$a_i=f(a_{i-1})$。

请你求出满足下述条件的最小整数 $m$：

• 存在整数 $n$，使得 $m>n$ 且 $a_m=a_n$。

输入格式

输入为一行，包含一个整数 $s$。

输出格式

输出满足条件的最小整数 $m$。

样例 1

输入

8

输出

5

样例 2

输入

7

输出

18

样例 3

输入

54

输出

114

说明/提示

限制

• $1\leq s\leq 100$
• 输入保证为整数。
• $a$ 的所有元素以及满足条件的最小 $m$ 均不超过 $1000000$。

样例解释 1

$a=\{8,4,2,1,4,2,1,4,2,1,\ldots\}$。由于 $a_5=a_2$，所以答案为 $5$。

样例解释 2

$a=\{7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,\ldots\}$。

由 ChatGPT 4.1 翻译