View source for Moser–De Bruijn sequence

[[File:Moser–de Bruijn addition.svg|thumb|upright=1.35|The addition table for <math>x+2y</math> where <math>x</math> and <math>y</math> both belong to the Moser–De Bruijn sequence, and the [[Z-order curve|Z-order curve]] that connects the sums in numerical order]]
In [[Number theory|number theory]], the '''Moser–De Bruijn sequence''' is an [[Integer sequence|integer sequence]] named after [[Biography:Leo Moser|Leo Moser]] and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4, or equivalently the numbers whose binary representations are nonzero only in even positions.

They grow in proportion to the [[Square number|square number]]s, and are the squares for a modified form of arithmetic without [[Carry (arithmetic)|carrying]]. No two doubled sequence members differ by a square, and every non-negative integer has a unique representation as the sum of a sequence member and a doubled sequence member. This decomposition into sums can be used to define a [[Bijection|bijection]] between the integers and pairs of integers, to define coordinates for the [[Z-order curve]], and to construct inverse pairs of [[Transcendental number|transcendental number]]s with simple decimal representations.

A simple [[Recurrence relation|recurrence relation]] allows values of the Moser–De Bruijn sequence to be calculated from earlier values, and can be used to prove that the Moser–De Bruijn sequence is a [[K-regular sequence|2-regular sequence]].

==Examples==
The Moser–De Bruijn sequence begins{{r|oeis}}
{{Block indent|left=1.6|0, 1, 4, 5, 16, 17, 20, 21, 64, 65, 68, 69, 80, 81, 84, 85, 256, ...}}
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 is that it is the ordered sequence of numbers whose binary representation has nonzero digits only in the even positions. For instance, 69 belongs to the sequence, because its binary representation 1000101<sub>2</sub> has nonzero digits in the positions for 2<sup>6</sup>, 2<sup>2</sup>, and 2<sup>0</sup>, all of which have even exponents. The numbers in the sequence can also be described as the numbers whose [[Quaternary numeral system|base-4 representation]] uses only the digits 0 or 1.{{r|oeis}} 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. The [[Hexadecimal|hexadecimal]] representation of these numbers contains only the digits 0, 1, 4, 5. For instance, 69 = 1011<sub>4</sub> = 45<sub>16</sub>. Equivalently, they are the numbers whose binary and negabinary representations are equal.{{r|oeis|arndt}} Because there are no two consecutive nonzeros in their binary representations, the Moser–De Bruijn sequence forms a subsequence of the [[Fibbinary number|fibbinary number]]s.

[[File:Moser–de Bruijn counts.svg|thumb|upright=1.65|Plot of the number of sequence elements up to <math>n</math> divided by <math>\sqrt n</math>, 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 number|square number]]s. The number of elements in the Moser–De Bruijn sequence that are below any given threshold <math>n</math> is proportional to <math>\sqrt n</math>,{{r|golomb}}
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 [[Carry (arithmetic)|carrying]] on binary numbers, in which the addition and multiplication of single bits are respectively the [[Exclusive or|exclusive or]] and [[Logical conjunction|logical conjunction]] operations.{{r|als}}

In connection with the [[Furstenberg–Sárközy theorem]] on sequences of numbers with no square difference, [[Biography:Imre Z. Ruzsa|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-<math>b</math> numbers.{{r|ruzsa}} When applied to the base <math>b=2</math>, 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 <math>x+2y</math>, where <math>x</math> and <math>y</math> both belong to the Moser–De Bruijn sequence, are all unique. No two of these sums have the same value. Moreover, every integer <math>n</math> can be represented as a sum <math>x+2y</math>, where <math>x</math> and <math>y</math> both belong to the Moser–De Bruijn sequence. To find the sum that represents <math>n</math>, compute <math>x=n\ \&\ \mathrm{0x55555555}</math>, the [[Bitwise operation|bitwise Boolean and]] of <math>n</math> with a binary value (expressed here in [[Hexadecimal|hexadecimal]]) that has ones in all of its even positions, and {{nowrap|set <math>y=(n-x)/2</math>.{{r|oeis|32bit}}}}

The Moser–De Bruijn sequence is the only sequence with this property, that all integers have a unique expression as <math>x+2y</math>. It is for this reason that the sequence was originally studied by {{harvtxt|Moser|1962}}.{{r|moser}} Extending the property, {{harvtxt|De Bruijn|1964}} found infinitely many other linear expressions like <math>x+2y</math> that, when <math>x</math> and <math>y</math> both belong to the Moser–De Bruijn sequence, uniquely represent all integers.{{r|debruijn|eip}}

==Z-order curve and successor formula==
Decomposing a number <math>n</math> into <math>n=x+2y</math>, and then applying to <math>x</math> and <math>y</math> 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|bijection]] from non-negative integers to [[Ordered pair|ordered pair]]s 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]].{{r|oeis|morton}}

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 <math>x</math> is an element of the sequence, then the next member after <math>x</math> can be obtained by filling in the bits in odd positions of the binary representation of <math>x</math> 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{{r|oeis|32bit|morton}}
<math display=block>\displaystyle (x + \textrm{0xaaaaaaab})\ \&\ \textrm{0x55555555}.</math>
The two hexadecimal constants appearing in this formula can be interpreted as the [[P-adic number|2-adic numbers]] <math>1/3</math> and <math>-1/3</math>, respectively.{{r|oeis}}

