1
$\begingroup$

The title says it all. On my homework I am tasked with creating an algorithm that determines whether or not a natural number n can be written as the sum of two squares.

The only stipulation I am given is that I have access to (theoretically) a computer which will quickly tell me if a number k is a perfect square.

I really am just stuck on how to go about doing this, so even just a small hint in the right direction would be appreciated!

  • 0
    Not helpful for large numbers, but the non-negative integer $n$ is a sum of two squares iff every prime of the form $4k+3$ in the prime factorization of $n$ occurs to an even power. (Am counting $0$ as a perfect square, and allow the two squares to be equal.)2012-09-11
  • 0
    See http://mathoverflow.net/questions/57981/testing-whether-an-integer-is-the-sum-of-two-squares.2012-09-11
  • 0
    Whoops, thought I searched far and wide before asking. Sorry about that.2012-09-11

1 Answers 1

0

From the description, I guess you're supposed to brute-force it:

a=0 while true do    b=n-a^2    if b<0 return false    if b is a perfect square return true    a=a+1 end 
  • 1
    If $n$ is $2$ or $3 \pmod 4$ you can return false immediately.2012-09-11
  • 0
    Should that not be "if $n$ is $3 \pmod{4}$ then return false"? Since $10 \equiv 2 \pmod{4}$ and 10 *is* a sum of 2 squares.2012-09-11
  • 0
    You can also stop as soon as $b < a^2$ instead of $b<0$.2012-09-11
  • 0
    It might not be a great saving, but we could also divide by any square factors first, since they have no effect on representability by a sum of 2 squares. e.g. if $n\equiv 0 \pmod{4}$, then replace $n$ by $n/4$.2012-09-11