Разложить число на кратчайшую сумму квадратов

Попробуйте подумать в такую сторону

S = summ(a[i]*i*i); где i=1..sqrt(10 000 000), a[i] - множители. Целевая функция min(summ(a[i]))

Понятно что самый длинный вариант это сумма единичек. Взяв за основу единички можно уменьшать целевую функцию добавив квадраты больших чисел. И не смотреть при переборе варианты когда целевая функция принимает большее значение чем текущая.

Идея такая что нужно схлопывать единички до минимума целевой функции. Это как вариант в какую сторону двигаться. У кого есть что нибудь получше пишите мне тоже интересно.

Вот в которой доказывается следующий факт.

Если x^2 + y^2 = n , то

(x+y)^2 + (x-y)^2 = 2*n

Имея данную формулу можно быстро уменьшить перебор для исходной целевой функции.

Ещё вот интересная о том что наша целевая функция меньше либо равна 4.

Теорема Лагранжа о сумме четырёх квадратов утверждает, что

Всякое натуральное число можно представить в виде суммы четырёх квадратов целых чисел.

Круг поиска отсюда ещё сузился.

Так как их максимум четыре можно в четыре вложенных циклов получить как или вот пример реализации на .