Square numbers in binary

19 May 2022

I was reading the Wikipedia article on square numbers (as one does), and came across this fun trivia paragraph:

In base 10, a square number can end only with digits 0, 1, 4, 5, 6 or 9, as follows:

if the last digit of a number is 0, its square ends in 0 (in fact, the last two digits must be 00);
if the last digit of a number is 1 or 9, its square ends in 1;
if the last digit of a number is 2 or 8, its square ends in 4;
if the last digit of a number is 3 or 7, its square ends in 9;
if the last digit of a number is 4 or 6, its square ends in 6; and
if the last digit of a number is 5, its square ends in 5 (in fact, the last two digits must be 25).

Similar rules can be given for other bases, or for earlier digits (the tens instead of the units digit, for example).^{[citation needed]} All such rules can be proved by checking a fixed number of cases and using modular arithmetic.

So I decided to give finding patterns like this a shot, in binary. I created a table of the first 1024 squares in binary, viewable here, and had a look.

The most obvious pattern is that if a number ends in 10, then its square will end in 100; and more generally, if a number ends in 1+a×0 (plus meaning concatenation and times meaning repetition of the bitstring here), then its square will end in 1+2a×0.

If a number ends in 011, its square will end in 1001. If a number ends in a ones, its square will end in 1 + a×0 + 1; for example, 1011111 ends in five ones, and its square is 10001101000001. (In decimal these are 95 and 9025.)

If a number ends in 101, its square will also end in 1001, but this follows a different rule: a number ending in 1+a×0+1 will have its square end in 1+(a+1)×0+1; for example, 193, which is 11000001, ends in 1 + five zeroes + 1, and has its square (37249, 1001000110000001) end in 1 + six zeroes + 1.

I'm wondering whether a string-rewriting system could manage to correctly square numbers, given a limited number of rewrite rules: it seems so far to be that, moving from right to left, applying these transformations and concatenating the results gives the square. The rules I gave above aren't enough for this, though; repeated ones in the middle or beginning of a number become a different pattern, but for numbers with lots of zeroes and few consequetive ones, it seems to loosely hold for their ends. Example: 392 in binary is 110001000. Its square, 153664, is 100101100001000000. 392 ends in a 1 and three zeroes, and its square ends in a 1 and six zeroes. Before the three final zeroes is a one, three zeroes, and one; before the six final zeroes of the square are a one, four zeroes, and a one. The leading 11 of 392 does turn into the not-yet-predicted pattern 100101.

(For the listing linked above, I used the following small function to format the binary numbers in groups of four. I've had to rewrite this a couple of times over time, so posting it here so it has a home online.)

def fmt_num_bin(n):
    b = f"{n:b}"[::-1]
    a = [b[i:i+4] for i in range(0, len(b), 4)]
    return "_".join(a)[::-1]

Index