Английская Википедия:Beatty sequence

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description In mathematics, a Beatty sequence (or homogeneous Beatty sequence) is the sequence of integers found by taking the floor of the positive multiples of a positive irrational number. 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

Any irrational number <math>r</math> that is greater than one generates the Beatty sequence <math display=block>\mathcal{B}_r = \bigl\{ \lfloor r \rfloor, \lfloor 2r \rfloor, \lfloor 3r \rfloor,\ldots \bigr\}</math> The two irrational numbers <math>r</math> and <math>s = r/(r-1)</math> naturally satisfy the equation <math>1/r + 1/s = 1</math>. The two Beatty sequences <math>\mathcal{B}_r</math> and <math>\mathcal{B}_s</math> 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.

Examples

When <math>r</math> is the golden ratio <math>r=(1+\sqrt5)/2\approx 1.618</math>, the complementary Beatty sequence is generated by <math>s=r+1=(3+\sqrt5)/2\approx 2.618</math>. In this case, the sequence <math>( \lfloor nr \rfloor)</math>, known as the lower Wythoff sequence, is Шаблон:Bi and the complementary sequence <math>( \lfloor ns \rfloor)</math>, the upper Wythoff sequence, is Шаблон:Bi These sequences define the optimal strategy for Wythoff's game, and are used in the definition of the Wythoff array.

As another example, for the square root of 2, <math>r=\sqrt2\approx 1.414</math>, <math>s=2+\sqrt2\approx 3.414</math>. In this case, the sequences are Шаблон:Bi Шаблон:Bi For <math>r=\pi\approx 3.142</math> and <math>s=\pi/(\pi-1)\approx 1.467</math>, the sequences are Шаблон:Bi Шаблон:Bi Any number in the first sequence is absent 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 Lord Rayleigh in the second edition of his book The Theory of Sound.

Rayleigh theorem

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

First proof

Given <math>r > 1 \,,</math> let <math>s = r/(r-1)</math>. We must show that every positive integer lies in one and only one of the two sequences <math>\mathcal{B}_r</math> and <math>\mathcal{B}_s</math>. We shall do so by considering the ordinal positions occupied by all the fractions <math>j/r</math> and <math>k/s</math> 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 <math>j/r = k/s</math> for some j and k. Then <math>r/s</math> = <math>j/k</math>, a rational number, but also, <math>r/s = r(1 - 1/r) = r - 1,</math> not a rational number. Therefore, no two of the numbers occupy the same position.

For any <math>j/r</math>, there are <math>j</math> positive integers <math>i</math> such that <math>i/r \le j/r</math> and <math> \lfloor js/r \rfloor</math> positive integers <math>k</math> such that <math>k/s \le j/r</math>, so that the position of <math>j/r</math> in the list is <math>j + \lfloor js/r \rfloor</math>. The equation <math>1/r + 1/s = 1</math> implies <math display=block>j + \lfloor js/r \rfloor = j + \lfloor j(s - 1) \rfloor = \lfloor js \rfloor.</math>

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

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

Шаблон:Em: Suppose that, contrary to the theorem, there are integers j > 0 and k and m such that <math display=block>j = \left\lfloor {k \cdot r} \right\rfloor = \left\lfloor {m \cdot s} \right\rfloor \,.</math> This is equivalent to the inequalities <math display=block>j \le k \cdot r < j + 1 \text{ and } j \le m \cdot s < j + 1. </math>

For non-zero j, the irrationality of r and s is incompatible with equality, so <math display=block>j < k \cdot r < j + 1 \text{ and } j < m \cdot s < j + 1, </math> which leads to <math display=block>{j \over r} < k < {j + 1 \over r} \text{ and } {j \over s} < m < {j + 1 \over s}. </math>

Adding these together and using the hypothesis, we get <math display=block>j < k + m < j + 1 </math> which is impossible (one cannot have an integer between two adjacent integers). Thus the supposition must be false.

Шаблон:Em: Suppose that, contrary to the theorem, there are integers j > 0 and k and m such that <math display=block>k \cdot r < j \text{ and } j + 1 \le (k + 1) \cdot r \text{ and } m \cdot s < j \text{ and } j + 1 \le (m + 1) \cdot s \,.</math>

