# 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, 10010001*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]
```