科拉茨猜想：我们仍然无法解决的简单数学问题

你会受到诱惑的。这个问题简单明了，容易理解，而且太吸引人了。只需选择一个数字，任何数字：如果数字是偶数，则将其减半；如果是奇数，则将其三倍并加1。取那个新数字，反复重复这一过程。如果你一直这样做，你最终会陷入循环。至少，这是我们认为会发生的事情。

以10为例：10是偶数，所以我们把它切成两半得到5。因为5是奇数，所以我们把它三倍加1。现在我们有16，这是偶数，所以我们把它减半得到8，然后再减半得到4，然后再减半得到2，再减半得到1。因为1是奇数，所以我们把它三倍加1。现在我们回到4，我们知道这是在哪里：4变成2，再变成1，再变成4，依此类推。我们被困在一个圈子里了。

或者尝试11：这很奇怪，所以我们三倍加1。现在我们有34，这是偶数，所以我们减半得到17，三倍再加1得到52，减半得到26，再加一得到13，三倍再加1得到40，减半得到20，然后是10，然后是5，三倍再加1得到16，再减半得到8，然后是4，2和1。我们又陷入了这个循环。

臭名昭著的Collatz猜想说，如果你从任何正整数开始，你总是会在这个循环中结束。你可能会忽视我关于试图解决它的警告：它看起来太简单太有序了，无法抗拒理解。事实上，很难找到一个没有解决过这个问题的数学家。

当我在学校第一次知道它的时候，我不能忽视它。我和我的朋友们花了几天时间交换激动人心的见解，这些见解似乎从未让我们更接近答案。但是，科拉茨猜想是臭名昭著的，原因是：即使每一个曾经尝试过的数字最终都会出现在那个循环中，我们仍然不能确定它是否总是正确的。尽管备受关注，但这仍然只是一种猜测。

然而，已经取得了进展。世界上在世的最伟大的数学家之一无视所有的警告，并对此进行了尝试，在这个问题上取得了几十年来最大的进步。让我们来看看是什么让这个简单的问题变得如此复杂。

$LaTeX f(N)=\BEGIN{CASES}n/2&；\text{如果$n$是偶数}\\3n+1&；\text{如果$n$是奇数}\end{CASES}\$。

您可能还记得学校里的“分段”函数：上面的函数接受n个输入，然后根据输入是奇数还是偶数，对其应用两个规则中的一个。这个函数f制定了我们上面描述的程序规则：例如，由于10是偶数，所以f_f(10)=10/2=5；由于5是奇数，所以f_f_f(5)=3×5+1=16。由于奇数输入的规则，Collatz猜想也被称为3n+1猜想。

Collatz猜想处理的是这个函数的“轨道”，如果你从一个数字开始，反复应用一个函数，把每一个输出作为新的输入反馈给函数，你就会得到一个轨道。我们称之为“迭代”函数。我们已经开始计算Ff下10的轨道了，所以我们来找下几项：

F(10)=10/2=5 f(5)=3×5+1=16 f(16)=16/2=8 f(8)=8/2=4。

表示轨道的一种方便方法是将其表示为带有箭头的序列。以下是10颗黑洞的轨道：

10→5→16→8→4→2→1→4→2→1→…。

最后，我们看到我们陷入了循环：1→4→2→1→…。那就是。

11→34→17→52→26→13→40→20→10→5→16→8→4→2→1→4→…。那就是。

我们又一次陷入了同样的循环。再试几个例子，你会发现轨道似乎总是稳定在那个4→2→1→…。循环。起始值9和19很有趣，如果您有几分钟的空闲时间，试试27。如果你的算术是正确的，你将在111步后到达那里。

Collatz猜想指出，Ff以下的每个数字的轨道最终都会达到1。虽然没有人证明这个猜想，但对于每个小于2 68的数字，它都得到了验证。因此，如果你在寻找反例，你可以从300百万分之一开始。(您被警告过了！)