Since j + 1 is non-zero and r and s are irrational, we can exclude equality, so <math display=block>k \cdot r < j \text{ and } j + 1 < (k + 1) \cdot r \text{ and } m \cdot s < j \text{ and } j + 1 < (m + 1) \cdot s. </math>

Then we get <math display=block>k < {j \over r} \text{ and } {j + 1 \over r} < k + 1 \text{ and } m < {j \over s} \text{ and } {j + 1 \over s} < m + 1 </math>

Adding corresponding inequalities, we get <math display=block>k + m < j \text{ and } j + 1 < k + m + 2 </math> <math display=block>k + m < j < k + m + 1 </math>

which is also impossible. Thus the supposition is false.

Properties

A number <math>m</math> belongs to the Beatty sequence <math>\mathcal{B}_r</math> if and only if <math display=block> 1 - \frac{1}{r} < \left[ \frac{m}{r} \right]_1</math> where <math>[x]_1</math> denotes the fractional part of <math>x</math> i.e., <math>[x]_1 = x - \lfloor x \rfloor</math>.

Proof: <math> m \in B_r </math> <math>\Leftrightarrow \exists n, m = \lfloor nr \rfloor</math> <math>\Leftrightarrow m < nr < m + 1</math> <math>\Leftrightarrow \frac{m}{r} < n < \frac{m}{r} + \frac{1}{r}</math> <math>\Leftrightarrow n - \frac{1}{r} < \frac{m}{r} < n</math> <math>\Leftrightarrow 1 - \frac{1}{r} < \left[ \frac{m}{r} \right]_1</math>

Furthermore, <math>m = \left\lfloor \left( \left\lfloor \frac{m}{r} \right\rfloor + 1 \right) r \right\rfloor</math>.

Proof: <math>m = \left\lfloor \left( \left\lfloor \frac{m}{r} \right\rfloor + 1 \right) r \right\rfloor </math> <math>\Leftrightarrow m < \left( \left\lfloor \frac{m}{r} \right\rfloor + 1 \right) r < m + 1</math> <math>\Leftrightarrow \frac{m}{r} < \left\lfloor \frac{m}{r} \right\rfloor + 1 < \frac{m + 1}{r}</math> <math>\Leftrightarrow \left\lfloor \frac{m}{r} \right\rfloor + 1 - \frac{1}{r} < \frac{m}{r} < \left\lfloor \frac{m}{r} \right\rfloor + 1</math> <math>\Leftrightarrow 1 - \frac{1}{r} < \frac{m}{r} - \left\lfloor \frac{m}{r} \right\rfloor =\left[ \frac{m}{r} \right]_1 </math>

Relation with Sturmian sequences

The first difference <math display=block>\lfloor (n+1)r\rfloor-\lfloor nr\rfloor</math> of the Beatty sequence associated with the irrational number <math>r</math> is a characteristic Sturmian word over the alphabet <math>\{\lfloor r\rfloor,\lfloor r\rfloor+1\}</math>.

Generalizations

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 <math>r</math> and <math>s</math> satisfy <math>1/r + 1/s = 1</math>, the sequences <math>( \lfloor mr \rfloor)_{m \in \mathbb{Z}}</math> and <math>( \lceil ns \rceil -1)_{n \in \mathbb{Z}}</math> form a partition of integers. For example, the white and black keys of a piano keyboard are distributed as such sequences for <math>r = 12/7</math> and <math>s = 12/5</math>.

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 <math>\alpha_1,\ldots,\alpha_n</math> are positive real numbers such that <math>(\lfloor k\alpha_i\rfloor)_{k,i\ge1}</math> contains all positive integers exactly once, then <math>n\le2.</math> That is, there is no equivalent of Rayleigh's theorem for three or more Beatty sequences.

Further reading

• Шаблон:Cite journal
• Шаблон:Cite journal Includes many references.

External links

• Шаблон:Mathworld
• Alexander Bogomolny, Beatty Sequences, Cut-the-knot