A few years ago I found an interesting programming problem:
"To find number of partition of n into sum of three squares with n < 10^9 and 1 second time limit."
Question: Does anyone know how to solve this problem with given constraints?
I think it can be do purely with asymptotic time complexity faster than O(n) only? Is there some clever math approach or it is code optimization engineering problem?
I found some info on https://oeis.org/A000164, but there are an O(n)-algo in FORMULA section
(because we need to find all divisors of each n-k^2 number for compute e(n-k^2)) and O(n)-algo in MAPLE section.
Yes. First factor the number, n - z^2, into primes, decompose the primes into Gaussian conjugates and find different expressions to expand and simplify to get a + bi, which can be then raised, a^2 + b^2. We can rule out any candidate n - z^2 that contains a prime of form 4k + 3 with an odd power.
This is based on expressing numbers as Gaussian integer conjugates. (a + bi)*(a - bi) = a^2 + b^2. See https://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares and https://stackoverflow.com/a/54839035/2034787