如何检查数字序列是否不收敛？

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猜想.这仍然是一个悬而未决的问题，因为这个问题极其棘手。

如果序列永远不会收敛，也不会进入循环呢？你怎么查这个？

此序列的行为尚不清楚。唯一能证明这一点的方法就是证明。可悲的是，仍然没有证据证明。所以，你可以希望它能收敛到1(还没有找到具体的例子)。

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

Collatz猜想的任何反例都必须包含一个无限发散的轨迹或一个不同于平凡(4；2；1)循环的循环。