The product of various prime numbers as the sum of a perfect square

Question

Given : k different primes say a1, a2, ....., ak

Purpose . The minimum number of perfect squares required to record the product of these prime numbers as the sum of perfect squares.

Examples:

k = 2, a1 = 3, a2 = 5 a1*a2 = 15 = 9 + 4 + 1 + 1 and the sum of 4 perfect squares

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

My algorithm

let p = a1*a2*...........*ak

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

I tested it for a few examples. That seems right to me. But it is wrong to generalize based on a few examples. How to prove it (if the algorithm is correct)?

Answer 1

Is the decision right?

Actually, your solution is wrong in this 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 three square Legendre theorems

Legend Three-dimensional theorem is all natural numbers n, except n, this is the form 4^a (8b + 7) can express the sum of three squares.

There is also a Lagrange four-square theorem , and all natural numbers can express the sum of four squares.

So the algorithm:

• Calculate if n is a form 4^a (8b + 7) . You can use simple factorization. If so, the answer will be 4.
• Calculate if n is a square number. If so, the answer will be 1.
• Calculate if n can express two squares. If so, the answer is 2.
• If the value 1-3 is all false, the answer is 3.

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

EDIT: Since n is a separate simple product, the square number does not appear, then case 2 does not appear. Case 1 appears if n mod 8 = 7.