Выразить данное число в виде суммы четырех квадратов
Я ищу алгоритм, который выражает данное число в виде суммы (до) четырех квадратов.
Примеры
120 = 82 + 62 + 42 + 22
6 = 02 + 12 + 12 + 22
20 = 42 + 22 + 02+ 02
Мой подход
Возьмите квадратный корень и повторите это несколько раз для остатка:
while (count != 4) {
root = (int) Math.sqrt(N)
N -= root * root
count++
}
Но это терпит неудачу, когда N равно 23, хотя есть решение:
32 + 32+ 22 + 12
Вопрос
Есть ли другой алгоритм для этого?
Это всегда возможно?
5 ответов
Всегда возможно?
Да, теорема Лагранжа о четырех квадратах утверждает, что:
каждое натуральное число может быть представлено как сумма четырех целочисленных квадратов.
Это было доказано несколькими способами.
Алгоритм
Есть более разумные алгоритмы, но я бы предложил следующий алгоритм:
Разложите число в простые множители. Они не должны быть простыми, но чем они меньше, тем лучше: простые числа лучше. Затем решите задачу для каждого из этих факторов, как показано ниже, и объедините все получающиеся 4 квадрата с ранее найденными 4 квадратами с тождеством Эйлера из четырех квадратов.
(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) 2 +
(aC - bD - cA + дБ) 2 +
(aD + bC - cB - dA) 2
Учитывая число n (один из факторов, упомянутых выше), получите наибольший квадрат, который не больше n, и посмотрите, можно ли записать n минус этот квадрат как сумму трех квадратов, используя теорему Лежандра о трех квадратах: возможно, если и только когда этот номер НЕ имеет следующую форму:
4 а (8б +7)
Если этот квадрат не подходит, попробуйте следующий меньший, ... пока не найдете. Он гарантированно будет один, и большинство из них будут найдены в течение нескольких повторных попыток.
Попробуйте найти фактический член второго квадрата так же, как в шаге 1, но теперь проверьте его жизнеспособность, используя теорему Ферма о суммах двух квадратов, что в дальнейшем означает, что:
если все простые множители n, совпадающие с 3 по модулю 4, совпадают с четным показателем степени, то n выражается как сумма двух квадратов. Обратное также верно.
Если этот квадрат не подходит, попробуйте следующий меньший, ... пока не найдете. Гарантируется, что будет один.
Теперь у нас есть остаток после вычитания двух квадратов. Попробуйте вычесть третий квадрат до тех пор, пока он не даст другой квадрат, что означает, что у нас есть решение. Этот шаг можно улучшить, сначала вычеркнув самый большой квадратный делитель. Затем, когда два квадратных члена определены, каждый из них может быть снова умножен на квадратный корень этого квадратного делителя.
Это примерно идея. Для нахождения простых факторов есть несколько решений. Ниже я просто буду использовать Сито Эратосфена.
Это код JavaScript, так что вы можете запустить его немедленно - он будет выдавать случайное число в качестве ввода и отображать его как сумму четырех квадратов:
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(' + '));Статья Майкла Барра на эту тему, вероятно, представляет собой более эффективный по времени метод, но текст скорее предназначен для доказательства, чем для алгоритма. Однако, если вам нужна большая экономия времени, вы можете подумать об этом вместе с более эффективным алгоритмом факторизации.
Это всегда возможно - это теорема в теории чисел, называемая "теорема Лагранжа о четырех квадратах".
Чтобы решить ее эффективно: в статье Рандомизированные алгоритмы в теории чисел (Рабин, Шаллит) приводится метод, который выполняется за ожидаемое время O((log n)^2).
Здесь есть интересная дискуссия о реализации: https://math.stackexchange.com/questions/483101/rabin-and-shallit-algorithm
Найдено через Википедию: теорема Лангранжа о четырех квадратах.
Вот решение, Простое 4 петли
max = square_root(N)
for(int i=0;i<=max;i++)
for(int j=0;j<=max;j++)
for(int k=0;k<=max;k++)
for(int l=0;l<=max;l++)
if(i*i+j*j+k*k+l*l==N){
found
break;
}
Таким образом, вы можете проверить на любые номера. Вы можете использовать условие разрыва после двух циклов, если сумма превышает, тогда разбейте ее.
const fourSquares = (n) => {
const result = [];
for (let i = 0; i * i <= n; i++) {
for (let j = 0; j * j <= n; j++) {
for (let k = 0; k * k <= n; k++) {
for (let l = 0; l * l <= n; l++) {
if (i * i + j * j + k * k + l * l === n) {
result.push(i, j, k, l);
return result;
}
}
}
}
}
return result;
}
const fourSquares = (n) => {
let a = Math.sqrt(n);
let b = Math.sqrt(n - a * a);
let c = Math.sqrt(n - a * a - b * b);
let d = Math.sqrt(n - a * a - b * b - c * c);
if (n === a * a + b * b + c * c + d * d) {
return [a, b, c, d];
}
}
const fourSquares = (n) => {
const result = [];
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= n; j++) {
for (let k = 0; k <= n; k++) {
for (let l = 0; l <= n; l++) {
if (i * i + j * j + k * k + l * l === n) {
result.push(i, j, k, l);
return result;
}
}
}
}
}
return result;
}
Это работает слишком долго
const fourSquares = (n) => {
const result = [];
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= (n - i * i); j++) {
for (let k = 0; k <= (n - i * i - j * j); k++) {
for (let l = 0; l <= (n - i * i - j * j - k * k); l++) {
if (i * i + j * j + k * k + l * l === n) {
result.push(i, j, k, l);
return result;
}
}
}
}
}
return result;
}