HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Beatty sequence (or homogeneous Beatty sequence) is the
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s found by taking the
floor A floor is the bottom surface of a room or vehicle. Floors vary from simple dirt in a cave to many layered surfaces made with modern technology. Floors may be stone, wood, bamboo, metal or any other material that can support the expected load ...
of the positive multiples of a positive
irrational number In mathematics, the irrational numbers (from in- prefix assimilated to ir- (negative prefix, privative) + rational) are all the real numbers that are not rational numbers. That is, irrational numbers cannot be expressed as the ratio of two inte ...
. Beatty sequences are named after Samuel Beatty, who wrote about them in 1926. Rayleigh's theorem, named after
Lord Rayleigh John William Strutt, 3rd Baron Rayleigh, (; 12 November 1842 – 30 June 1919) was an English mathematician and physicist who made extensive contributions to science. He spent all of his academic career at the University of Cambridge. A ...
, 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 r that is greater than one generates the Beatty sequence \mathcal_r = \lfloor r \rfloor, \lfloor 2r \rfloor, \lfloor 3r \rfloor,\ldots The two irrational numbers r and s = r/(r-1) naturally satisfy the equation 1/r + 1/s = 1. The two Beatty sequences \mathcal_r and \mathcal_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.


Examples

When r is the
golden ratio In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0, where the Greek letter phi ( ...
r=(1+\sqrt5)/2\approx 1.618, the complementary Beatty sequence is generated by s=r+1=(3+\sqrt5)/2\approx 2.618. In this case, the sequence ( \lfloor nr \rfloor), known as the ''lower Wythoff sequence'', is and the complementary sequence ( \lfloor ns \rfloor), the ''upper Wythoff sequence'', is These sequences define the optimal strategy for
Wythoff's game Wythoff's game is a two-player mathematical subtraction game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile m ...
, and are used in the definition of the
Wythoff array In mathematics, the Wythoff array is an infinite matrix of integers derived from the Fibonacci sequence and named after Dutch mathematician Willem Abraham Wythoff. Every positive integer occurs exactly once in the array, and every integer sequence ...
. As another example, for the
square root of 2 The square root of 2 (approximately 1.4142) is a positive real number that, when multiplied by itself, equals the number 2. It may be written in mathematics as \sqrt or 2^, and is an algebraic number. Technically, it should be called the princip ...
, r=\sqrt2\approx 1.414, s=2+\sqrt2\approx 3.414. In this case, the sequences are For r=\pi\approx 3.142 and s=\pi/(\pi-1)\approx 1.467, the sequences are 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 ''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an e ...
'' 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 John William Strutt, 3rd Baron Rayleigh, (; 12 November 1842 – 30 June 1919) was an English mathematician and physicist who made extensive contributions to science. He spent all of his academic career at the University of Cambridge. A ...
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 r > 1 \,, there exists s > 1 so that the Beatty sequences \mathcal_r and \mathcal_s
partition Partition may refer to: Computing Hardware * Disk partitioning, the division of a hard disk drive * Memory partition, a subdivision of a computer's memory, usually for use by a single job Software * Partition (database), the division of a ...
the
set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
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 \mathcal_r and \mathcal_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 In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ration ...
, 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 \le j/r and \lfloor js/r \rfloor positive integers k such that 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 statement is also true: if ''p'' and ''q'' are two
real numbers In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every real ...
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 = \left\lfloor \right\rfloor = \left\lfloor \right\rfloor \,. This is equivalent to the inequalities j \le k \cdot r < j + 1 \text j \le m \cdot s < j + 1. For non-zero ''j'', the irrationality of ''r'' and ''s'' is incompatible with equality, so j < k \cdot r < j + 1 \text j < m \cdot s < j + 1, which leads to < k < \text < m < . 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 \text j + 1 \le (k + 1) \cdot r \text m \cdot s < j \text 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 \text j + 1 < (k + 1) \cdot r \text m \cdot s < j \text j + 1 < (m + 1) \cdot s. Then we get k < \text < k + 1 \text m < \text < m + 1 Adding corresponding inequalities, we get k + m < j \text j + 1 < k + m + 2 k + m < j < k + m + 1 which is also impossible. Thus the supposition is false.


Properties

A number m belongs to the Beatty sequence \mathcal_r if and only if 1 - \frac < \left \frac \right1 where 1 denotes the fractional part of x i.e., 1 = x - \lfloor x \rfloor. Proof: m \in B_r \Leftrightarrow \exists n, m = \lfloor nr \rfloor \Leftrightarrow m < nr < m + 1 \Leftrightarrow \frac < n < \frac + \frac \Leftrightarrow n - \frac < \frac < n \Leftrightarrow 1 - \frac < \left \frac \right1 Furthermore, m = \left\lfloor \left( \left\lfloor \frac \right\rfloor + 1 \right) r \right\rfloor. Proof: m = \left\lfloor \left( \left\lfloor \frac \right\rfloor + 1 \right) r \right\rfloor \Leftrightarrow m < \left( \left\lfloor \frac \right\rfloor + 1 \right) r < m + 1 \Leftrightarrow \frac < \left\lfloor \frac \right\rfloor + 1 < \frac \Leftrightarrow \left\lfloor \frac \right\rfloor + 1 - \frac < \frac < \left\lfloor \frac \right\rfloor + 1 \Leftrightarrow 1 - \frac < \frac - \left\lfloor \frac \right\rfloor =\left \frac \right1


Relation with Sturmian sequences

The
first difference In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a paramete ...
\lfloor (n+1)r\rfloor-\lfloor nr\rfloor of the Beatty sequence associated with the irrational number r is a characteristic Sturmian word over the alphabet \.


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 r and s satisfy 1/r + 1/s = 1, the sequences ( \lfloor mr \rfloor)_ and ( \lceil ns \rceil -1)_ 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 The Lambek–Moser theorem is a mathematical description of partitions of the natural numbers into two Complement (set theory), complementary sets. For instance, it applies to the partition of numbers into even number, even and odd number, odd, or ...
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 \alpha_1,\ldots,\alpha_n are positive real numbers such that (\lfloor k\alpha_i\rfloor)_ contains all positive integers exactly once, then n\le2. That is, there is no equivalent of Rayleigh's theorem for three or more Beatty sequences.R. L. Graham
On a theorem of Uspensky
''Amer. Math. Monthly'' 70 (1963), pp. 407–409.


References


Further reading

* * Includes many references.


External links

* {{mathworld, title = Beatty Sequence, urlname = BeattySequence *
Alexander Bogomolny Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and M ...

Beatty Sequences
Cut-the-knot Alexander Bogomolny (January 4, 1948 July 7, 2018) was a Soviet-born Israeli-American mathematician. He was Professor Emeritus of Mathematics at the University of Iowa, and formerly research fellow at the Moscow Institute of Electronics and Math ...
Integer sequences Theorems in number theory Diophantine approximation Combinatorics on words Articles containing proofs