不同素数的乘积作为完美平方的总和

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

我已经测试了几个例子.对我而言似乎是正确的.但在少数例子的基础上进行概括是不正确的.如何证明这一点(如果算法正确)？

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

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

勒让德的三平方定理是所有自然数n除了n是4^a (8b + 7)可以表示三个平方和的形式.
还有四平方和定理和所有自然数可以表达的四个正方形总和.

所以算法是:

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.