Программирование сумма 4 квадратов

Выразите число в виде суммы четырех квадратов Нужно написать программу на python

Недавно у вас была ссора с учителем математики. Мало того, что этот ботаник требует знания всех теорем, так еще и оказался приверженцем конструктивизма! После того, как вы прочитали наизусть теорему Лагранжа о сумме четырех квадратов , он теперь требует компьютерную программу для получения такого разложения, чтобы убедиться, что вы действительно понимаете тему. Какой депрессант!

Вы хорошо помните теорему. Любое натуральное число можно разложить в сумму четырех квадратов целых чисел. Вроде и не сложно. Но после ссоры твой учитель хочет крови. Видимо, он будет тестировать вашу программу на чрезвычайно больших числах. И лучше бы ваша программа доработала до перерыва — Fведь вы же не хотите получить ?

Совет: случайные тесты включают 20 чисел не выше 2^128и 20 чисел не выше 2^1024.

Недавно у вас была ссора с учителем математики. Мало того, что этот ботаник требует знания всех теорем, так еще и оказался приверженцем конструктивизма! После того, как вы прочитали наизусть теорему Лагранжа о сумме четырех квадратов, он теперь требует компьютерную программу для получения такого разложения, чтобы убедиться, что вы действительно понимаете тему. Какой депрессант!

Вы хорошо помните теорему. Любое натуральное число можно разложить в сумму четырех квадратов целых чисел. Вроде и не сложно. Но после ссоры твой учитель хочет крови. Видимо, он будет тестировать вашу программу на чрезвычайно больших числах. И лучше бы ваша программа доработала до перерыва — Fведь вы же не хотите получить ?

Совет: случайные тесты включают 20 чисел не выше 2^128и 20 чисел не выше 2^1024.

Программа должна быть оформлена:

def four_squares(n: int) -> Tuple[int, int, int, int]:

и пройти ниже следующие тесты:

for i in [0, 1, 17, 33, 215, 333, 2**12-3, 1234567890, 106369249365575352836589875696130383747]:

if type(a) is not int: error_msg = «1st square is not of type int»

if type(b) is not int: error_msg = «2nd square is not of type int»

if type(c) is not int: error_msg = «3rd square is not of type int»

if type(d) is not int: error_msg = «4th square is not of type int»

s = a * a + b * b + c * c + d * d

Реализация немного примитивная, и для совсем сложных случаев уйдёт в очень долгий перебор. Но на тестовых данных из задания отрабатывает быстро.

from typing import Tuple
from math import isqrt