很容易验证科拉茨猜想对于任何特定的数字都是正确的：只需计算轨道，直到到达1。但是要了解为什么很难证明每个数字都是正确的，让我们来探索一个稍微简单一点的函数，ℊ。

$LaTeX g(N)=\BEGIN{CASES}n/2&；\text{如果$n$是偶数}\\n+1&；\text{如果$n$是奇数}\end{CASES}\$。

函数ℊ*类似于ff，但对于奇数，它只加1，而不是先将它们增加三倍。由于数字ℊ和数字f是不同的函数，因此数字在数字ℊ下的轨道与在数字ℊ下的轨道不同，例如数字在数字ℊ下的轨道是10和11的轨道是不同的：

10→5→6→3→4→2→1→2→1→2→…。11→12→6→3→4→2→1→2→1→2→…。

请注意，11的轨道在ℊ下达到1的速度比在Ff下快得多，27的轨道在ℊ下达到1的速度也要快得多。

27→28→14→7→8→4→2→1→2→…。

在这些例子中，ℊ下的轨道看起来是稳定的，就像Ff下的轨道一样，但循环稍微简单一些：

我们可以猜想，ℊ下的轨道总会达到1，我称之为“Nollatz”猜想，但我们也可以称之为n+1猜想。我们可以通过测试更多的轨道来探索这一点，但知道一些数字-即使是其中的268%-也是正确的，并不能证明对每个数字都是正确的。幸运的是，诺拉茨猜想实际上是可以证明的。这是怎么做的。

首先，我们知道正整数的一半总是小于整数本身。因此，如果n是偶数且为正，那么ℊ(N)=n/2<；n n。换言之，当一个轨道达到偶数时，下一个数字总是会更小。

现在，如果nn是奇数，那么ℊ(N)=nn+1，它比nn大，但是因为nn是奇数，所以nn+1是偶数，所以我们知道轨道下一步会去哪里：ℊ会把nn+1减半。对于一个奇怪的恒星，轨道将看起来如下所示：

请注意，$LaTeX\frac{n+1}{2}$=$LaTeX\frac{n}{2}$+$LaTeX\frac{1}{2}$。因为$LaTeX\frac{n}{2}$<；n和$LaTeX\frac{1}{2}$是小的，所以$LaTeX\frac{n}{2}$+$LaTeX\frac{1}{2}$可能也小于N。事实上，一些简单的数论可以告诉我们，只要n是1，那么$LaTeX\frac{n}{2}$+$LaTeX\frac{1}{2}$<；n总是正确的。

这告诉我们，当ℊ下的轨道达到大于1的奇数时，我们在两步之后总是处于较小的数字。现在我们可以勾勒出诺拉茨猜想的一个证明：在我们轨道上的任何地方，无论是偶数还是奇数，我们都会呈下降趋势。唯一的例外是当我们在下降的底部打到1的时候。但是一旦我们数到1，我们就会陷入循环，就像我们猜测的那样。

类似的论点能适用于科拉茨猜想吗？让我们回到原来的函数。

$LaTeX f(N)=\BEGIN{CASES}n/2&；\text{如果$n$是偶数}\\3n+1&；\text{如果$n$是奇数}\end{CASES}\$。

与ℊ一样，将ff应用于偶数会使其变小。与ℊ一样，将ff应用于奇数会产生偶数，这意味着我们知道接下来会发生什么：ff将把新数字减半。以下是当nn很奇怪时，ff下的轨道看起来是什么样子：

但这就是我们的论点分崩离析的地方。与上面的例子不同，这个数字大于n：$latex\frac{3n+1}{2}$=$latex\frac{3n}{2}$+$latex\frac{1}{2}$和$latex\frac{3n}{2}$=1.5n，它总是大于n。我们证明Nollatz猜想的关键是奇数必须在两步后变小，但在Collatz的情况下并非如此。我们的论点行不通。

如果你像我和我在学校的朋友一样，你现在可能会对证明科拉茨猜想是错误的感到兴奋：毕竟，如果轨道继续变大，那么它怎么会降到1呢？但这一论点需要思考接下来会发生什么，接下来会发生什么就说明了为什么Collatz猜想如此难以捉摸：我们无法确定$LaTeX\frac{3n+1}{2}$1是偶数还是奇数。

