不同质数的乘积作为完全平方和

Question

给定：k个不同的素数说a1,a2,.....,ak

Objective：将给定素数的乘积写为完全平方和所需的最小完全平方数。

示例：

k = 2, a1 = 3, a2 = 5 a1*a2 = 15 = 9 + 4 + 1 + 1 即 4 个完全平方的总和

k = 3, a1 = 2, a2 = 5, a3 = 11 a1*a2*a3 = 110 = 100 + 9 + 1 即对 3 个完全平方数求和

我的算法

让p = a1*a2*...........*ak

counter = 0
while p != 0:
    find the largest perfect square <= p say z
    p = p-z
    counter = counter + 1
return counter

我已经测试了几个例子。对我来说这似乎是正确的。但根据少数例子进行概括是不正确的。如何证明这一点（如果算法是正确的）？

Answer 1

实际上，在这些情况下您的解决方案是错误的：

k = 1, a1 = 61 => Your result: 61 = 49 + 9 + 1 + 1 + 1 / Best Result: 61 = 36 + 25
k = 2, a1 = 2, a2 = 37 => Your result: 74 = 64 + 9 + 1 / Best Result: 74 = 49 + 25

Legendre's Three-square Theorem是除n以外的所有自然数n是4^a (8b + 7)可以表示三平方和的形式
还有Lagrange's Four-square Theorem，所有自然数都可以表示四平方和

所以算法是：

可以O(sqrt(n))做操作1，O(log(n))做操作2，O(sqrt(n) * log(n))做操作3，所以整体时间复杂度是O(sqrt(n) * log(n)).

编辑：由于 n 是互不相异的质数积，所以没有出现平方数，所以情况 2 没有出现。如果 n mod 8 = 7.

则出现情况 1

Product of distinct prime numbers as a sum of perfect square