Solution #19

If n is the difference of two squares, then n can be written in the form a²-b² = (a+b)(a-b).

Suppose n is odd, and hence of the form 2m+1. Then let a = m+1 and b = m. Then (a+b)(a-b) = (m+1+m)(m+1-m) = 2m + 1 = n. So all odd numbers between 1 and 1000 are differences of two squares.

If n is even, at least one of a+b and a-b must be even. But if one is, they both are (because the difference between them is 2b, which is even). So n is then a multiple of 4. So no number than is 2 mod 4 can be written as the difference of two squares.

Suppose n is 0 mod 4. Then n = 4m for some m. Let a = m+1 and b = m-1, and we have (m+1+m-1)(m+1-(m-1)) = (2m)(2) = 4m.

Thus all odd numbers are all numbers 0 mod 4 between 1 and 1000 can be written as the difference of two squares, for a total of 750 numbers.