Moser–de Bruijn sequence

The addition table for ${\displaystyle x+2y}$ where $x$ and $y$ both belong to the Moser–de Bruijn sequence, and the Z-order curve that connects the sums in numerical order

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

0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, ... (sequence A000695 in the OEIS)

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

Binary and related representations

Another definition of the Moser–de Bruijn sequence 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;^[1] for instance, 69 = 1011₄. Equivalently, they are the numbers whose binary and negabinary representations are equal.^[1][2]

Plot of the number of sequence elements up to $n$ divided by ${\sqrt {n}}$, on a logarithmic horizontal scale

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 $n$ is proportional to ${\sqrt {n}}$,^[3] 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.^[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-$b$ numbers.^[5] When applied to the base $b=2$, 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.

Unique representation as sums

The Moser–de Bruijn sequence obeys a property similar to that of a Sidon sequence: the sums ${\displaystyle x+2y}$, where $x$ and $y$ both belong to the Moser–de Bruijn sequence, are all unique. No two of these sums have the same value. Moreover, any integer $n$ can be represented as such a sum. To find the sum that represents $n$, compute ${\displaystyle x=n\ \&\ \mathrm {0x55555555} }$, the bitwise Boolean and of $n$ with a binary value (expressed here in hexadecimal) that has ones in all of its even positions, and set ${\displaystyle y=(n-x)/2}$.^[1][6]

This property, that all integers have a unique expression as ${\displaystyle x+2y}$, uniquely defines the Moser–de Bruijn sequence, and is the reason that this sequence was originally studied by Moser (1962).^[7] de Bruijn (1964) found infinitely many linear expressions like ${\displaystyle x+2y}$ that, when $x$ and $y$ both belong to the Moser–de Bruijn sequence, uniquely represent all integers.^[8][9]

Z-order curve and successor formula

Decomposing a number $n$ into ${\displaystyle n=x+2y}$, and then applying to $x$ and $y$ an order-preserving map from the Moser–de Bruijn sequence to the integers (by replacing the powers of four in each number by the corresponding powers of two) gives a bijection from non-negative integers to ordered pairs of non-negative 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. This can be done as follows. If $x$ is an element of the sequence, then the next member after $x$ can be obtained by filling in the bits in odd positions of the binary representation of $x$ by ones, adding one to the result, and then masking off the filled-in bits. Filling the bits and adding one can be combined into a single addition operation. That is, the next member is the number given by the formula

${\displaystyle (x+{\textrm {0xaaaaaaab}})\ \&\ {\textrm {0x55555555}}}$.^[1][6][10]

The two hexadecimal constants appearing in this formula can be interpreted as the 2-adic numbers $1/3$ and $-1/3$, respectively.^[1]

Subtraction game

Golomb (1966) investigated a game, analogous to subtract a square, based on this sequence. In Golomb's game, two players take turns removing coins from a pile of $n$ coins. In each move, a player may remove any number of coins that belongs to the Moser–de Bruijn sequence. Removing any other number of coins is not allowed. The winner is the player who removes the last coin. As Golomb observes, the "cold" positions of this game (the ones in which the player who is about to move is losing) are exactly the positions of the form ${\displaystyle 2y}$ where $y$ belongs to the Moser–de Bruijn sequence. A winning strategy for playing this game is to decompose the current number of coins, $n$, into ${\displaystyle x+2y}$ where $x$ and $y$ both belong to the Moser–de Bruijn sequence, and then (if $x$ is nonzero) to remove $x$ coins, leaving a cold position to the other player. If $x$ is zero, this strategy is not possible, and there is no winning move.^[3]

Decimal reciprocals

The Moser–de Bruijn sequence forms the basis of an example of an irrational number $x$ with the unusual property that the decimal representations of $x$ and $1/x$ can both be written simply and explicitly. Let $E$ denote the Moser–de Bruijn sequence itself, and ${\displaystyle 2E}$ denote the numbers in this sequence multiplied by two: ${\displaystyle \{0,2,8,10,\dots \}}$. Then for

${\displaystyle x=3\sum _{e\in E}10^{-e}=3.300330000000000330033\dots ,}$

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 in the positions given by ${\displaystyle 2E}$:

${\displaystyle {\frac {1}{x}}=3\sum _{e\in 2E}10^{-e-1}=0.30300000303\dots \ .}$^[11][12]

Similar examples also work in other bases. 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.^[13] These binary and decimal numbers, and the numbers defined in the same way for any other base by repeating a single nonzero digit in the positions given by the Moser–de Bruijn sequence, are transcendental numbers. 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.^[12]

Generating function

The generating function

${\displaystyle F(x)=\prod _{i=0}^{\infty }(1+x^{4^{i}})=1+x+x^{4}+x^{5}+x^{16}+x^{17}+\cdots ,}$

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

${\displaystyle F(x)F(x^{2})={\frac {1}{1-x}}}$^[1][2]

and

${\displaystyle F(x)=(1+x)F(x^{4}).}$^[14]

For example, this function can be used to describe the two decimal reciprocals given above: one is ${\displaystyle 3F(1/10)}$ and the other is ${\displaystyle {\tfrac {3}{10}}F(1/100)}$. The fact that they are reciprocal is an instance of the first of the two functional equations. 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.^[11]

Recurrence and regularity

The Moser–de Bruijn sequence obeys a recurrence relation that allows the nth value of the sequence, $S(n)$ (starting at ${\displaystyle S(0)=0}$) to be determined from the value at position $\lfloor n/2\rfloor$:

${\displaystyle S(2n)=4S(n)}$

${\displaystyle S(2n+1)=4S(n)+1}$

Iterating this recurrence allows any subsequence of the form ${\displaystyle S(2^{i}n+j)}$ to be expressed as a linear function of the original sequence, meaning that the Moser–de Bruijn sequence is a 2-regular sequence.^[15]

See also

• Cantor set, a fractal defined similarly using base-3 representations

Notes

1. "Sloane's A000695 : Moser-de Bruijn sequence". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
2. Arndt, Jörg (2011), Matters Computational: Ideas, Algorithms, Source Code (PDF), Springer, pp. 59, 750.
3. Golomb, Solomon W. (1966), "A mathematical investigation of games of "take-away"", Journal of Combinatorial Theory, 1 (4): 443–458, doi:10.1016/S0021-9800(66)80016-9, MR 0209015.
4. Applegate, David; LeBrun, Marc; Sloane, N. J. A. (2011), "Dismal arithmetic" (PDF), Journal of Integer Sequences, 14 (9): Article 11.9.8, 34, arXiv:1107.1130 [math.NT], Bibcode:2011arXiv1107.1130A, MR 2859992.
5. Ruzsa, I. Z. (1984), "Difference sets without squares", Periodica Mathematica Hungarica, 15 (3): 205–209, doi:10.1007/BF02454169, MR 756185.
6. The constants in this formula are expressed in hexadecimal and based on a 32-bit word size. The same bit pattern should be extended or reduced in the obvious way to handle other word sizes.
7. Moser, Leo (1962), "An application of generating series", Mathematics Magazine, 35 (1): 37–38, JSTOR 2689100, MR 1571147.
8. de Bruijn, N. G. (1964), "Some direct decompositions of the set of integers", Mathematics of Computation, 18: 537–546, MR 0167447.
9. Eigen, S. J.; Ito, Y.; Prasad, V. S. (2004), "Universally bad integers and the 2-adics", Journal of Number Theory, 107 (2): 322–334, doi:10.1016/j.jnt.2004.04.001, MR 2072392.
10. Thiyagalingam, Jeyarajan; Beckmann, Olav; Kelly, Paul H. J. (September 2006), "Is Morton layout competitive for large two-dimensional arrays yet?" (PDF), Concurrency and Computation: Practice and Experience, 18 (11): 1509–1539, doi:10.1002/cpe.v18:11.
11. van der Poorten, A. J. (1993), "Continued fractions of formal power series" (PDF), Advances in number theory (Kingston, ON, 1991), Oxford Sci. Publ., Oxford Univ. Press, New York, pp. 453–466, MR 1368441.
12. Blanchard, André; Mendès France, Michel (1982), "Symétrie et transcendance", Bulletin des Sciences Mathématiques, 106 (3): 325–335, MR 680277. As cited by van der Poorten (1993).
13. Bailey, David H.; Borwein, Jonathan M.; Crandall, Richard E.; Pomerance, Carl (2004), "On the binary expansions of algebraic numbers", Journal de Théorie des Nombres de Bordeaux, 16 (3): 487–518, MR 2144954. See in particular the discussion following Theorem 4.2.
14. Lehmer, D. H.; Mahler, K.; van der Poorten, A. J. (1986), "Integers with digits 0 or 1", Mathematics of Computation, 46 (174): 683–689, doi:10.2307/2008006, MR 829638.
15. Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-regular sequences", Theoretical Computer Science, 98 (2): 163–197, doi:10.1016/0304-3975(92)90001-V, MR 1166363. Example 13, p. 188.

External links

• Weisstein, Eric W. "Moser-de Bruijn Sequence". MathWorld.