一尘不染

当平方和为N时,如何找到四个变量的所有可能值?

algorithm

A^2+B^2+C^2+D^2 = N给定一个整数N,打印出所有可能的ABCD求解方程的整数值组合。

我猜想我们可以做得比蛮力强。


阅读 269

收藏
2020-07-28

共1个答案

一尘不染

Wikipedia页面上有一些有趣的背景信息,但是Lagrange的四平方定理(或更准确地说,Bachet定理-
Lagrange仅证明了这一点)并未真正详细地介绍如何找到所述平方。

正如我在评论中所说,解决方案将是不平凡的。本文讨论了四平方和的可解性。该文件称:

没有便捷的算法(除了本文第二段中提到的简单算法),无法找到表示形式计算所指示的其他解决方案,但是也许可以通过给出一种解决方案的思路来简化搜索过程,并且不存在。

还有一些与此主题相关的有趣事实。还有其他定理指出,每个整数都可以写成四个特定平方倍的和。例如,每个整数可以写为N = a ^ 2 + 2b ^ 2 +
4c ^ 2 + 14d ^ 2。对于所有整数,有54种这样的情况都是正确的,并且Ramanujan在1917年提供了完整列表。

有关更多信息,请参见模块化表单。除非您具有数论方面的背景知识,否则这很难理解。如果您可以概括Ramanujan的54个表格,则可能会更轻松。话虽如此,在我引用的第一篇论文中,有一个小片段讨论了可以找到所有解决方案的算法(即使我觉得很难遵循):

例如,在1911年有报道说,要求计算器Gottfried Ruckle将N = 15663减少为四个平方的和。他在8秒内产生了125 ^ 2 + 6 ^
2 + 1 ^ 2 + 1 ^ 2的溶液,随后立即得到125 ^ 2 + 5 ^ 2 + 3 ^ 2 + 2 ^
2。一个更困难的问题(反映为一个远离原始数的第一项,后面的项相应更大)花费了56秒:11399 = 105 ^ 2 + 15 ^ 2 + 8 ^ 2 +
5 ^ 2。 通常,策略是将第一个项设置为N以下的最大平方,并尝试将较小的余数表示为三个平方之和。
然后将第一项设置为N之下的下一个最大平方,依此类推。
随着时间的流逝,闪电计算器将逐渐熟悉将小数表示为平方和,从而加快了处理过程。

(强调我的。)

该算法被描述为递归的,但是可以很容易地迭代实现。

2020-07-28