Question

How many of 1, 2, 3, ...,1000 can be written ad the difference of the squares of two non-negative integers?

Answer 1

This problem has bugged me few months ago, here is the M.SE thread: http://math.stackexchange.com/questions/56649/

Answer 2

750

Answer 3

Hey, satt, do you know any closed form?

Answer 4

but i cheated. however, if you want a nice worked out solution...

Answer 5

You used a program?

Answer 6

no i just looked it up. the solution is comprehensible though

Answer 7

Yep, check out André's answer in that url I posted.

Answer 8

here is a nice brief explanation
http://www.artofproblemsolving.com/Wiki/index.php/1997_AIME_Problems/Problem_1

Answer 9

seems much clearer than the link at stackexchange

Answer 10

For a unknown reason, my browser is failing to load the latex/mathjax in that url you posted.

Answer 11

ok then i can paraphrase if you like because it is short

Answer 12

That would be great :-)

Answer 13

if
\[x=(a-b)(a+b)\] then
\[a+b,a-b\] have the same parity. so
\[x\neq 4n+2=2(2n+1)\] because one factor is even and one is odd

Answer 14

that leaves odd n, and for any
\[x=2n+1\] you have
\[x=2n+1=(n+1)^2-n^2\] and for
\[x=4n\]
\[x=4n=(n+1)^2-(n-1)^2\]

Answer 15

I don't get it, how does this helps in counting?

Answer 16

i guess the point is, that if x is odd, we have
\[2n+1=(n+1)^2-n^2\] and if x is divisible by 4 we have
\[4n = (n+1)^2-(n-1)^2\] and if x is divisible by 2 and not 4, then it is not possible

Answer 17

so that counts out 1/4 of the numbers, leaving 750

Answer 18

http://takshzilabeta.com/cat-quant/number-systems/application-of-number-of-factors-part-ii/

Answer 19

this is like trying to find a pythagorean triple with one side given. say the side is 7, then you write
\[7=m^2-n^2=(m+n)(m-n)=7\times 1\] making
\[m=4, n=3\] and the triple is
\[7,24,25\] or
\[m^2-m^2,2mn,m^2+n^2\]

Answer 20

if the side is even but not divisible by 4, you cannot find a "primitive" triple, but you can if it is divisible by 4