100000014 - longest Collatz sequence

n为奇数时,n=3×n+1

n为偶数时,n=n/2

科拉茨猜想认为任何正整数经过以上迭代最终都会变为1。例如:

13->40->20->10->5->16->8->4->2->1

该Collatz序列从13开始,共10个数。求不大于t的数中,哪个数产生的Collatz序列最长。

输入

n

测试点一:n=10^6

测试点二:n=10^7

输出

一个整数,表示不大于n的数中,Collatz序列长度最长的那个数。

如果有多个长度相同的,输出第一个。

样例

输入

13

输出

10

提示

这个题目需要挨个测试,但明显的26有11长:

13->40->20->10->5->16->8->4->2->1

26->13->40->20->10->5->16->8->4->2->1

所以记录中间结果非常重要,并且显然的,这个中间结果被用于所有数的迭代过程,所以不存在清空操作。

除此之外,显而易见的,当n为奇数时可以优化:3×n+1必定为偶数,所以当n为奇数时,一次性前进两步即可。

时间限制 500 毫秒
内存限制 128 MB
统计
上一题 下一题