最顶尖的数学家，也没能给出证明？

这是一个非常诡异的数学猜想，因为它的表述异常简单并且非常容易理解，而且问题的形式看起来那么富有吸引力。

但是即使是最顶尖的数学家，也没能给出一个证明！！

不要试图自己解决这个问题！

虽然我已经发出了警告，但你一定还是会被这个问题所蛊惑，因为它的表述是那么简单，那么容易理解，而且问题的形式看起来那么富有吸引力。

任意选择一个整数，如果它是偶数，就将它除以二；如果它是奇数，就把它乘以三再加一。对于新产生的数，我们对它进行上一步的操作，依次类推。

如果你这样一直做下去，你一定会陷入一个循环中。至少我们猜想会是这样。

接下来以10为例来说明这个问题：

10是偶数，所以我们将它除以2然后得到5；又因为5是奇数，所以用3乘以5再加1得到16；16是偶数，16除以2得8，接下来可以得到4，然后是2，再接下来是1。因为1是奇数，3乘以1加1是4，最后进入了4-2-1-4-2-1......的循环中。

如果以11为例，我们可以得到以下过程：11-34-17-52-26-13-40-20-10-5-16-8-4-2-1-4-2-1....最终我们还是掉入了相同的循环中。

这个“臭名昭著”的考拉兹猜想讲的是，如果从一个正整数开始，你最终一定会陷入循环中。也许你会不顾我的警告而尝试去解决它：因为它看起来很简单也很容易理解。事实上，多数数学家都曾在这个问题上花过功夫。

我第一次在学校学习到这个猜想时就被它吸引了。我和我的朋友花了很长时间来思考这个问题，但是这并没有让我们得到答案。

考拉兹猜想之所以臭名昭著的原因是：即使你可以证明你见过的所有数字都满足这个猜想，那你也不能证明它一定是对的。所以，它至今只是个猜想。

看似简单 ·实则极难

为了理解考拉兹猜想，我们从下面这个函数开始：

你也许还记得学校里教的“分段函数”：上面的函数里包含一个作为自变量的正整数n，并且有两种对它进行操作的规则，我们需要根据n的奇偶性来选择两个规则中的一个。

函数f代表我们对n进行操作的规则，例如：f(10)=10/2=5，f(5)=3*5+1=16。根据函数f对输入的奇数的操作，考拉兹猜想也被成为3n+1猜想。

考拉兹猜想处理的是函数f的“轨迹”问题。轨迹指的是如果你从一个正整数开始计算函数值，并将上算出的值重新代入到函数中得到新的函数值。我们称这种操作为函数的“迭代”。我们已经计算过了输入为10时函数f的轨迹：

f (10) = 10/2 = 5

f (5) = 3 × 5 + 1 = 16

f (16) = 16/2 = 8

f (8) = 8/2 = 4

更方便的表达函数轨迹的方法如下：

10 5 16 8 4 2 1 4 2 1 …

在轨迹的尾部我们可以看到1 4 2 1 的循环。

类似地，对于11有：

11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 4  ….

我们同样陷入了相同的循环中。在尝试其他的例子后，我们会发现轨道最终总是会陷入到循环4 2 1 …中去。

考拉兹猜想声称，任意正整数的轨迹最终都会经过1。尽管没有人能证明这个猜想，但是已经有人证明了，任何小于2^68的正整数都符合考拉兹猜想。所以，如果你想找一个反例的话，你要到大于300000000000000000000的整数里去找。

很容易证明某个数是否符合考拉兹猜想：只要计算相应的轨迹直到得到数字1。但是如果想要知道这个猜想为什么这么难证明，让我们先研究一个稍微简单一点的函数，g(n)。

函数g和f类似，但是对于奇数，函数g只是让数字加1。由于函数f和g不同，数字在函数g中的轨迹和在f中的不同。例如，g中10和11的轨迹分别是：

10 5 6 3 4 2 1 2 1 2 …

11 12 6 3 4 2 1 2 1 2 …

可以看到，g中11的轨迹更快到达1。同样的，27的轨迹在g中也更快的到达1.

27 28 14 7 8 4 2 1 2  …

在这些例子中，g中的轨迹也会陷入循环中，但是它比f中的循环更加简单：

2 1 2 1  ….

我们可以猜想，g中的轨迹最终也会到达1。我可以把它称作“诺拉兹”猜想，但是我还是想叫它n+1猜想。我们会通过检验更多的数的轨迹来研究它，即便是证明了很多数都满足这个猜想，我们也不能认定所有的数都满足这个猜想。幸运的是，诺拉兹猜想可以被证明，方法如下：

