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:

     solution = sqrt(N)
     print solution
     N-= solution*solution

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.

  • $\begingroup$ 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})$... $\endgroup$
    – 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.


the math overflow algorithm can be found here.


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.


  • 3
    $\begingroup$ Whilst this may theoretically answer the question, it would be preferable to include the essential parts of the answer here, and provide the link for reference. $\endgroup$
    – Raphael
    Jan 11 '17 at 7:56
  • $\begingroup$ This answer also appears at mathoverflow.net/a/259203/37212. $\endgroup$
    – D.W.
    Jan 20 '17 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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