algorithm - 如何检查数列是否不收敛？

Question

这是一个求职面试问题:

给定一个正整数 n，您可以使用此函数生成一个数字序列:

f(n) = n/2 if n is even
f(n) = 3*n+1 if n is odd

所以对于 n=3，序列是:

3 10 5 16 8 4 2 1

如果你尝试几个正数，序列总是收敛到 1。

现在编写一个程序来检查 2-N(一个非常大的整数)之间的每个数字是否都会收敛到 1。

我的猜测是:如果序列不收敛，很可能进入这样一个循环:

...,k,3k+1,...,k,...

很容易检查之前是否生成过数字。我的面试官问:如果序列永远不会收敛并且永远不会进入循环怎么办？你如何检查？

如果我没有检测到这种情况，就会导致堆栈溢出，因为我正在使用递归函数来解决这个问题。

如果它永远不会进入循环，我怎么能确定它最终不会收敛？假设奇/偶/奇/偶迭代几次后，数字不断变大，但如果某个 3*N+1 恰好是 2 的幂，它直接收敛到 1 呢？

有什么想法吗？

Answer 1

这个序列是众所周知的 3n+1 序列，其中有 Collatz conjecture .这仍然是一个悬而未决的问题，因为这个问题非常难。

What if the sequence never converges and never enters a loop? How do you check for that?

此序列的行为未知。检查这一点的唯一方法是证明它。可悲的是，仍然没有证据。所以你只能希望它会收敛到 1(仍然没有找到 couterexample)。

所以你的程序应该是这样的:你开始迭代序列并将所有找到的值保存在一个集合中。如果你两次找到相同的值，你就会停下来说有一个反例。如果对于所有值你的程序停止并且你到达 1 你已经证明了 2-N 范围内的所有值都收敛到 1。如果你的程序没有停止，你就不能说什么。

Any counterexample to the Collatz conjecture would have to consist either of an infinite divergent trajectory or a cycle different from the trivial (4; 2; 1) cycle.