Beatty sequence

In mathematics, a Beatty sequence (or homogeneous Beatty sequence) is the sequence of integers found by taking the floor of the positive multiples of an irrational number that is greater than one.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 10 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In mathematics, a Beatty sequence (or homogeneous Beatty sequence) is the sequence of integers found by taking the floor of the positive multiples of an irrational number that is greater than one. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926.

Rayleigh's theorem, named after Lord Rayleigh, states that the complement of a Beatty sequence, consisting of the positive integers that are not in the sequence, is itself a Beatty sequence generated by a different irrational number.

Beatty sequences can also be used to generate Sturmian words.

Definition

edit edit source

Any irrational number r that is greater than one generates the Beatty sequence ℬr={⌊r⌋,⌊2r⌋,⌊3r⌋,…} The two irrational numbers r and s=r/(r−1) naturally satisfy the equation 1/r+1/s=1. The two Beatty sequences ℬr and ℬs that they generate form a pair of complementary Beatty sequences. Here, "complementary" means that every positive integer belongs to exactly one of these two sequences.[1]

Examples

edit edit source

When r is the golden ratio r=(1+5)/2≈1.618, the sequence of integer multiples of r have the approximate values

1.618, 3.236, 4.854, 6.472, 8.090, 9.708, ...

Rounding these numbers down to integers gives the sequence (⌊nr⌋), known as the lower Wythoff sequence, which is

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... (sequence A000201 in the OEIS).

In this case, the complementary Beatty sequence is generated by s=rr−1=(1+5)/2(−1+5)/2=3+52≈2.618. Its integer multiples have the approximate values

2.618, 5.236, 7.854, 10.472, 13.090, 15.708, ...

Rounding these values down to integers (⌊ns⌋) produces the upper Wythoff sequence,

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... (sequence A001950 in the OEIS).

Every positive integer is in exactly one of these two sequences. These sequences define the optimal strategy for Wythoff's game,[1] and are used in the definition of the Wythoff array.[2]

As another example, for the square root of 2, r=2≈1.414, and s=2/(2−1)=2+2≈3.414. 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 the OEIS), and 3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... (sequence A001952 in the OEIS).

For r=π≈3.142 and s=π/(π−1)≈1.467, the sequences are

3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ... (sequence A022844 in the OEIS), and 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, ... (sequence A054386 in the OEIS).

Any number in the first sequence is absent in the second, and vice versa.[1]

History

edit edit source

Beatty sequences got their name from the problem posed in The American Mathematical Monthly by Samuel Beatty in 1926.[3][4] However, even earlier, in 1894 such sequences were briefly mentioned by Lord Rayleigh in the second edition of his book The Theory of Sound.[5]

Rayleigh theorem

edit edit source

Rayleigh's theorem (also known as Beatty's theorem) states that given an irrational number r>1, there exists s>1 so that the Beatty sequences ℬr and ℬs partition the set of positive integers: each positive integer belongs to exactly one of the two sequences.[5]

First proof

edit edit source

Given r>1, let s=r/(r−1). We must show that every positive integer lies in one and only one of the two sequences ℬr and ℬs. We 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 positive integers i such that i/r≤j/r and ⌊js/r⌋ positive integers k such that k/s≤j/r, so that the position of j/r in the list is j+⌊js/r⌋. The equation 1/r+1/s=1 implies j+⌊js/r⌋=j+⌊j(s−1)⌋=⌊js⌋.

Likewise, the position of k/s in the list is ⌊kr⌋.

Conclusion: every positive integer (that is, every position in the list) is of the form ⌊nr⌋ or of the form ⌊ns⌋, but not both. The converse statement 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.

Second proof

edit edit source

Collisions: Suppose that, contrary to the theorem, there are integers j > 0 and k and m such that j=⌊k⋅r⌋=⌊m⋅s⌋. This is equivalent to the inequalities j≤k⋅r<j+1 and j≤m⋅s<j+1.

For non-zero j, the irrationality of r and s is incompatible with equality, so j<k⋅r<j+1 and j<m⋅s<j+1, which leads to jr<k<j+1r and js<m<j+1s.

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⋅r<j and j+1≤(k+1)⋅r and m⋅s<j and j+1≤(m+1)⋅s.