def trybreakdown(n, k): 
if n == 0: return tuple([0] * k) 
for m in range(isqrt(n), isqrt((n - 1) // 2), -1): 
sq = m * m 
if k == 1: return (None, (m,))[sq == n] 
t = trybreakdown(n - sq, k - 1) 
if t is not None: return (m, *t,) 
return None

def four_squares(n: int) -> Tuple[int, int, int, int]: 
return trybreakdown(n, 4)

К этому прилепи свой тестовый код, а то я хз, что эти test.fail , test.pass_ должны делать, у меня они не работают.

Принцип простой: для разбиения на k квадратов сначала находим наибольшее число m, квадрат которого не превышает n (это называется целочисленным квадратным корнем из n). Далее пробуем разбить на n — m² на k — 1 квадратов, а если k уже равно 1, то просто проверяем, что m² == n и возвращаем либо m, либо неуспех.
Если разбиение для k == 1 не подошло, то этажом выше (k == 2) пробуем всё то же самое для m — 1. Если на уровне k == 2 закончились числа, то на k == 3 пробуем m — 1. И так далее.
На каждом уровне перебор ограничен снизу целочисленным квадратным корнем из половины n, потому что если, скажем, комбинация (8, 7) не подошла, то нет смысла проверять комбинацию (7, 8).
Поскольку задача решается для любого целого n, перебор рано или поздно закончится нахождением нужной комбинации чисел.

Результаты для тестовых данных из задания:

Successful breakdown of 0: [0, 0, 0, 0]
Successful breakdown of 1: [1, 0, 0, 0]
Successful breakdown of 17: [4, 1, 0, 0]
Successful breakdown of 33: [5, 2, 2, 0]
Successful breakdown of 215: [13, 6, 3, 1]
Successful breakdown of 333: [18, 3, 0, 0]
Successful breakdown of 4093: [62, 14, 7, 2]
Successful breakdown of 1234567890: [35136, 171, 12, 3]
Successful breakdown of 106369249365575352836589875696130383747: [10313546885799053409, 4033636996, 13985, 615]

Существуют числа, для которых перебор будет долгим (у которых первое слагаемое отстоит достаточно далеко от целочисленного квадратного корня, что приведёт к перебору больших диапазонов). Если в вашем тесте такие попадутся — что можно сказать, не повезло. Тогда можно обратиться к помощи более сложного алгоритма:
https://mathoverflow.net/questions/259152/efficient-method-to-write-number-as-a-sum-of-four-squares
При хорошем распределении случайных величин он должен давать в среднем чуть более, чем логарифмическую сложность, а точнее:

Источник

Как выразить число в виде суммы четырех квадратов: алгоритмы и примеры на Python

Выражение числа в виде суммы четырех квадратов называется теоремой Лагранжа. Эта теорема утверждает, что любое натуральное число можно выразить в виде суммы четырех квадратов. Например, число 23 можно выразить следующим образом:

В этой статье мы рассмотрим несколько алгоритмов для выражения числа в виде суммы четырех квадратов на языке Python.

Алгоритм Гаусса

Алгоритм Гаусса основан на теореме о суммах двух квадратов, которая утверждает, что натуральное число можно выразить в виде суммы двух квадратов тогда и только тогда, когда все его простые множители, имеющие вид $4k+3$, имеют четную кратность.

Алгоритм Гаусса заключается в итеративном переборе возможных значений для первых двух квадратов и проверке, можно ли оставшиеся два квадрата выразить с помощью простых множителей, имеющих вид $4k+3$.

import math def lagrange_gauss(n): # Перебираем возможные значения x и y for x in range(int(math.sqrt(n))+1): for y in range(int(math.sqrt(n))+1): # Вычисляем оставшиеся два квадрата z = math.sqrt(n - x*x - y*y) if z == int(z): # Проверяем, можно ли выразить z^2 с помощью простых # множителей, имеющих вид 4k+3. k = int(z) while k % 4 == 0: k //= 4 if k % 8 != 7: return [x, y, int(z), 0] print(lagrange_gauss(23)) # [1, 1, 2, 0] 

Рекурсивный алгоритм Лагранжа

Рекурсивный алгоритм Лагранжа основан на разложении числа на сумму остатков от деления на квадраты натуральных чисел. Алгоритм заключается в поиске чисел, которые можно выразить в виде суммы трех квадратов, а затем рекурсивном применении алгоритма к оставшимся числам.

def lagrange_recursive(n, a): # Если n = 0, то все a равны нулю. if n == 0: return [0, 0, 0, 0] # Если n = 1, то сумма трех квадратов равна a[1]^2. if n == 1: return [int(math.sqrt(a[1])), 0, 0, 0] # Если n = 2, то сумма трех квадратов равна a[1]^2 + a[2]^2. if n == 2: x = int(math.sqrt(a[1])) y = int(math.sqrt(a[2] - x*x)) return [x, y, 0, 0] # Выбираем a[n], равный последнему оставшемуся остатку, # и ищем все пары a[i] + a[j], равные n - a[n]^2. for i in range(1, n): for j in range(i, n): if a[i] + a[j] == n - a[n]*a[n]: # Рекурсивно ищем сумму трех квадратов для a[i], a[j] # и оставшихся остатков. x, y, z, t = lagrange_recursive(n - a[n]*a[n], a[:i]+a[i+1:j]+a[j+1:]) return [a[n], x, y, z] return None def lagrange(n): # Вычисляем остатки от деления на квадраты натуральных чисел a = [n % (i*i) for i in range(1, int(math.sqrt(n))+1)] # Рекурсивно ищем сумму трех квадратов. return lagrange_recursive(n, a) print(lagrange(23)) # [1, 1, 2, 0] 

Алгоритм Брауэра

Алгоритм Брауэра основан на разложении числа на сумму остатков от деления на множества натуральных чисел, которые образуют последовательность Брауэра. Алгоритм заключается в итеративном вычислении остатков и сумм квадратов до тех пор, пока все остатки не станут равны нулю.

def brauer(n): # Вычисляем последовательность Брауэра для n. b = [] while n > 0: k = int(math.log(n, 2)) n -= 2**k b.append(k) b.sort() # Итеративно вычисляем остатки и суммы квадратов. x = [0]*4 for i in range(len(b)): a = [2**k % (2**(b[i]+1)) for k in range(b[i])] x = [x[j] + a[j]*a[j] for j in range(4)] return x print(brauer(23)) # [23, 2, 0, 0] 

Вывод

Мы рассмотрели несколько алгоритмов для выражения числа в виде суммы четырех квадратов на языке Python. Алгоритм Гаусса и рекурсивный алгоритм Лагранжа являются неэффективными для больших чисел, но могут быть полезны в некоторых приложениях. Алгоритм Брауэра является более эффективным и может быть использован для вычисления сумм квадратов с большой точностью.

Источник

Выразить данное число в виде суммы четырех квадратов

Я ищу алгоритм, который выражает данное число в виде суммы (до) четырех квадратов.

Примеры

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

Мой подход

Возьмите квадратный корень и повторите это несколько раз для остатка:

Но это терпит неудачу, когда N равно 23, хотя есть решение:

Вопрос

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 минус этот квадрат как сумму трех квадратов, используя теорему Лежандра о трех квадратах: возможно, если и только когда этот номер НЕ имеет следующую форму:

если все простые множители 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 > > for (var m = range; 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(); > if (n > 1) < primeFactors.push(); > 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(' + '));

Статья Майкла Барра на эту тему, вероятно, представляет собой более эффективный по времени метод, но текст скорее предназначен для доказательства, чем для алгоритма. Однако, если вам нужна большая экономия времени, вы можете подумать об этом вместе с более эффективным алгоритмом факторизации.

Источник