Perfect square or not?

[only_human]

OK, after lopping off the even number of trailing 0's (if present), we have every square ending in:
001

Talking about odd squares so that we can stop talking about the trailing 0's, are there any other simple things left?

What about the next more significant bit, bit 3?
x001

I think that if it is set, that means that either bit 2 or bit 1 of the original unsquared number was set (but not not both)
That is x = b₁ xor b₂

So looking at sequential odd numbers, when they are squared, bit 3 is going to count like Gray Code, like this 0,1,1,0:

odd squares in sequence
1,9,25,49 in binary:
0000 0001
0000 1001
0001 1001
0011 0001

81,121,169,225 in binary:
0101 0001
0111 1001
1010 1001
1110 0001

So if someone said they were passing you odd squares in sequence, but would only let you look at bit 3, you could call them a liar if it didn't go 0,1,1,0, 0,1,1,0, ... in sequence.

[only_human]

So Bob has humongous squares but could only tell Alice about a few bits at the least significant end. The canny ticks Alice can try:

Lop off trailing zeroes, if any, there must be an even number of them or it is not a square

What's left must end in 001 or it is not a square.

That's about all unless Bob is juggling massive squares in sequence.

If the numbers are in sequence, bit 3 has a pattern that I mentioned above.

Originally Posted by LaurV

edit: like this ......xxxxxxx001*, where the * can be replaced with nothing, or with an even number of zeroes.
edit2: xxxx from above it is always a triangular number, so if you can test this fast... :P

As LaurV says, after lopping off any trailing zeroes and then lopping off the 001, what remains is a triangular number.

A formula for triangular numbers is (n² + n)/2

An odd number squared:
(2n + 1)²
4(n² + n ) + 1
or as
8(n² + n)/2 + 1

This gives another method of calling Bob a liar because if the squares are in sequence, the triangular numbers will be in sequence too. Any two triangular numbers in sequence will add up to a square. So Alice can remember a few bits of the triangular number part and add it to the next triangular number and then apply the square tests she knows on that sum too:

odd squares in sequence
9,25,49, 81,121,169,225 in binary:
00001 001
00011 001
00110 001
01010 001
01111 001
10101 001
11100 001

The triangular numbers in the left column above are 1, 3, 6, 10, 15, 21, 28
Any adjacent triangular numbers in sequence can be added and the sum is square. After lopping off the lower bits she expects in a square, to the left of that is again a triangular number...