Product of distinct prime numbers as a sum of perfect square

Question

Given: k distinct prime numbers say a1, a2, ....., ak

Objective: Minimum number of perfect squares required to write product of the given primes as a sum of perfect squares.

Examples:

k = 2, a1 = 3, a2 = 5 a1*a2 = 15 = 9 + 4 + 1 + 1 i.e sum 4 perfect squares

k = 3, a1 = 2, a2 = 5, a3 = 11 a1*a2*a3 = 110 = 100 + 9 + 1 i.e. sum 3 perfect squares

My Algorithm

let 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

I have tested it for few examples. To me it seems to be correct. But it is incorrect to generalize on the basis of few examples. How to prove this(if algorithm is correct)?

Answer 1

Is the solution right?

Actually, your solution is wrong in these case:

• 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

Solution using Legendre's three-square theorems

Legendre's Three-square Theorem is the all natural numbers n except n is the form of 4^a (8b + 7) can express sum of three squares.
There is also Lagrange's Four-square Theorem and all natural numbers can express sum of four squares.

So the algorithm is:

1. Compute whether n is the form of 4^a (8b + 7). You can use prime factorization. If so, the answer is 4.
2. Compute whether n is a square number. If so, the answer is 1.
3. Compute whether n can express for two squares. If so, the answer is 2.
4. If 1-3 is all false, the answer is 3.

You can do operation 1 for O(sqrt(n)), operation 2 for O(log(n)), operation 3 for O(sqrt(n) * log(n)), so the overall time complexity is O(sqrt(n) * log(n)).

EDIT: Since n is a distinct prime product, so square number is not appeared, then case 2 is not appeared. Case 1 appears if n mod 8 = 7.