четырехквадратное представление суммы для целых чисел до N

Question

Lagrange's four-square theorem доказывает, что любое натуральное число можно записать в виде суммы четырех квадратных чисел. Мне нужно найти любой способ написать натуральное число x как сумму четырех квадратных чисел для всех 0 <= x <= N для любого заданного верхнего предела N.

То, что я сделал до сих пор, находит двухквадратное представление суммы для всех чисел <= N, для которых его можно найти, и сохранил их в массиве с именем two_square_div. Тогда я использовал жадный подход, как следующее:

last_two_square_sum = 0 

for num in 0..N 
    if num can be written as sum of two square 
     last_two_square_sum = num 
    other_last_two_square_sum = num - last_two_square_sum 
    four_square_div[num] = (two_square_div[last_two_square_sum], two_square_div[other_last_two_square_sum] 

Но этот подход не работает для чисел, как 23, для которых last_two_square_sum = 20other_last_two_square_sum = 3. Но 3 не может быть записана как сумма двух квадратов, поэтому этот метод терпит неудачу.

Так может ли кто-нибудь предоставить правильное решение O(N) или любой полезный намек? Спасибо.

Answer 1

Ваш алгоритм должен выполнить несколько попыток (если он уже выполняется, то условие выхода должно быть улучшено).

23 может быть написано как 3 + 20, да; но 3 не разложим второго порядка и не может привести к решению.

Итак, вы идете на: дальше вы пробуете 4 + 19, и на этот раз это 19, что отклонено. Затем вы пытаетесь 5, так что 23-5 является 18, и 5 составляет 1 + 2 в то время как 18 является 3 + 3 .

(Конечно, это совсем не O (N)).

Непонятно, как вы достигаете 20 и не принимаете предыдущие решения; попробуйте опубликовать весь код.

Кроме того, попробуйте запросить Math StackExchange.