全球40万台计算机才解开的数学问题，到底怎么回事？

三立方数和一直是困扰数学家的难题之一，一些数字的求解非常简单，例如 29 可以写成 3^3+1^3+1^3 (27 + 1 + 1)。2019 年，MIT 数学家 Andrew Sutherland 和布里斯托大学教授 Andrew Booker 不仅首次攻克了 100 以内自然数的最后一个关卡——42，还找到了自然数 3 的第 3 组三立方和解。近日，相关研究在《美国国家科学院院刊》（PNAS）上发表。

本文来自微信公众号：机器之心（ID：almosthuman2014），编辑：魔王、杜伟，原文标题：《3的三个整数立方和有多少个解？全球40万台计算机助力，MIT研究登上PNAS》

1992 年，数学家罗杰希思 - 布朗（Roger Heath-Brown）提出猜想，所有自然数都可以被写成 3 个数立方之和。

2019 年，数学家 Andrew Sutherland 和 Andrew Booker 首次将 42 写成 3 个整数的立方和，这意味着 100 以内自然数全部被攻破。

Andrew Sutherland（左）和 Andrew Sutherland（右）。

但是，两人并未停止探索的脚步，而是“挥刀向更强”：找出自然数 3 的下一个解。在发现 42 的立方和解之后数周，他们即解决了这个难题。近期，Sutherland 和 Booker 的相关研究文章发表在了《美国国家科学院院刊》（PNAS）上。

文章链接：https://www.pnas.org/content/118/11/e2022377118

三立方数和问题

1957 年，英国数学家莫德尔（Louis Mordell）提出一个问题：哪些正整数可以写成三个立方数之和？（这三个数可正、可负，也可以等于 0。）这就是著名的“三立方数和问题”。

1992 年，英国牛津大学的罗杰 · 西斯–布朗提出了一个猜想：除了 9n±4 型自然数外，所有自然数都可以用无穷多种不同方式写成三个立方数的和。

20 世纪，三立方数和问题的研究进展（图源：https://math.mit.edu/~drew/Waterloo2019.pdf）

2000 年，美国哈佛大学的诺姆 · 埃尔吉斯提出了一个实用的算法，成功找到了许多较小整数的立方和算式。

2015 年，数学家蒂姆 · 布朗宁发布了一段解释该问题的视频。当时小于 100 的整数几乎都被解决，只剩下 33、42 和 74 这三个数。

2019 年 9 月，数学家 Andrew Sutherland 和 Andrew Booker 破解了 100 以内自然数的最后一个难关——42。

之后短短数周时间，他们又解决了一个更大的难题：找到了自然数 3 的第 3 个三立方数和解。

自然数 3 的又一个三立方数和解

对于 x^3+y^3+z^3 = 3，恐怕连高中生都能给出 x、y、z 的解：

那么，还有没有其他解呢？

这个问题困扰了数学家几十年。1953 年，数学家莫德尔提出问题：对于自然数 3，是否存在其他解？

Sutherland 表示：“这更像是莫德尔发起的一个挑战。解决这个问题的有趣之处并不是求出特定解，而是更好地了解这些公式的求解难度。这是我们用来衡量自己的标准。”

自 1953 年莫德尔抛出这个问题后，60 多年都没人发现答案。直到 2019 年，Andrew Sutherland 和 Andrew Booker 破解了 42 的三立方数和解，并很快找到了 3 的第三个解。

这一发现直接回答了莫德尔的问题。或许更重要的是，这个包含 21 位数字的解直到 2019 年才被发现，说明对于 3 或其他自然数还存在更多解。

“莫德尔的问题太难了，因此数学和计算社区对此曾经存在严重怀疑。”Sutherland 说道，“解包含的数字如此之大。但是找到这个解之后，我相信肯定存在更多其他解。”

如何求解？

为了找出 42 和 3 的解，该团队一开始使用现有的算法，将三立方数和方程转换为他们认为更易于求解的形式：

这一算法最初由英国数学家罗杰希思 - 布朗提出，根据他的猜想，每个适当的 k 应该有无限多个解。该团队通过将 x+y 表示为单个参数 d 进一步修改了这一算法。然后他们将两边都除以 d 并保留余数，进一步简化了问题表示。

牛津大学数学家罗杰希思 - 布朗。

Sutherland 解释道：“你现在可以将 k 视为 z 的立方根，并对 d 进行取模运算。因此，想象一下在算法系统中只关心对 d 取模运算后的余数会怎么样。我们尝试计算 k 的立方根。”

有了这个更简洁的方程，要想找到 k=3 时 x, y 和 z 的最终解，研究人员只需找到 d 和 z 的值即可。但是，他们必须搜索的数字空间无限大。因此，研究人员使用数学“筛分”法大大减少 d 的可能解的空间，进而优化了该算法。

Sutherland 表示：“这涉及一些非常先进的数论。使用我们已知的数域结构，来避免搜寻我们不需要考虑的空间。”

全球 40 多万台计算机助力 42 和 3 的三立方数和解

该团队还开发了一些可以将算法搜索高效地分解为数十万个并行处理流的方法。如果仅在一台计算机上运行该算法，则需要花费数百年的时间才能找到 k=3 的解。而将该求解过程分割为数百万个较小任务后，每个任务可以在单个计算机上独立运行，这样该团队可以进一步加速搜索进程。

2019 年 9 月，研究人员通过 Charity Engine 项目将他们的计划付诸实践，该项目旨在利用闲置的家庭计算机来共同求解数学难题，任何个人计算机都可以免费下载该项目。当时，Charity Engine 网格涵盖全球超 40 万台计算机。作为 Charity Engine 新软件平台的测试，Booker 和 Sutherland 可以在该网格上运行其算法。

Charity Engine 项目。图源：https://thenextweb.com/apps/2011/12/14/charity-engine-donate-spare-pc-power-and-stand-a-chance-to-win-a-1m-invites/

Sutherland 表示：“Charity Engine 网格中每台计算机的任务是寻找素因数在此范围内的 d 值，但受到其他条件的约束。此外我们必须搞清楚如何将求解过程分解为大约 400 万个任务，每台计算机大约花费 3 个小时来完成一个任务。”

很快，全球网格返回了 K=42 的首个解，并在两周后，研究人员证实找到了 k=3 的第 3 个解。他们在 T 恤上打印出了这一里程碑式的解。

K=3 存在第 3 个三立方和解的事实表明，Heath-Brown 最初的猜想是正确的，除了这一最新解之外，还有无穷多个解。罗杰希思 - 布朗还预测，解之间的空间随搜索范围呈指数增长。例如，x, y 和 z 的第 4 个解可能不再是 21 位数，可能是难以置信的 28 位数。

对此，Sutherland 表示：“每个新解所需的工作量会增加 1000 万倍。因此，第 4 个解或许需要 1000 万 ×40 万台计算机才能找到，甚至还不一定够。我不知道能否找到第 4 个解，但我确信它始终就在那里。”

参考链接：

https://news.mit.edu/2021/solution-3-sum-cubes-puzzle-0311

https://math.mit.edu/~drew/Waterloo2019.pdf

https://www.ituring.com.cn/book/tupubarticle/34408

本文来自微信公众号：机器之心（ID：almosthuman2014）