Since j + 1 is non-zero and r and s are irrational, we can exclude equality, so k⋅r<j and j+1<(k+1)⋅r and m⋅s<j and j+1<(m+1)⋅s.

Then we get k<jr and j+1r<k+1 and m<js and j+1s<m+1

Adding corresponding inequalities, we get k+m<j and j+1<k+m+2 k+m<j<k+m+1

which is also impossible. Thus the supposition is false.

Properties

edit edit source

A number m belongs to the Beatty sequence ℬr if and only if 1−1r<[mr]1 where [x]1 denotes the fractional part of x i.e., [x]1=x−⌊x⌋.

Proof: m∈Br ⇔∃n,m=⌊nr⌋ ⇔m<nr<m+1 ⇔mr<n<mr+1r ⇔n−1r<mr<n ⇔1−1r<[mr]1

Furthermore, m=⌊(⌊mr⌋+1)r⌋.

Proof: m=⌊(⌊mr⌋+1)r⌋ ⇔m<(⌊mr⌋+1)r<m+1 ⇔mr<⌊mr⌋+1<m+1r ⇔⌊mr⌋+1−1r<mr<⌊mr⌋+1 ⇔1−1r<mr−⌊mr⌋=[mr]1

Relation with Sturmian sequences

edit edit source

The first difference ⌊(n+1)r⌋−⌊nr⌋ of the Beatty sequence associated with the irrational number r is a characteristic Sturmian word over the alphabet {⌊r⌋,⌊r⌋+1}.

Generalizations

edit edit source

If slightly modified, the Rayleigh's theorem can be generalized to positive real numbers (not necessarily irrational) and negative integers as well: if positive real numbers r and s satisfy 1/r+1/s=1, the sequences (⌊mr⌋)m∈ℤ and (⌈ns⌉−1)n∈ℤ form a partition of integers. For example, the white and black keys of a piano keyboard are distributed as such sequences for r=12/7 and s=12/5.

The Lambek–Moser theorem generalizes the Rayleigh theorem and shows that more general pairs of sequences defined from an integer function and its inverse have the same property of partitioning the integers.

Uspensky's theorem states that, if α1,…,αn are positive real numbers such that (⌊kαi⌋)k,i≥1 contains all positive integers exactly once, then n≤2. That is, there is no equivalent of Rayleigh's theorem for three or more Beatty sequences.[6][7]

References

edit edit source
  1. ^ a b c Gardner, Martin (March 1977). "Mathematical Games: Cornering a queen leads unexpectedly into corners of the theory of numbers". Scientific American. 236 (3): 131–141. JSTOR 24953943. Wikipedia revision 1328951712, retrieved 2026-11-18
  2. ^ Morrison, D. R. (1980). "A Stolarsky array of Wythoff pairs". A Collection of Manuscripts Related to the Fibonacci Sequence (PDF). Santa Clara, California: The Fibonacci Association. pp. 134–136. Wikipedia revision 1328951712, retrieved 2026-11-18
  3. ^ Beatty, Samuel (1926). "Problem 3173". American Mathematical Monthly. 33 (3): 159. doi:10.2307/2300153. JSTOR 2300153. Wikipedia revision 1328951712, retrieved 2026-11-18
  4. ^ S. Beatty; A. Ostrowski; J. Hyslop; A. C. Aitken (1927). "Solutions to Problem 3173". American Mathematical Monthly. 34 (3): 159–160. doi:10.2307/2298716. JSTOR 2298716. Wikipedia revision 1328951712, retrieved 2026-11-18
  5. ^ a b John William Strutt, 3rd Baron Rayleigh (1894). The Theory of Sound. Vol. 1 (Second ed.). Macmillan. p. 123.{{cite book}}: CS1 maint: numeric names: authors list (link) Wikipedia revision 1328951712, retrieved 2026-11-18
  6. ^ J. V. Uspensky, On a problem arising out of the theory of a certain game, Amer. Math. Monthly 34 (1927), pp. 516–521. Wikipedia revision 1328951712, retrieved 2026-11-18
  7. ^ R. L. Graham, On a theorem of Uspensky, Amer. Math. Monthly 70 (1963), pp. 407–409. Wikipedia revision 1328951712, retrieved 2026-11-18

Further reading

edit edit source edit edit source

Text derived from https://en.wikipedia.org/w/index.php?oldid=1328951712 under CC BY-SA 4.0; modifications have been made.