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, or whose base-4 representations consist of the digits 0 and 1. The Moser–de Bruijn numbers in this sequence grow in proportion to the square numbers. They are the squares for a modified form of arithmetic without carrying. The difference of two Moser–de Bruijn numbers, multiplied by two, is never square. Every natural number can be formed in a unique way as the sum of a Moser–de Bruijn number and twice a Moser–de Bruijn number. 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. A simple 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 2-regular sequence.
Definition and examples 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
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 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. The numbers in the sequence can also be described as 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. The hexadecimal representation of these numbers contains only the digits 0, 1, 4, 5. For instance, 69 = 10114 = 4516. Equivalently, they are the numbers whose binary and negabinary representations are equal. Because there are no two consecutive nonzeros in their binary representations, the Moser–de Bruijn sequence forms a subsequence of the fibbinary numbers.
Growth rate and differences
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 {\displaystyle n} is proportional to n {\displaystyle {\sqrt {n}}} , a fact which is also true of the square numbers. More precisely, the number oscillates between n {\displaystyle {\sqrt {n}}} (for numbers of the form n = 4 k {\displaystyle n=4^{k}} ) and 3 n {\displaystyle {\sqrt {3n}}} (for n ∼ 4 k / 3 {\displaystyle n\sim 4^{k}/3} ). 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. 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 {\displaystyle b} numbers. When applied to the base b = 2 {\displaystyle 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.
… excerpt ends here. Continue reading the full article.
