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.

Equivalently, they are the numbers whose binary representations are nonzero only in even positions.

This representation as a sum defines a one-to-one correspondence between integers and pairs of integers, listed in order of their positions on a Z-order curve.

The Moser–de Bruijn sequence can be used to construct pairs of transcendental numbers that are multiplicative inverses of each other and both have simple decimal representations.

The numbers in the Moser–de Bruijn sequence are formed by adding distinct powers of 4.

The sequence lists these numbers in sorted order; it begins[1] For instance, 69 belongs to this sequence because it equals 64 + 4 + 1, a sum of three distinct powers of 4.

For instance, 69 belongs to the sequence, because its binary representation 10001012 has nonzero digits in the positions for 26, 22, and 20, all of which have even exponents.

Equivalently, they are the numbers whose binary and negabinary representations are equal.

[1][2] Because there are no two consecutive nonzeros in their binary representations, the Moser–de Bruijn sequence forms a subsequence of the fibbinary 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.

[4] In connection with the Furstenberg–Sárközy theorem on sequences of numbers with no square difference, Imre Z. Ruzsa found a construction for large square-difference-free sets that, like the binary definition of the Moser–de Bruijn sequence, restricts the digits in alternating positions in the base-

, Ruzsa's construction generates the Moser–de Bruijn sequence multiplied by two, a set that is again square-difference-free.

However, this set is too sparse to provide nontrivial lower bounds for the Furstenberg–Sárközy theorem.

with a binary value (expressed here in hexadecimal) that has ones in all of its even positions, and set

[7] Extending the property, De Bruijn (1964) found infinitely many other linear expressions like

both belong to the Moser–de Bruijn sequence, uniquely represent all integers.

The inverse of this bijection gives a linear ordering on the points in the plane with non-negative integer coordinates, which may be used to define the Z-order curve.

[1][10] In connection with this application, it is convenient to have a formula to generate each successive element of the Moser–de Bruijn sequence from its predecessor.

can be obtained by filling in the bits in odd positions of the binary representation of

Filling the bits and adding one can be combined into a single addition operation.

The two hexadecimal constants appearing in this formula can be interpreted as the 2-adic numbers

In Golomb's game, two players take turns removing coins from a pile of

In each move, a player may remove any number of coins that belongs to the Moser–de Bruijn sequence.

A winning strategy for playing this game is to decompose the current number of coins,

[3] The Moser–de Bruijn sequence forms the basis of an example of an irrational number

a decimal number whose nonzero digits are in the positions given by the Moser–de Bruijn sequence, it follows that the nonzero digits of its reciprocal are located in positions 1, 3, 9, 11, ..., given by doubling the numbers in

For instance, the two binary numbers whose nonzero bits are in the same positions as the nonzero digits of the two decimal numbers above are also irrational reciprocals.

Their transcendence can be proven from the fact that the long strings of zeros in their digits allow them to be approximated more accurately by rational numbers than would be allowed by Roth's theorem if they were algebraic numbers, having irrationality measure no less than 3.

whose exponents in the expanded form are given by the Moser–de Bruijn sequence, obeys the functional equations[1][2]

The partial products of the product form of the generating function can be used to generate the convergents of the continued fraction expansion of these numbers themselves, as well as multiples of them.