Beatty sequence

From Wikipedia, the free encyclopedia

Suppose r and s are positive irrational numbers satisfying

\frac1r + \frac1s = 1.

Then the sequences ( \lfloor nr \rfloor)_{n\geq 1} and ( \lfloor ns \rfloor)_{n\geq 1} are a pair of complementary Beatty sequences, and each is a Beatty sequence. As Beatty's theorem states, each positive integer belongs to exactly one of the two sequences.

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.

Contents

[edit] 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 \le j/r and \lfloor js/r \rfloor numbers k/s \le j/r, so that the position of j / r in the list is j + \lfloor js/r \rfloor. The equation 1 / r + 1 / s = 1 implies

j + \lfloor js/r \rfloor = j + \lfloor j(s - 1) \rfloor = \lfloor js \rfloor.

Likewise, the position of k / s in the list is \lfloor kr \rfloor.

Conclusion: every positive integer (that is, every position in the list) is of the form \lfloor nr \rfloor or of the form \lfloor ns \rfloor, 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.

[edit] Examples

For r = the golden mean, we have s = r + 1. In this case, the sequence ( \lfloor nr \rfloor), known as the lower Wythoff sequence, is

and the sequence ( \lfloor ns \rfloor), the upper Wythoff sequence, is

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, ... (sequence A001951 in OEIS) and 3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... (sequence A001952 in OEIS).

[edit] Relation with Sturmian sequences

The first difference

\lfloor (n+1)r\rfloor-\lfloor nr\rfloor

of the Beatty sequence associated to the irrational number r is a characteristic Sturmian word over the alphabet \{\lfloor r\rfloor,\lfloor r\rfloor+1\}.

[edit] References

  • Beatty, Samuel (1926). "Problem 3173". American Mathematical Monthly 33 (3): 159. doi:10.2307/2300153.  Solutions by Beatty, A. Ostrowski, J. Hyslop, and A. C. Aitken, vol. 34 (1927), pp. 159-160.
  • Holshouser, Arthur; Reiter, Harold (2001). "A generalization of Beatty’s Theorem". Southwest Journal of Pure and Applied Mathematics 2: 24–29. 
  • Stolarsky, Kenneth (1976). "Beatty sequences, continued fractions, and certain shift operators". Canadian Mathematical Bulletin 19 (4): 473–482. MR0444558.  Includes many references.

[edit] External links

Languages