Beatty sequence

Definition

A positive irrational number r generates the Beatty sequence

B r = ⌊ r ⌋ , ⌊ 2 r ⌋ , ⌊ 3 r ⌋ , …

If r > 1 , then s = r / ( r − 1 ) is also a positive irrational number. These two numbers naturally satisfy the equation 1 / r + 1 / s = 1 . The two Beatty sequences they generate,

B r = ( ⌊ n r ⌋ ) n ≥ 1 and B s = ( ⌊ n s ⌋ ) n ≥ 1 ,

form a pair of complementary Beatty sequences. Here, "complementary" means that every positive integer belongs to exactly one of these two sequences.

Examples

For r = the golden mean, we have s = r + 1. In this case, the sequence ( ⌊ n r ⌋ ) , 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, ... (sequence A000201 in the OEIS).

and the complementary sequence ( ⌊ n s ⌋ ) , the upper Wythoff sequence, is

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

These sequences define the optimal strategy for Wythoff's game, and are used in the definition of the Wythoff array

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 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).

And for r = π and s = π/(π - 1) 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).

Notice that any number in the first sequence is lacking in the second, and vice versa.

History

Beatty sequences got their name from the 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. However, even earlier, in 1894 such sequences were briefly mentioned by John W. Strutt (3rd Baron Rayleigh) in the second edition of his book The Theory of Sound.

Rayleigh theorem

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

First proof

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 B r and B 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 numbers i/r ≤ j/r and ⌊ j s / r ⌋ numbers k / s ≤ j / r , so that the position of j / r in the list is j + ⌊ j s / r ⌋ . The equation 1 / r + 1 / s = 1 implies

j + ⌊ j s / r ⌋ = j + ⌊ j ( s − 1 ) ⌋ = ⌊ j s ⌋ .

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

Conclusion: every positive integer (that is, every position in the list) is of the form ⌊ n r ⌋ or of the form ⌊ n s ⌋ , 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

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 lead to

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

m ∈ B r if and only if

where [ x ] 1 denotes the fractional part of x i.e., [ x ] 1 = x − ⌊ x ⌋ .

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

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

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

Relation with Sturmian sequences

The first difference

⌊ ( n + 1 ) r ⌋ − ⌊ n r ⌋

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

Generalizations

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 to three or more Beatty sequences.

Additional reading

Holshouser, Arthur; Reiter, Harold (2001). "A generalization of Beatty's Theorem". Southwest Journal of Pure and Applied Mathematics. 2: 24–29. Archived from the original on 2014-04-19. 

Stolarsky, Kenneth (1976). "Beatty sequences, continued fractions, and certain shift operators". Canadian Mathematical Bulletin. 19 (4): 473–482. doi:10.4153/CMB-1976-071-6. MR 0444558.  Includes many references.