Moser–de Bruijn sequence

In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4. It begins

For instance, 69 belongs to this sequence because it equals 64 + 4 + 1, a sum of three distinct powers of 4.

Another definition of the Moser–de Bruijn sequence is that it is the ordered sequence of numbers whose binary representation has nonzero digits only in the even positions. For instance, 69 = 1000101₂, a binary number that has nonzero digits in the positions for 2⁶, 2², and 2⁰, all of which have even exponents. These are also the numbers whose base-4 representation uses only the digits 0 or 1. For a number in this sequence, the base-4 representation can be found from the binary representation by skipping the binary digits in odd positions, which should all be zero. For instance, 69 = 1011₄. Equivalently, they are the numbers whose binary and negabinary representations are equal.

It follows from either the binary or base-4 definitions of these numbers that they grow roughly in proportion to the square numbers. The number of elements in the Moser–de Bruijn sequence that are below any given threshold ${\displaystyle n}$ is proportional to ${\displaystyle {\sqrt {n}}}$, a fact which is also true of the square numbers. In fact the numbers in the Moser–de Bruijn sequence are the squares for a version of arithmetic without carrying on binary numbers, in which the addition and multiplication of single bits are respectively the exclusive or and logical conjunction operations.

...
Wikipedia