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

Question

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

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

例子:

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

k = 3, a1 = 2, a2 = 5, a3 = 11a1*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 => 你的结果:61 = 49 + 9 + 1 + 1 + 1/最佳结果:61 = 36 + 25
• k = 2, a1 = 2, a2 = 37 => 你的结果:74 = 64 + 9 + 1/最佳结果:74 = 49 + 25

使用勒让德的三平方定理求解

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

所以算法是:

1. 计算n是否是4^a (8b + 7)的形式。您可以使用质因数分解。如果是，答案是 4。
2. 计算 n 是否为平方数。如果是，答案是 1。
3. 计算 n 是否可以表示两个正方形。如果是，答案是 2。
4. 如果 1-3 都为假，则答案为 3。

您可以为 O(sqrt(n)) 执行操作 1，为 O(log(n)) 执行操作 2，为 O( sqrt(n) * log(n))，所以整体时间复杂度为O(sqrt(n) * log(n))。

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