Beatty sequence

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Beatty (Fahrenheit 451) — Captain Beatty is a fictional character from Fahrenheit 451 , by Ray Bradbury. He is captain of the protagonist, Guy Montag s, fire house. While firemen in Fahrenheit 451 burn books, and Beatty is dedicated to his work, he is also very well read …   Wikipedia

  • Bruce W. Beatty — CM, CD, FRHSC is a Canadian graphic designer best known as being chiefly responsible for designing the emblems of the Canadian Honours System, starting with the badge of the Order of Canada in 1967. The emblem is the shape of a snowflake just as… …   Wikipedia

  • Montage sequence — A montage sequence is a technique in film editing in which a series of short shots is edited into a sequence to condense narrative. It is usually used to advance the story as a whole (often to suggest the passage of time), rather than to create… …   Wikipedia

  • Sturmian word — In mathematics, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite word. Contents 1 Definition 2 Discussion 3 History 4 Re …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Wythoff's game — is a two player mathematical game of strategy, played with two piles of counters. Players take turns removing counters from one or both piles; in the latter case, the numbers of counters removed from each pile must be equal. The game ends when… …   Wikipedia

  • Целая часть — График функции «пол» (целая часть числа) …   Википедия

  • biblical literature — Introduction       four bodies of written works: the Old Testament writings according to the Hebrew canon; intertestamental works, including the Old Testament Apocrypha; the New Testament writings; and the New Testament Apocrypha.       The Old… …   Universalium

  • Diatessaron — For the musical interval, see perfect fourth. Arabic Diatessaron, Translated by Abul Faraj Al Tayyeb from Syriac to Arabic, 11th Century The Diatessaron (c 160 175) is the most prominent Gospel harmony created by Tatian, an early Christian… …   Wikipedia

  • West Side Story (film) — Infobox Film name = West Side Story image size = 215px caption = film poster by Saul Bass director = Jerome Robbinscite book last= Munden first= Kenneth W. others= title= The asshole Film Institute Catalog of Motion Pictures Produced in the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”