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:$$j le k cdot r < j + 1 ext{ and } j le m cdot s < j + 1. ,

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

:$$j < k cdot r < j + 1 ext{ and } j < m cdot s < j + 1 ,

which lead to

:$${j over r} < k < {j + 1 over r} ext{ and } {j over s} < m < {j + 1 over s}. ,

Adding these together and using the hypothesis, we get

:$$j < k + m < j + 1 ,

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

:$$k cdot r < j ext{ and } j + 1 le (k + 1) cdot r ext{ and } m cdot s < j ext{ and } j + 1 le (m + 1) cdot s ,.

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

:$$k cdot r < j ext{ and } j + 1 < (k + 1) cdot r ext{ and } m cdot s < j ext{ and } j + 1 < (m + 1) cdot s. ,

Then we get:$$k < {j over r} ext{ and } {j + 1 over r} < k + 1 ext{ and } m < {j over s} ext{ and } {j + 1 over s} < m + 1 ,

Adding corresponding inequalities, we get:$$k + m < j ext{ and } j + 1 < k + m + 2 ,:$$k + m < j < k + m + 1 ,

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 floorof 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