如果宇宙的答案是42，那么问题是什么？ | 姬扬

导言：

难道这就是宇宙的终极问题吗？是还是不是，这是一个问题。

“老实说，我认为问题在于，你从来都不知道问题是什么。”

这是《美国科学院院刊》（PNAS）的一篇数学论文的开场白。这篇文章的作者是两位数学家布克尔（Andrew R. Booker）和萨瑟兰（Andrew V. Sutherland），分别来自于英国的布里斯托大学和美国的麻省理工学院，他们讨论的问题是某个丢番图方程（具有整数解的不定方程）。更准确地说，他们发现了代数不定方程的整数解(x,y,z)，其中最小的数也大于1亿亿，也就是，1后面跟16个0。

其实，开场白的这句话不是这两位数学家说的，而是来自于亚当斯（Douglas Adams）的著名科幻小说《银河系漫游指南》，一台超级计算机经过700万年的思考，得出了关于“生命、宇宙和万事万物终极问题”的答案—— 42。这本小说里并没有具体地描述这个问题，所以，问题来了：如果宇宙的答案是42，那么问题是什么呢？布克尔和萨瑟兰给出了他们的回答。

萨瑟兰（Andrew V. Sutherland，左）和 布克尔（Andrew R. Booker，右）

看到这个方程，很多人都会想到费马大定理（在1637年左右，法国数学家费马在阅读丢番图《算术》的拉丁文译本时提出的一个猜想）：对于任何大于2的整数n，没有任何正整数(x,y,z)能够满足。

显然，n=3只是一种特殊的情况，而且著名数学家欧拉早在1753年就证明了它。至于n是大于2的任何整数的情况，则是在1995年被英国数学家怀尔斯（Andrew Wiles）证明了。

既然没有整数解，自然就会问，对于什么样的整数k，有整数解呢？因为一个整数的立方除以9的余数只能是0、1或者8，很容易证明，如果k除以9的余数是4或者5，这个方程就不可能有整数解。但是对于其他的k，仍然有很多方程不知道有没有整数解。即使在4年以前的2018年，对于小于100的k来说，33和42对应的方程仍然没人知道有没有整数解——直到布克尔开始思考这个问题。

2019年，布克尔发表了一篇文章，解决了这个问题，2021年，布克尔和萨瑟兰合作发表的PNAS文章，解决了这个问题，以及其他一些相关问题。

他们是怎么做的呢？利用中学的数学知识，就可以理解布克尔的解决思路，以及33这个问题所涉及的数学和计算内容。42这个问题需要的数学要更多一些，但主要是为了提高算法的效率。这里主要介绍布克尔的第一篇文章。

再描述一遍问题。为了便于描述，我利用了答案，把问题重新描述如下：

寻找三个正整数x>y>z>0，满足。

这里不考虑(x,y,z)三个变量里有两个相等的情况，因为这样涉及的计算量很少，容易验证不存在这样的解。

对于这个问题，蛮力搜索当然在原则上是可以的，但是太费时间，所以需要用一些数学和计算技巧。因为

令d=x-y和s=x+y，可以得到，

等式右边是个整数，所以，d=x-y必须是的因子，经过一些简单的代数运算，就得到

注意到等式右边是完全平方数，所以，左边也必须是完全平方数。

根据你的计算能力和资源，选择一个z的上限B，比如说，。然后，按照如下流程计算，就可以得到答案了。

1、选择一个整数z（<B），

2、计算，

3、寻找的因子d，

• 找到一个新的因子，继续进行步骤4；

• 找不到因子，或者找不到新的因子，返回步骤1，选择一个新的整数z。

4、计算，

5、检查是不是某个整数s的平方，

• 如果是平方数，就成功了，，；
• 如果结果不是平方数，回到步骤3，寻找的下一个因子。

上述流程的思路很清楚，但是需要的计算量仍然很大，为了减少计算量，布克尔还采用了很多技巧。有些很简单，比如说，(x,y,z)不能是3的倍数，d=x-y有上限，等等；有一些需要初等数论的知识，布克尔教授的文章里给出了一些引理，很有帮助；还有一些技巧相当高级，需要利用一些关于莫德尔曲线（Mordell curve）的结论，可以排除所有d≤40的情况（这部分有些困难，就不介绍了）。

利用这些限制，可以显著减少计算量，但是仍然不太够，主要是因为确定一个数是不是平方数，常规检验（也就是计算一个数的平方根）需要的计算量太大。布克尔采用了一种更有效的方案：用几率的方法判断一个数是不是完全平方数。他设定了一系列检验条件，通不过这些检验条件的，一定不是平方数，通过检验的数很少，对它们进行常规的检验。

这里涉及了“二次剩余定理”。这是初等数论的内容，概念和证明都不难，这里只讲一个非常简化的结论。

  //  

