当平方和为N时，如何找到四个变量的所有可能值? [英] How to find all possible values of four variables when squared sum to N?

问题描述

A^2+B^2+C^2+D^2 = N给定整数N，请打印出所有可能的整数值ABCD组合，以解决该方程.

A^2+B^2+C^2+D^2 = N Given an integer N, print out all possible combinations of integer values of ABCD which solve the equation.

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

I am guessing we can do better than brute force.

推荐答案

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

The Wikipedia page has some interesting background information, but Lagrange's four-square theorem (or, more correctly, Bachet's Theorem - Lagrange only proved it) doesn't really go into detail on how to find said squares.

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

As I said in my comment, the solution is going to be nontrivial. This paper discusses the solvability of four-square sums. The paper alleges that:

没有便捷的算法(除了 本文的第二段)以查找其他解决方案 由制图表达所表明的，但也许 通过提供哪种类型的提示可以简化搜索过程 解决方案不存在.

There is no convenient algorithm (beyond the simple one mentioned in the second paragraph of this paper) for finding additional solutions that are indicated by the calculation of representations, but perhaps this will streamline the search by giving an idea of what kinds of solutions do and do not exist.

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

There are a few other interesting facts related to this topic. There exist other theorems that state that every integer can be written as a sum of four particular multiples of squares. For example, every integer can be written as N = a^2 + 2b^2 + 4c^2 + 14d^2. There are 54 cases like this that are true for all integers, and Ramanujan provided the complete list in the year 1917.

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

For more information, see Modular Forms. This is not easy to understand unless you have some background in number theory. If you could generalize Ramanujan's 54 forms, you may have an easier time with this. With that said, in the first paper I cite, there is a small snippet which discusses an algorithm that may find every solution (even though I find it a bit hard to follow):

例如，据报道，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以下的下一个最大正方形，依此类推.随着时间的推移， 闪电计算器将变得熟悉表达小 数字作为平方和，这将加快处理过程.

For example, it was reported in 1911 that the calculator Gottfried Ruckle was asked to reduce N = 15663 as a sum of four squares. He produced a solution of 125^2 + 6^2 + 1^2 + 1^2 in 8 seconds, followed immediately by 125^2 + 5^2 + 3^2 + 2^2. A more difficult problem (reflected by a first term that is farther from the original number, with correspondingly larger later terms) took 56 seconds: 11399 = 105^2 + 15^2 + 8^2 + 5^2. In general, the strategy is to begin by setting the first term to be the largest square below N and try to represent the smaller remainder as a sum of three squares. Then the first term is set to the next largest square below N, and so forth. Over time a lightning calculator would become familiar with expressing small numbers as sums of squares, which would speed up the process.

(强调我的.)

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

The algorithm is described as being recursive, but it could easily be implemented iteratively.

这篇关于当平方和为N时，如何找到四个变量的所有可能值?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！