There is Lagrange's four-square theorem, which statea that

Given an integer $N$, we can write $N$ as a sum of four squares $A^2+B^2+C^2+D^2=N$.

How can I find a valid solution with time complexity of $O(1)$ or $O(\sqrt N)$? I only have to find one solution.

Here is my $O(1)$ algorithm:

while(count!=4){
     solution = sqrt(N)
     print solution
     N-= solution*solution
     count++       
}

But it does not works for all $N$, for example it fails for $N=23$. Is there any other solution?

Try this: Legendre's_three-square_theorem

Assume $4\not\mid N$. If not, divide $N$ by $4^k$ and multiply $2^k$ back in the end. Find an $A$ satisfying $N-A^2\not\equiv0,4,7 \mod 8$. It's always valid to choose $A=\lfloor\sqrt{N}\rfloor$ or $\lfloor\sqrt{N}\rfloor-1$. (Choose the even one if $N\equiv 1,5 \mod 8$ and the odd one otherwise.) Now $N-A^2$ is an integer in $O(\sqrt{N})$ and you can find $B,C,D$ in $O(\sqrt{N})$ easily.

Edit: Since $B,C,D\le cN^{\frac{1}{4}}$ for some small constant $c$, we can enumerate two of them (suppose $B$ and $C$) and check whether the corresponding $D$ is an integer. This works in $O(\sqrt{N})$. There might be some faster solutions.

  • Couldn't figure out for ages how you can find B, C, D in O ($N^{1/2}$). But that is obviously because $B^2+C^2+D^2 ≤ O(N^{1/2})$, so B, C, D ≤ $O(N^{1/4})$... – gnasher729 Jan 10 '17 at 22:22

I am going to provide you with 4 links and I hope it will help you.

this one is an online calculator based on an algorithm from math overflow.

http://www.mathcelebrity.com/foursquare.php?num=+178&pl=Show+Lagrange+Four-Square+Notation

the math overflow algorithm can be found here.

https://stackoverflow.com/questions/11732555/how-to-find-all-possible-values-of-four-variables-when-squared-sum-to-n

and then there is also this algorithm from cs stackexchange

How fast can we find all Four-Square combinations that sum to N?

and if you want to do a bit of work, then there is this algorithm that can find the sum of 2 squares for a given integer. So you would have to divide your number in two ( not necessarily equal part ) and then add up the results to get a 4 square representation.

https://math.stackexchange.com/questions/1972771/is-this-the-general-solution-of-finding-the-two-original-squares-that-add-up-to/1977767?noredirect=1#comment4062390_1977767

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.