Beatty sequence

A (homogeneous) Beatty sequence $mathcal\{B\}\_r,$ is a sequence formed by successive positive integer multiples of a positive irrational number $r,$ rounded down to the nearest integer, so that the sequence

:$mathcal\{B\}\_r\; =\; lfloor\; r\; floor,\; lfloor\; 2r\; floor,\; lfloor\; 3r\; floor,...\; =\; (\; lfloor\; nr\; floor)\_\{ngeq\; 1\}$

If $r\; >\; 1\; ,,$ then $s\; =\; r/(r-1),$ is also a positive irrational number. They naturally satisfy:$frac1r\; +\; frac1s\; =\; 1\; ,$

and the sequences :$mathcal\{B\}\_r\; =\; (\; lfloor\; nr\; floor)\_\{ngeq\; 1\}$ and :$mathcal\{B\}\_s\; =\; (\; lfloor\; ns\; floor)\_\{ngeq\; 1\}$ form a "pair of complementary Beatty sequences". As Beatty's theorem states, each positive integer belongs to exactly one of the two sequences.

A more general non-homogeneous Beatty sequence takes the form

:$mathcal\{B\}\_r\; =\; lfloor\; r+p\; floor,\; lfloor\; 2r+p\; floor,\; lfloor\; 3r+p\; floor,...\; =\; (\; lfloor\; nr+p\; floor)\_\{ngeq\; 1\}$

where $p,$ is a real number. For $p=1,$, the complementary non-homogeneous Beatty sequences can be found by making $t\; =\; 1/r,$ so that

:$mathcal\{B\}\_r\; =\; (\; lfloor\; n(r+1)\; floor)\_\{ngeq\; 1\}$ and :$mathcal\{B\}\_t\; =\; (\; lfloor\; n(t+1)\; floor)\_\{ngeq\; 1\}$ will form a pair of complementary Beatty sequences. For other values of $p,$ the procedure for finding complementary sequences is not as straightforward.

Beatty sequences solve a problem posed in the "American Mathematical Monthly" by Samuel Beatty in 1926. It is probably one of the most often cited problems ever posed in the "Monthly". Beatty sequences can also be used to generate Sturmian words.

Beatty's theorem

A pair of complementary Beatty sequences partition the set of positive integers.

Proof: We must show that every positive integer lies in one and only one of the two sequences and shall do so by considering the ordinal positions occupied by all the fractions "j"/"r" and "k"/"s" when they are jointly listed in nondecreasing order for positive integers "j" and "k".

To see that no two of the numbers can occupy the same position (as a single number), suppose to the contrary that $j/r\; =\; k/s$ for some "j" and "k". Then "r"/"s" = "j"/"k", a rational number, but also, $r/s\; =\; r(1\; -\; 1/r)\; =\; r\; -\; 1,$ not a rational number. Therefore no two of the numbers occupy the same position.

For any "j"/"r", there are "j" numbers "i"/"r" ≤ "j"/"r" and $lfloor\; js/r\; floor$ numbers $k/s\; le\; j/r$, so that the position of $j/r$ in the list is $j\; +\; lfloor\; js/r\; floor$. The equation $1/r\; +\; 1/s\; =\; 1$ implies

: $j\; +\; lfloor\; js/r\; floor\; =\; j\; +\; lfloor\; j(s\; -\; 1)\; floor\; =\; lfloor\; js\; floor.$

Likewise, the position of "k"/"s" in the list is $lfloor\; kr\; floor$.

Conclusion: every positive integer (that is, every position in the list) is of the form $lfloor\; nr\; floor$ or of the form $lfloor\; ns\; floor$, but not both.

The converse of the theorem is also true: if p and q are two real numbers such that every positive integer occurs precisely once in the above list, then "p" and "q" are irrational and the sum of their reciprocals is 1.

Alternative proof

Collisions: Suppose that, contrary to the theorem, there are integers "j" > 0 and "k" and "m" such that:$j\; =\; leftlfloor\; \{k\; cdot\; r\}\; ight\; floor\; =\; leftlfloor\; \{m\; cdot\; s\}\; ight\; floor\; ,.$

This is equivalent to the inequalities:

For non-zero "j", the irrationality of "r" and "s" is incompatable with equality, so

:

which lead to

:

Adding these together and using the hypothesis, we get

:

which is impossible (one cannot have an integer between two adjacent integers). Thus the supposition must be false.

Anti-collisions: Suppose that, contrary to the theorem, there are integers "j" > 0 and "k" and "m" such that

:

Since "j" + 1 is non-zero and "r" and "s" are irrational, we can exclude equality, so

:

Then we get:

Adding corresponding inequalities, we get::

which is also impossible. Thus the supposition is false.

Examples

For "r" = the golden mean, we have "s" = "r" + 1. In this case, the sequence $(\; lfloor\; nr\; floor)$, known as the "lower Wythoff sequence", is
* 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... OEIS|id=A000201.

and the sequence $(\; lfloor\; ns\; floor)$, the "upper Wythoff sequence", is
* 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... OEIS|id=A001950.

These sequences define the optimal strategy for Wythoff's game.

As another example, for "r" = √2, we have "s" = 2 + √2. In this case, the sequences are
* 1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... OEIS|id=A001951 and
* 3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... OEIS|id=A001952.

Relation with Sturmian sequences

The first difference

:$lfloor\; (n+1)r\; floor-lfloor\; nr\; floor$of the Beatty sequence associated to the irrational number $r$ is a characteristic Sturmian word over the alphabet $\{lfloor\; r\; floor,lfloor\; r\; floor+1\}$.

References

* cite journal
author = Beatty, Samuel
title = Problem 3173
journal = American Mathematical Monthly
volume = 33
issue = 3
year = 1926
pages = 159
doi = 10.2307/2300153 [http://www.jstor.org/stable/2298716 Solutions] by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159-160.
*
* cite journal
author = Stolarsky, Kenneth
title = Beatty sequences, continued fractions, and certain shift operators
journal = Canadian Mathematical Bulletin
volume = 19
issue = 4
year = 1976
id = MathSciNet | id = 0444558
pages = 473–482 Includes many references.

External links

*
* Alexander Bogomolny, [http://www.cut-the-knot.org/proofs/Beatty.shtml Beatty Sequences] , Cut-the-knot