我们知道3n+1是偶数。如果3n+1也能被4整除，那么$LaTeX\frac{3n+1}{2}$1也是偶数，轨道就会下降。但是如果3n+1不能被4整除，那么$LaTeX\frac{3n+1}{2}$1就是奇数，轨道就会上升。一般来说，我们无法预测哪个是真的，所以我们的论点就停滞不前了。

但是这种方法并不是完全无用的。由于所有正整数中有一半是偶数，因此$LaTeX\frac{3n+1}{2}$有50%的可能性是偶数，这使得轨道上的下一步是$LaTeX\frac{3n+1}{4}$。对于n=1，这比n=1小，所以有一半的时间奇数应该会在两步之后变得更低。(注：$LaTeX\frac{3n+1}{2}$是偶数，这使得轨道上的下一步是$LaTeX\frac{3n+1}{4}$。)。$LATEX\FRAC{3n+1}{4}$1也有50%的可能性是偶数，这意味着奇数在三个步骤后有25%的可能性会减少到不到开始时的一半。诸若此类。最终的结果是，在某种平均意义上，当Collatz轨道遇到奇数时，它们会减少。由于Collatz轨道总是以偶数递减，这表明从长远来看，所有Collatz序列都必须递减。这一概率论据广为人知，但还没有人能够将其扩展到对这一猜想的完全证明。

然而，几位数学家已经证明，科拉茨猜想“几乎总是”正确的。这意味着他们已经证明，相对于他们知道的导致1的数字的数量，他们不确定的数量可以忽略不计。1976年，爱沙尼亚裔美国数学家Riho Terras证明，在反复应用Collatz函数后，几乎所有的数字最终都会低于它们开始的位置。正如我们在上面看到的，显示轨道上的数字不断变小是表明它们最终达到1的一条途径。

2019年，世界上最伟大的在世数学家之一陶渊明在这一结果的基础上有所改进。Terras证明了对于几乎所有的数字，n的Collatz序列最终都低于n，陶渊明证明了对于几乎所有的数字，n的Collatz序列最终都要低得多：低于$LaTeX\frac{n}{2}$，低于$LaTeX\sqrt{n}$，低于$LaTeX\ln$(n的自然对数)，甚至低于每个f(N)，其中f(X)f是任何无穷大的函数，无论多么缓慢。也就是说，对于几乎每个数字，我们可以保证它的Collatz序列是我们想要的那样低。在一次关于这个问题的谈话中，陶说这个结果“几乎是一个人在没有实际解决的情况下尽可能接近科拉茨猜想的结果。”

即便如此，这个猜想仍将继续吸引数学家和爱好者。所以选择一个数字，任何一个数字，然后试一试。只要记住，你已经被警告过：不要陷入无休止的循环。

2.数n的“停止时间”是n的Collatz轨道达到1所需的最小步数，例如10的停止时间为6，11的停止时间为14，找出两个停止时间为5的数。

3.在最近一次关于Collatz猜想的演讲中，Terrance陶渊明提到了以下类似Collatz的函数：

$latex h(N)=\BEGIN{CASES}n/2&；\text{如果$n$是偶数}\\3n-1&；\text{如果$n$是奇数}\end{case}\$。

陶指出，除了1→2→1→2→1…。循环，则会出现另外两个循环。你能找到他们吗？

请注意，2的每个幂都有一个到1的简单动态观察路径。例如，

因为有无穷多个2的幂，所以有无限多个数的Collatz轨道经过1。

请注意，%2%5的停止时间为%5，因为%2%5→%2%4→%2%3%→%2%2→%2→%1→…。。因为2 4的停止时间是4，所以任何距离2 4一步的数字都有5的停止时间。例如，5→16→8→4→2→1。还会有其他的数字吗？

17→50→25→74→37→110→55→164→82→41→122→61→182→91→272→136→68→34→17→…。。