Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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.) –  André Nicolas Sep 11 '12 at 3:15
    
See mathoverflow.net/questions/57981/…. –  lhf Sep 11 '12 at 3:28
    
Whoops, thought I searched far and wide before asking. Sorry about that. –  Domonic Mei Sep 11 '12 at 16:39
add comment

1 Answer 1

up vote 0 down vote accepted

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
share|improve this answer
    
If $n$ is $2$ or $3 \pmod 4$ you can return false immediately. –  Ross Millikan Sep 11 '12 at 3:45
    
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. –  Old John Sep 11 '12 at 10:19
    
You can also stop as soon as $b < a^2$ instead of $b<0$. –  lhf Sep 11 '12 at 12:03
    
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$. –  Old John Sep 11 '12 at 23:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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