“二次剩余定理”有一个推论：两个整数X和Y的乘积的勒让德符号(XY|p)，等于它们各自的勒让德符号(X|p)和(Y|p)的乘积，(XY|p)=(X|p)(Y|p)。
对于整数a和p，勒让德符号(a|p)描述二次剩余的性质，其定义如下

(a|p)=0，如果

(a|p)=+1，如果，而且存在某个整数x，使得

(a|p)=-1，如果，而且不存在任何整数x，使得

如果(a|p)=+1，就称a为二次剩余(mod p)；如果(a|p)=-1，就称a为非二次剩余(mod p)。

应用这个结论，可以快速地判断某个数XY是不是平方数，因为计算(X|p)和(Y|p)比直接计算(XY|p)更容易。稍微具体的说，是这样的：

1、判断是不是平方数，等价于判断是不是平方数，这个转换只是把除法变成了乘法，判断起来更容易了。

2、选择某个整数（例如）M=5×7×11×13=5005，它是四个最小素数（除了2和3以外）的乘积，不考虑素数2和3是因为前面提到的限制条件已经有效地计算了相关的情况。

3、计算3d和这两个数对整数M取模的余数X和Y，计算勒让德符号(XY|p)=(X|p)(Y|p)，这个结果只可能是0或±1。大约有一半的机会，结果是-1，这样的数肯定不是平方数。对素数p=5,7,11,13进行这种操作，就可以淘汰掉大约百分之九十的选手。

4、对于剩下来的幸运儿，还可以用更多的素数考验它们（需要相应地改变M），每次考验可以淘汰大约一半的选手。

5、经过步骤3和4的筛选，就可以大大减少真正需要计算平方根的情况了。

上面是数学，下面再简单讨论一下计算。

布克尔证明了，应用上述所有技巧以后，寻找42所需的时间正比于搜索量，或者说B的大小，而相比之下，蛮力计算的用时跟成正比。事后来看，因为B是10的16 次方的量级，即使用上现在所有的计算机，蛮力计算需要的时间也很容易就超过了宇宙的年龄。

查表可以加快计算。有些数值需要经常算，把它们的结果存下来，需要的时候直接查表，这也是常用的方法，能够“以空间换时间”——因为需要把许多表格存下来。

并行处理也可以让计算加速。每个符合条件的z值可以单独处理，彼此并不影响，这样就可以把任务分配给不同的计算机（或者同一个“并行计算机”的不同的核），结果就是“人多力量大”——大家不会互相干扰，无论谁找到结果，都是最终的胜利。

编程当然也很重要。布克尔的文章里也有描述，但是我不太懂，所以就不多谈了。

利用上面描述的方法和技巧，如果z跑完了上限以内的所有值，仍然得不到想要的结果，你要么放弃，要么设定一个更大的上限，重复上述流程。实际上，布克尔在这个范围里，只找到了33的结果，

后来，他跟萨瑟兰合作，采用了更精细的算法，在更大的范围搜索，在全球40万台计算机的帮助下，才得到

这些答案检查起来很简单，用笔记本电脑里自带的科学计算器就可以验证，但是，寻找答案所需要的计算量却是非常惊人的。

总之，这个不定方程有整数解吗？答案是肯定的。

难道这就是宇宙的终极问题吗？是还是不是，这是一个问题。

后记

布克尔（Andrew R. Booker）和萨瑟兰（Andrew V. Sutherland），还有那个证明了费马大定理的怀尔斯（Andrew Wiles），他们的名字都是安德鲁。这个名字有什么奥秘吗？我们注意到，安德鲁这个名字有33个笔画，也许这就是他们成功的奥秘吧。

这里我强行规定了这个不定方程整数解为正，并根据答案确定了它们前面的加减号。这样描述起来很方便，但是不严谨——布克尔的文章是非常严谨的。

这里提到的两篇文章是：

[1]Andrew R. Booker, Cracking the problem with 33, arXiv:1903.04284. 正式发表于Res. Number Theory 5, 26 (2019)

[2]Andrew R. Booker and Andrew V. Sutherland, On a question of Mordell, PNAS 118 (11), e2022377118.

我觉得，第一篇文章很容易读，第二篇文章要困难得多，可能是因为必须进一步提高算法效率的原因。这里只讲了第一篇文章。

 点击下载原文附件 

■ 扩展阅读：兴风作浪的翻译人 | 姬扬
《半导体的故事》译者的话 | 姬扬
科普困境之窥一斑而知全豹 | 姬扬
量子信息的显学、玄学和科学 | 姬扬从《科学：无尽的前沿》看科学的功用、规划和实施 | 姬扬
我们需要真正的中文科技文章的预印本文库 | 姬扬
■ 背景简介：本文作者姬扬，中国科学院半导体研究所研究员，科学网博客主页（http://blog.sciencenet.cn/u/jiyang1971）。作者授权风云之声首发。
■ 责任编辑：KK.

关注风云之声 提升思维层次