==Subtraction game==
{{harvtxt|Golomb|1966}} investigated a [[Subtraction game|subtraction game]], analogous to [[Subtract a square|subtract a square]], based on this sequence. In Golomb's game, two players take turns removing coins from a pile of <math>n</math> 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 <math>2y</math> where <math>y</math> belongs to the Moser–De Bruijn sequence. A winning strategy for playing this game is to decompose the current number of coins, <math>n</math>, into <math>x+2y</math> where <math>x</math> and <math>y</math> both belong to the Moser–De Bruijn sequence, and then (if <math>x</math> is nonzero) to remove <math>x</math> coins, leaving a cold position to the other player. If <math>x</math> is zero, this strategy is not possible, and there is no winning move.{{r|golomb}}

==Decimal reciprocals==
The Moser–De Bruijn sequence forms the basis of an example of an [[Irrational number|irrational number]] <math>x</math> with the unusual property that the decimal representations of <math>x</math> and <math>1/x</math> can both be written simply and explicitly. Let <math>E</math> denote the Moser–De Bruijn sequence itself. Then for
<math display=block>x = 3\sum_{n\in E} 10^{-n} = 3.300330000000000330033\dots,</math>
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 {{nowrap|1, 3, 9, 11, ...,}} given by doubling the numbers in <math>E</math> and adding one to all of them:{{r|vdp|bmf}}
<math display=block>\frac{1}{x}=3\sum_{n\in E} 10^{-2n-1} = 0.30300000303\dots\ .</math>

Alternatively, one can write:
<math display=block>\displaystyle\left(\sum_{n\in E}10^{-n}\right)\left(\sum_{n\in E}10^{-2n}\right)=\frac{10}{9}.</math>

Similar examples also work in other bases. For instance, the two [[Binary number|binary number]]s whose nonzero bits are in the same positions as the nonzero digits of the two decimal numbers above are also irrational reciprocals.{{r|bbcp}} 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 number|transcendental number]]s. Their transcendence can be proven from the fact that the long strings of zeros in their digits allow them to be [[Diophantine approximation|approximated]] more accurately by [[Rational number|rational number]]s than would be allowed by [[Roth's theorem]] if they were [[Algebraic number|algebraic number]]s.{{r|bmf}}

==Generating function==
The [[Generating function|generating function]]
<math display=block>F(x)=\prod_{i=0}^{\infty}(1+x^{4^i})=1+x+x^4+x^5+x^{16}+x^{17}+\cdots,</math>
whose exponents in the expanded form are given by the Moser–De Bruijn sequence,
obeys the [[Functional equation|functional equation]]s{{r|oeis|arndt}}
<math display=block>F(x)F(x^2)=\frac{1}{1-x}</math>
and{{r|lmp}}
<math display=block>F(x)=(1+x)F(x^4).</math>
For example, this function can be used to describe the two decimal reciprocals given above: one is <math>3 F(1/10)</math> and the other is <math>\tfrac{3}{10} F(1/100)</math>. The fact that they are reciprocals 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|continued fraction]] expansion of these numbers themselves, as well as multiples of them.{{r|vdp}}

==Recurrence and regularity==
The Moser–De Bruijn sequence obeys a [[Recurrence relation|recurrence relation]] that allows the {{mvar|n}}th value of the sequence, <math>S(n)</math> (starting at <math>S(0)=0</math>) to be determined from the value at {{nowrap|position <math>\lfloor n/2\rfloor</math>:}}
<math display=block>
\begin{align}
S(2n)&=4S(n)\\
S(2n+1)&=4S(n)+1
\end{align}
</math>
Iterating this recurrence allows any subsequence of the form <math>S(2^i n + j)</math> to be expressed as a linear function of the original sequence, meaning that the Moser–De Bruijn sequence is a [[K-regular sequence|2-regular sequence]].{{r|as}}

==See also==
*[[Stanley sequence]] and [[Cantor set]], sets defined similarly using the base-3 representations of their elements

