不同质数的乘积是否可以表示为完全平方数之和？

Question

给定: k个不同的质数，分别为a1, a2, ....., ak

目标: 找到将给定质数的乘积表示为完全平方数之和所需的最小完全平方数数量。

示例:

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

我已经测试了几个例子。对我来说看起来是正确的。但是基于少数例子泛化是不正确的。如果算法正确，如何证明它呢？

- cryptomanic

---

这个算法是完全正确的，因为最小的完全平方数是1，所以你总会得到某个数字;) - Yola

@Yola 这并不完美。请看我的回答。 - square1001

@square1001 我是第一个点赞你的回答的人，之前的评论只是个玩笑，你只是比我更快地回答了问题。 - Yola

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的三平方定理的解决方案

Legendre的三平方定理可以证明对于所有自然数n，除非n以4^a (8b + 7)的形式出现，否则都可以表示为三个整数的平方和。
还有Lagrange的四平方定理，它表明所有自然数都可以表示为四个整数的平方和。

因此，算法如下：

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

您可以对操作1进行O(sqrt(n))次运算，对操作2进行O(log(n))次运算，对操作3进行O(sqrt(n) * log(n))次运算，因此总时间复杂度为O(sqrt(n) * log(n))。

编辑： 由于n是不同的质数乘积，所以不会出现完全平方数，因此情况2不会出现。 当n mod 8 = 7时，情况1会出现。

- square1001

---

由于它是不同质数的乘积，情况“1”和“2”是不可能的。 - user58697

可能。请参见我的第一个示例，它将满足情况1。 - cryptomanic

@user58697，我已经进行了编辑并为情况1和2指定了特定说明。 - square1001