Difference of two square integers

[primarygun]

Find the 2002nd positive integer that is not the difference of two square integers.
I have idea for the answers, but there are two.

 

[shmoe]

How about posting your ideas?

 

[T@P]

well, that would mean that the integer cannot be a^2 - b^2, if a > b... i vaguely remember doing this before, but all i can remember is that it really comes down to finding what numbers *cant* be expressed as the difference of two squares, and then sort of just doing it... sorry I am not very helpful

 

[primarygun]

Thank you. That helps me a lot !

 

[Popey]

Hello, primarygun

Find the 2002nd positive integer that is not the difference of two square integers.
I have idea for the answers, but there are two.

There are two?

I can't understand how could that be.
If we put all these numbers in a series, just one is in the place 2002!

Anyway...


x=a^2-b^2
I SUPPOSE THAT a,b>0
If a number can be written as a difference of two perfect squares then I'll call that number a perfect difference

Well, that's what I found

First, I wrote down some squares, from 1^2 to 10^2 and I found the differences (you can easy do it on Excel)
I noticed that the differences are either
3,5,7,9,11,..
or
8,12,16,20,24,..

And there is not other!
(But there are numbers which are repeated many times, e.g
24=7^2-5^2, but also
24=5^2-1^2)

That is, the perfect differences are all even numbers (>=3) and all multiples of 4 (>=8)

I think that I must prove it

Well, say x=a^2-b^2 => x=(a+b)(a-b)
(That is we suppose that x is a perfect difference)
Of course a>b

x may be either odd or even

1)
x is even
so x=2q (where q>=1)
(a-b)(a+b)=2q
The second side is even
So a-b is even or a+b is even
but if a-b is even then a+b is even too:
a-b=2k =>
a=b+2k =>
a+b= (b+2k)+b = 2b+2k = 2(b+k)
Then x = 2k*2(b+k) = 4k(b+k)

Since k>=1 & b>=1 the value of k(b+k) has a minimum value 1*(1+1)=1*2=2

So, IF x is even THEN x=4r, where r>=2
(That is, all multiples of 4, except 4)

2)
x is odd

so x=2k+1
but if you set
a=k+1
b=k

then you get a^2-b^2 = (a-b)(a+b) = 1*(k+k+1) = 2k+1
Since b>=1 => k>=1 => x>2*1+1 =>
x>=3

So, IF x is odd & x>=3 THEN x is a perfect difference.

We found that the perfect differences are:
-the odd numbers (>=3)
-the multiples of 4 (>=8)

In other words if x=4k+m (you divide by 4, k is the quotient and m is the remainder)
m=0 => x is a perfect difference
m=1 => x is a perfect difference (because x is odd)
m=3 => x is a perfect difference (because x is odd)

But if m=2 <=> x=4m+2 <=> x=2(2m+1)
then x isn't divisible by 4, so x is NOT a perfect difference

The desired numbers are all the doubles of an odd, x=2(2m+1)
and also, x=4 and x=1
(x=4 is the only multiple of 4 which is less than 8
x=1 is the only odd number <3)
So, can you now find which NON perfect difference is at the place 2002?

If you don't understand something, just tell me, ok?

 

[primarygun]

Thanks.
Actually, I have already got the solution. But I suspect the answer from that book.

 

[Popey]

Doesn't matter !
It was actually a very good problem, so I was glad to deal with this!

 

[primarygun]

8006?......

 

[Popey]

I think you forgot to count x=4 and x=1

...
Put all even numbers in a series
The first one is 1
The next 3,5,7,...
The 2002nd is 4003 (if I calculated right)

Double them
The first is 2, then 6,10,14,...
The 2002nd is 8006

But there are also the numbers x=4 and x=1

There are 2 numbers, so we want the 2000th in the series 2,6,10,14,..., which is 7998
(n=2000=>
k=2n-1= 3999 =>
2k = 7998)

 

[shmoe]

Popey, 4 and 1 are a difference of square integers. 1=1^2-0^2 and 4^2-0^2. Zero is a square integer.

Also, while your proof shows that if a positive integer divisible by 2 is a difference of squares then it's divisible by 4, you did not show that every integer divisible by 4 is a difference of squares. Did you deal with this primarygun?

 

[Popey]

Thanks, shmoe!

I can't understand how could that be.
If we put all these numbers in a series, just one is in the place 2002!

Anyway...


x=a^2-b^2
I SUPPOSE THAT a,b>0

Since I didn't knew for a and b, if they are positive, I supposed that they are!
That's why I reject the values
x=1=1²-0²
x=4=4²-0²


With this shmoe's comment , primarygun is correct! the number is 8006

About your second comment, I did it to my paper but I didn't post it here, because I thought that it's not important.

Now I see clearly that it's important!
----------------------------------------------------
Well, suppose that x=4n (n>0 because x>0)
x=2*2n

if you set a=n+1 & b=n-1, then
a²-b²=
(a+b)(a-b)=
[(n+1)-(n-1)][(n+1)+(n-1)]=2*2n=x

Thank you!

 

[tongos]

were trying to count out the occurance of the sum of consecutive odd positive integers.