将给定数字表示为四个平方的总和 [英] Express a given number as a sum of four squares
问题描述
我正在寻找一种将给定数字表示为(最多)四个平方之和的算法.
I am looking for an algorithm that expresses a given number as a sum of (up to) four squares.
120 = 8 2 + 6 2 + 4 2 + 2 2
6 = 0 2 + 1 2 + 1 2 + 2 2
20 = 4 2 + 2 2 + 0 2 + 0 2
120 = 82 + 62 + 42 + 22
6 = 02 + 12 + 12 + 22
20 = 42 + 22 + 02+ 02
取平方根，然后在其余部分重复上述步骤:
Take the square root and repeat this repeatedly for the remainder:
while (count != 4) {
root = (int) Math.sqrt(N)
N -= root * root
count++
}
但是，即使有解决方案，当 N 为23时，此操作也会失败:
But this fails when N is 23, even though there is a solution:
3 2 + 3 2 + 2 2 + 1 2
32 + 32+ 22 + 12
-
还有其他算法可以做到这一点吗?
Is there any other algorithm to do that?
是否总是有可能?
推荐答案
总是可行的吗?
是的，拉格朗日的四平方定理指出:
每个自然数都可以表示为四个整数平方的和.
every natural number can be represented as the sum of four integer squares.
已经通过多种方式证明了这一点.
It has been proved in several ways.
有一些更聪明的算法，但是我建议使用以下算法:
There are some smarter algorithms, but I would suggest the following algorithm:
将数字分解为主要因子.它们不一定是素数，但是它们越小越好:因此素数是最好的.然后针对以下所有这些因素解决任务，并使用欧拉的四角形.
Factorise the number into prime factors. They don't have to be prime, but the smaller they are, the better: so primes are best. Then solve the task for each of these factors as below, and combine any resulting 4 squares with the previously found 4 squares with the Euler's four-square identity.
(a 2 + b 2 + c 2 + d 2 )
(A 2 + B 2 + C 2 + D 2 )=
(aA + bB + cC + dD) 2
(aB-bA + cD-dC)+ sup <2 >
(aC-bD-cA + dB) 2 >
(aD + bC-cB-dA) 2
(a2 + b2 + c2 + d2)
(A2 + B2 + C2 + D2) =
(aA + bB + cC + dD)2 +
(aB − bA + cD − dC)2 +
(aC − bD − cA + dB)2 +
(aD + bC − cB − dA)2
-
给出一个数字 n (上述因素之一)，得到不大于 n 的最大平方，然后查看 n 减去这个平方可以使用 Legendre的三个平方写为三个平方的和平方定理:只有当该数字不是以下形式时，才有可能:
Given a number n (one of the factors mentioned above), get the greatest square that is not greater than n, and see if n minus this square can be written as the sum of three squares using the Legendre's three-square theorem: it is possible, if and only when this number is NOT of the following form:
4 a (8b + 7)
4a(8b+7)
如果发现该正方形不适合，请尝试下一个较小的正方形，直到找到一个.这样可以保证会有一个，并且大多数都可以在几次重试中找到.
If this square is not found suitable, try the next smaller one, ... until you find one. It guaranteed there will be one, and most are found within a few retries.
尝试以与步骤1中相同的方式找到实际的第二个平方项，但是现在使用关于两个平方和的费马定理在扩展意义上是:
Try to find an actual second square term in the same way as in step 1, but now test its viability using Fermat's theorem on sums of two squares which in extension means that:
如果与3模4一致的所有 n 质数因子均出现偶数指数，则 n 可表示为两个平方之和.反之亦成立.
if all the prime factors of n congruent to 3 modulo 4 occur to an even exponent, then n is expressible as a sum of two squares. The converse also holds.
如果发现该正方形不适合，请尝试下一个较小的正方形，直到找到一个.保证会有一个.
If this square is not found suitable, try the next smaller one, ... until you find one. It's guaranteed there will be one.
现在，我们将两个平方相减后得到余数.尝试减去第三个平方，直到得出另一个平方，这意味着我们有了一个解决方案.可以通过首先排除最大平方除数来改进此步骤.然后，在识别出两个平方项后，可以将每个平方项再次乘以该平方除数的平方根.
Now we have a remainder after subtracting two squares. Try subtracting a third square until that yields another square, which means we have a solution. This step can be improved by first factoring out the largest square divisor. Then when the two square terms are identified, each can then be multiplied again by the square root of that square divisor.
这大概是个主意.为了找到主要因素，有几种解决方案.在下面，我将仅使用筛网筛网.
This is roughly the idea. For finding prime factors there are several solutions. Below I will just use the Sieve of Eratosthenes.
这是JavaScript代码，因此您可以立即运行它-它会产生一个随机数作为输入并将其显示为四个平方的总和:
This is JavaScript code, so you can run it immediately -- it will produce a random number as input and display it as the sum of four squares:
function divisor(n, factor) {
var divisor = 1;
while (n % factor == 0) {
n = n / factor;
divisor = divisor * factor;
}
return divisor;
}
function getPrimesUntil(n) {
// Prime sieve algorithm
var range = Math.floor(Math.sqrt(n)) + 1;
var isPrime = Array(n).fill(1);
var primes = [2];
for (var m = 3; m < range; m += 2) {
if (isPrime[m]) {
primes.push(m);
for (var k = m * m; k <= n; k += m) {
isPrime[k] = 0;
}
}
}
for (var m = range; m <= n; m += 2) {
if (isPrime[m]) primes.push(m);
}
return {
primes: primes,
factorize: function (n) {
var p, count, primeFactors;
// Trial division algorithm
if (n < 2) return [];
primeFactors = [];
for (p of this.primes) {
count = 0;
while (n % p == 0) {
count++;
n /= p;
}
if (count) primeFactors.push({value: p, count: count});
}
if (n > 1) {
primeFactors.push({value: n, count: 1});
}
return primeFactors;
}
}
}
function squareTerms4(n) {
var n1, n2, n3, n4, sq, sq1, sq2, sq3, sq4, primes, factors, f, f3, factors3, ok,
res1, res2, res3, res4;
primes = getPrimesUntil(n);
factors = primes.factorize(n);
res1 = n > 0 ? 1 : 0;
res2 = res3 = res4 = 0;
for (f of factors) { // For each of the factors:
n1 = f.value;
// 1. Find a suitable first square
for (sq1 = Math.floor(Math.sqrt(n1)); sq1>0; sq1--) {
n2 = n1 - sq1*sq1;
// A number can be written as a sum of three squares
// <==> it is NOT of the form 4^a(8b+7)
if ( (n2 / divisor(n2, 4)) % 8 !== 7 ) break; // found a possibility
}
// 2. Find a suitable second square
for (sq2 = Math.floor(Math.sqrt(n2)); sq2>0; sq2--) {
n3 = n2 - sq2*sq2;
// A number can be written as a sum of two squares
// <==> all its prime factors of the form 4a+3 have an even exponent
factors3 = primes.factorize(n3);
ok = true;
for (f3 of factors3) {
ok = (f3.value % 4 != 3) || (f3.count % 2 == 0);
if (!ok) break;
}
if (ok) break;
}
// To save time: extract the largest square divisor from the previous factorisation:
sq = 1;
for (f3 of factors3) {
sq *= Math.pow(f3.value, (f3.count - f3.count % 2) / 2);
f3.count = f3.count % 2;
}
n3 /= sq*sq;
// 3. Find a suitable third square
sq4 = 0;
// b. Find square for the remaining value:
for (sq3 = Math.floor(Math.sqrt(n3)); sq3>0; sq3--) {
n4 = n3 - sq3*sq3;
// See if this yields a sum of two squares:
sq4 = Math.floor(Math.sqrt(n4));
if (n4 == sq4*sq4) break; // YES!
}
// Incorporate the square divisor back into the step-3 result:
sq3 *= sq;
sq4 *= sq;
// 4. Merge this quadruple of squares with any previous
// quadruple we had, using the Euler square identity:
while (f.count--) {
[res1, res2, res3, res4] = [
Math.abs(res1*sq1 + res2*sq2 + res3*sq3 + res4*sq4),
Math.abs(res1*sq2 - res2*sq1 + res3*sq4 - res4*sq3),
Math.abs(res1*sq3 - res2*sq4 - res3*sq1 + res4*sq2),
Math.abs(res1*sq4 + res2*sq3 - res3*sq2 - res4*sq1)
];
}
}
// Return the 4 squares in descending order (for convenience):
return [res1, res2, res3, res4].sort( (a,b) => b-a );
}
// Produce the result for some random input number
var n = Math.floor(Math.random() * 1000000);
var solution = squareTerms4(n);
// Perform the sum of squares to see it is correct:
var check = solution.reduce( (a,b) => a+b*b, 0 );
if (check !== n) throw "FAILURE: difference " + n + " - " + check;
// Print the result
console.log(n + ' = ' + solution.map( x => x+'²' ).join(' + '));
迈克尔·巴尔(Michael Barr)撰写的有关该主题的文章可能代表了更节省时间方法，但本文的目的更多地是作为一种证明，而不是一种算法.但是，如果您需要更高的时间效率，可以考虑使用它，以及更高效的分解算法.
The article by by Michael Barr on the subject probably represents a more time-efficient method, but the text is more intended as a proof than an algorithm. However, if you need more time-efficiency you could consider that, together with a more efficient factorisation algorithm.
这篇关于将给定数字表示为四个平方的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