首先，我们知道一个正整数的一半总是小于这个数字自身。因此如果n是正偶数， g(n) = n/2 < n。也就是说，当轨迹遇到一个偶数，那么轨迹上的下一个数一定会变小。

如果n是奇数，g(n) = n + 1，得到的数字会变大。但是由于n是奇数，n+1一定是偶数，下一个数是(n+1)/2，所以一个奇数的轨道如下：

…  n  n + 1  (n+1)/2  …

可以看出(n+1)/2 = n/2 + 1/2。因为n/2 < n并且1/2也很小，所以 n/2 + 1/2应该小于n。事实上，简单的数论知识可以证明，当n>1，总有n/2 + 1/2< n。

这些性质告诉我们，当g中的轨道到达了一个大于1的奇数，我们总是可以在两步之后获得一个更小的数。

现在我们可以给出证明诺拉兹猜想的思路了：在轨迹中的某一个点，无论它是偶数还是奇数，那么之后的点总是会逐渐变小，最终，轨迹会到达1。然后它就陷入了循环中，就像我们猜想的那样。

问题在哪？

可以用类似的方法证明考拉兹猜想吗？让我们回到最初的函数形式。

就像函数g那样，函数f会让一个偶数变小，也会让一个奇数变成偶数，接下来再让新的得到的偶数减半。而一个奇数的轨道如下：

…  n  3n + 1  (3n+1)/2  …

而这里正是我们的策略会失败的地方。和前面的例子不同的是，(3n+1)/2 >n。证明诺拉兹猜想的关键是奇数在被函数g作用两次之后会变小，但是这在考拉兹猜想中是不适用的。所以我们的策略失败了。

那考拉兹猜想是不是错的呢？毕竟轨道上的数似乎一直在变大，那它怎么可能慢慢变成1呢？这就要考察接下来会发生什么了，接下来发生的事情会解释考拉兹猜想为什么这么难证明：因为我们不能确定(3n+1)/2 是奇数还是偶数。

我们知道3n+1是偶数。如果3n+1可以被4整除，那么(3n+1)/2是偶数，轨迹上的数会变小。如果3n+1不能被4整除，那么(3n+1)/2是奇数，接下来轨迹上的数会变大。我们不能预测接下来的情况是什么，所以证明诺拉兹猜想的方法在这里失效了。

但是，这种方法并不是毫无用处。因为有一半的整数是偶数，所以 (3n+1)/2有一半的可能性是偶数，这样下一个数就是(3n+1)/4。

对于n>1，(3n+1/)4所以从平均的意义上讲，所有轨迹都必须减少。虽然这在概率论中说得通，但没有人能够完整证明考拉兹猜想。

还是有一点进展...

然而，几位数学家已经证明考拉兹猜想“几乎总是”正确的。这意味着他们已经证明，相对于他们知道的满足考拉兹猜想的正整数，还没有被证明的数字的个数可以忽略不计。1976年，爱沙尼亚裔美国数学家Riho Terras证明，在反复应用考拉兹函数之后，几乎所有的数字最终都会低于最初的值。正如我们在上面看到的，表明轨迹上的数字会不断变小是证明它们最终会达到1的一条途径。

2019年，著名数学家陶哲轩改进了这一结果。当Terras证明了几乎所有的数n的考拉兹轨道最终都会变小后，陶哲轩证明了对于几乎所有的数，n的考拉兹轨迹最终小得多：低于n/2，低于√n，低于lnn。但是陶哲轩说，这个结果是“在没有真正解决它的情况下，最接近完全证明它的工作。”

尽管如此，这个猜想会继续吸引大量的数学家和爱好者的注意。所以你可以选择一个数字尝试一下。记住，有人警告过你：不要陷入无休止的循环中。

下面给大家几个小练习

向上滑动查看答案

1. 证明有无穷多个数可以让考拉兹轨迹经过1

举个例子，我们很容易注意到：

24 23 22 2 1 …

既然2的幂可以写出无穷多个，那么很显然有无穷多个数的考拉兹轨迹经过1。

向上滑动查看答案

2.让n的考拉兹轨迹到达1的最小的操作次数被称为“停止时间”。例如，10的停止时间是6，11的停止时间是14。找出两个停止时间是5的数。

很容易注意到， 25的停止时间是5，因为 25242322 2 1 ….

而 24的停止时间是4，那么从24开始往外数一步的数的停止时间都是5，比如5 16 8 4 2 1

大家可以想想还有其他思路么？

向上滑动查看答案

3.在最近的报告中，陶哲轩提到一个和考拉兹函数相似的函数：

他提出，除了循环 1 2 1 2 1…，还存在其他两种循环，你可以找到它们吗？

另外的两个循环是：

5 14 7 20 10 5 …

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

你是如何找到的呢？