==Notes==
{{reflist|refs=

<ref name=32bit>The constants in this formula are expressed in [[Hexadecimal|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.</ref>

<ref name=als>{{citation
 | last2 = LeBrun | first2 = Marc
 | issue = 9
 | journal = [[Journal of Integer Sequences]]
 | mr = 2859992
 | page = Article 11.9.8, 34
 | title = Dismal arithmetic
 | url = http://emis.ams.org/journals/JIS/VOL14/Sloane/carry2.pdf
 | volume = 14
 | year = 2011| bibcode = 2011arXiv1107.1130A
 | arxiv = 1107.1130
 }}.</ref>

<ref name="arndt">{{citation|last=Arndt|first=Jörg|title=Matters Computational: Ideas, Algorithms, Source Code|publisher=Springer|year=2011|url=http://jjj.de/fxt/fxtbook.pdf|pages=59, 750}}.</ref>

<ref name=as>{{citation
 | last1 = Allouche | first1 = Jean-Paul
 | doi = 10.1016/0304-3975(92)90001-V
 | issue = 2
 | journal = Theoretical Computer Science
 | mr = 1166363
 | pages = 163–197
 | title = The ring of {{mvar|k}}-regular sequences
 | volume = 98
 | year = 1992| doi-access = free
 }}. Example 13, p.&nbsp;188.</ref>

<ref name=bbcp>{{citation
 | issue = 3
 | journal = Journal de Théorie des Nombres de Bordeaux
 | mr = 2144954
 | pages = 487–518
 | title = On the binary expansions of algebraic numbers
 | url = http://jtnb.cedram.org/item?id=JTNB_2004__16_3_487_0
 | volume = 16
 | year = 2004 | doi=10.5802/jtnb.457}}. See in particular the discussion following Theorem 4.2.</ref>

<ref name=bmf>{{citation
 | last1 = Blanchard | first1 = André
 | last2 = Mendès France | first2 = Michel
 | issue = 3
 | journal = Bulletin des Sciences Mathématiques
 | mr = 680277
 | pages = 325–335
 | title = Symétrie et transcendance
 | volume = 106
 | year = 1982}}. As cited by {{harvtxt|van der Poorten|1993}}.</ref>

<ref name=debruijn>{{citation
 | journal = [[Mathematics of Computation]]
 | mr = 0167447
 | pages = 537–546
 | title = Some direct decompositions of the set of integers
 | volume = 18
 | year = 1964
 | doi=10.2307/2002940| doi-access = free
 }}.</ref>

<ref name=eip>{{citation
 | last1 = Eigen | first1 = S. J.
 | last2 = Ito | first2 = Y.
 | last3 = Prasad | first3 = V. S.
 | doi = 10.1016/j.jnt.2004.04.001
 | issue = 2
 | journal = Journal of Number Theory
 | mr = 2072392
 | pages = 322–334
 | title = Universally bad integers and the 2-adics
 | volume = 107
 | year = 2004| doi-access = free
 }}.</ref>

<ref name=golomb>{{citation
 | doi = 10.1016/S0021-9800(66)80016-9
 | journal = Journal of Combinatorial Theory
 | mr = 0209015
 | pages = 443–458
 | title = A mathematical investigation of games of "take-away"
 | volume = 1
 | issue = 4 | year = 1966| doi-access = free
 }}.</ref>

<ref name=lmp>{{citation
 | doi = 10.2307/2008006
 | issue = 174
 | journal = [[Mathematics of Computation]]
 | mr = 829638
 | pages = 683–689
 | title = Integers with digits 0 or 1
 | volume = 46
 | year = 1986}}.</ref>

<ref name=morton>{{citation
 | last1 = Thiyagalingam
 | first1 = Jeyarajan
 | last2 = Beckmann
 | first2 = Olav
 | last3 = Kelly
 | first3 = Paul H. J.
 | date = September 2006
 | doi = 10.1002/cpe.v18:11
 | issue = 11
 | journal = Concurrency and Computation: Practice and Experience
 | pages = 1509–1539
 | title = Is Morton layout competitive for large two-dimensional arrays yet?
 | url = http://www.doc.ic.ac.uk/~ob3/Publications/CandCPEMorton2004.pdf
 | volume = 18
 | access-date = 2016-11-18
 | archive-url = https://web.archive.org/web/20170329104300/http://www.doc.ic.ac.uk/~ob3/Publications/CandCPEMorton2004.pdf
 | archive-date = 2017-03-29
 | url-status = dead
 }}.</ref>

<ref name=moser>{{citation
 | issue = 1
 | journal = Mathematics Magazine
 | jstor = 2689100
 | mr = 1571147
 | pages = 37–38
 | title = An application of generating series
 | volume = 35
 | year = 1962}}.</ref>

<ref name=oeis>{{Cite OEIS|A000695|name=Moser–De Bruijn sequence|mode=cs2}}</ref>

<ref name=ruzsa>{{citation
 | doi = 10.1007/BF02454169
 | issue = 3
 | journal = Periodica Mathematica Hungarica
 | mr = 756185
 | pages = 205–209
 | title = Difference sets without squares
 | volume = 15
 | year = 1984}}.</ref>

<ref name=vdp>{{citation
 | contribution = Continued fractions of formal power series
 | contribution-url = http://web.williams.edu/Mathematics/sjmiller/public_html/book/papers/vdp/Poorten_ContFracsOfFormalPowerSeries.pdf
 | mr = 1368441
 | pages = 453–466
 | publisher = Oxford Univ. Press, New York
 | series = Oxford Sci. Publ.
 | title = Advances in number theory (Kingston, ON, 1991)
 | year = 1993}}.</ref>

}}

==External links==
*{{mathworld|id=Moser-deBruijnSequence|title=Moser–De Bruijn Sequence|mode=cs2}}

{{DEFAULTSORT:Moser-De Bruijn sequence}}
[[Category:Integer sequences]]
[[Category:Binary arithmetic]]

{{Sourceattribution|Moser–De Bruijn sequence|1}}