Beatty sequence

Beatty sequence (Redirected from Beatty's theorem) Aller à la navigation Aller à la recherche En mathématiques, 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.

Contenu 1 Définition 2 Exemples 3 Histoire 4 Rayleigh theorem 4.1 Première preuve 4.2 Deuxième preuve 5 Propriétés 5.1 Relation with Sturmian sequences 6 Généralisations 7 Références 8 Lectures complémentaires 9 External links Definition A positive irrational number {style d'affichage r} generates the Beatty sequence {style d'affichage {mathématique {B}}_{r}=lfloor rrfloor ,lfloor 2rrfloor ,lfloor 3rrfloor ,ldots } Si {displaystyle r>1,,} alors {displaystyle s=r/(r-1)} is also a positive irrational number. These two numbers naturally satisfy the equation {displaystyle 1/r+1/s=1} . The two Beatty sequences they generate, {style d'affichage {mathématique {B}}_{r}=(lfloor nrrfloor )_{ngq 1}} et {style d'affichage {mathématique {B}}_{s}=(lfloor nsrfloor )_{ngq 1}} , form a pair of complementary Beatty sequences. Ici, "complementary" means that every positive integer belongs to exactly one of these two sequences.

Examples When r is the golden mean, we have s = r + 1. Dans ce cas, la séquence {style d'affichage (lfloor nrrfloor )} , known as the lower Wythoff sequence, est 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 {style d'affichage (lfloor nsrfloor )} , the upper Wythoff sequence, est 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. Dans ce cas, 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) et 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) et 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, et vice versa.

History Beatty sequences got their name from the problem posed in the American Mathematical Monthly by Samuel Beatty in 1926.[1][2] It is probably one of the most often cited problems ever posed in the Monthly. Cependant, even earlier, dans 1894 such sequences were briefly mentioned by John W. Strutt (3rd Baron Rayleigh) in the second edition of his book The Theory of Sound.[3] Rayleigh theorem The Rayleigh theorem (also known as Beatty's theorem) states that given an irrational number {displaystyle r>1,,} il existe {displaystyle s>1} so that the Beatty sequences {style d'affichage {mathématique {B}}_{r}} et {style d'affichage {mathématique {B}}_{s}} partition the set of positive integers: each positive integer belongs to exactly one of the two sequences.[3] First proof Given {displaystyle r>1,,} laisser {displaystyle s=r/(r-1)} . We must show that every positive integer lies in one and only one of the two sequences {style d'affichage {mathématique {B}}_{r}} et {style d'affichage {mathématique {B}}_{s}} . We shall do so by considering the ordinal positions occupied by all the fractions {displaystyle j/r} et {displaystyle 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 {displaystyle j/r=k/s} for some j and k. Alors {displaystyle r/s} = {displaystyle j/k} , a rational number, but also, {displaystyle r/s=r(1-1/r)=r-1,} not a rational number. Par conséquent, no two of the numbers occupy the same position.

Pour toute {displaystyle j/r} , il y a {displaystyle j} positive integers {style d'affichage i} tel que {displaystyle i/rleq j/r} et {displaystyle lfloor js/rrfloor } positive integers {style d'affichage k} tel que {displaystyle k/sleq j/r} , so that the position of {displaystyle j/r} in the list is {displaystyle j+lfloor js/rrfloor } . The equation {displaystyle 1/r+1/s=1} implique {displaystyle j+lfloor js/rrfloor =j+lfloor j(s-1)rfloor =lfloor jsrfloor .} De même, the position of {displaystyle k/s} in the list is {displaystyle lfloor krrfloor } .

Conclusion: every positive integer (C'est, every position in the list) is of the form {displaystyle lfloor nrrfloor }  or of the form {displaystyle lfloor nsrfloor } , 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: Supposer que, contrary to the theorem, there are integers j > 0 and k and m such that {displaystyle j=leftlfloor {kcdot r}rightrfloor =leftlfloor {mcdot s}rightrfloor ,.} This is equivalent to the inequalities {displaystyle jleq kcdot r 0 and k and m such that {displaystyle kcdot rt s.} Then we get {style d'affichage k<{j over r}{text{ and }}{j+1 over r}Adding corresponding inequalities, on a {displaystyle k+mdisplaystyle Leftrightarrow n-{frac {1}{r}}<{frac {m}{r}}displaystyle Leftrightarrow 1-{frac {1}{r}}

Si vous voulez connaître d'autres articles similaires à Beatty sequence vous pouvez visiter la catégorie Diophantine approximation.