Просмотр кода страницы Последовательность Битти

{{плохой перевод|en|Beatty sequence|дата=2020-06-01}}
{{Нет ссылок|дата=2020-05-30}}

'''Однородная последовательность Битти''' — последовательность [[Целые числа|целых чисел]], являющихся [[Целая часть|целыми частями]] от положительных чисел, кратных положительному [[Иррациональное число|иррациональному числу]]. Последовательности Битти названы в честь {{iw|Битти, Сэмюэл (математик)|Сэмюэля Битти|en|Samuel Beatty (mathematician)}}, написавшего о них в [[1926 год|1926 году]]. Последовательности Битти также могут быть использованы для генерации {{iw|Последовательность Штурма|последовательностей Штурма||Sturmian word}}.

== Определение последовательности Битти ==
Последовательность Битти, основанием для которой служит какое-либо положительное [[иррациональное число]] <math>r</math>, можно задать следующим образом:

: <math>\mathcal{B}_r = (\lfloor r \rfloor, \lfloor 2r \rfloor, \lfloor 3r \rfloor,\ldots)</math>

В случае, если <math>r > 1 \,</math>, то <math>s = \frac{r}{r-1}</math> тоже является положительным иррациональным числом, причем две последовательности Битти, которые они задают, а именно,

: <math>\mathcal{B}_r = ( \lfloor nr \rfloor)_{n\geq 1}</math> и
: <math>\mathcal{B}_s = ( \lfloor ns \rfloor)_{n\geq 1}</math>,

образуют пару комплементарных последовательностей Битти. Здесь слово «комплементарный» означает, что каждое положительное целое число принадлежит ровно к одной из этих двух последовательностей.

== Примеры последовательностей Битти ==
В случае, где <math>r=\varphi</math>, где <math>\varphi</math> - [[золотое сечение]], имеем <math>s=r+1</math>. В этом случае, последовательность <math>\mathcal{B}_r=\mathcal{\check{W}}</math>, становится ''[[Последовательности Витхоффа|нижней последовательностью Витхоффа]]:''

* 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... {{OEIS|id=A000201}}.

Комплементарной последовательностью <math>\mathcal{B}_s</math>, является [[последовательность]] <math>\widehat{\mathcal{W}}</math> - [[Последовательности Витхоффа|''верхняя последовательность Витхоффа'']]:

* 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... {{OEIS|id=A001950}}.

С другой стороны, для <math>r=\sqrt{2}</math>, имеем <math>s=2+\sqrt{2}</math>. В этом случае вырождаются следующие последовательности:

* 1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... {{OEIS|id=A001951}} и
* 3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... {{OEIS|id=A001952}}.

Для <math>r=\pi</math> и <math>s=\cfrac{\pi}{\pi-1}</math> вырождаются последовательности

* 3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ... {{OEIS|id=A022844}} и
* 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, ... {{OEIS|id=A054386}}.

Любое число из первой последовательности отсутствует во второй, и наоборот.

== История ==

Последовательность Битти получила свое название от задачи, поставленной в ''[[American Mathematical Monthly|Американском математическом ежемесячнике]]'' Самуэлем Битти в 1926 году<ref>{{статья|заглавие=Problem 3173|ссылка=https://archive.org/details/sim_american-mathematical-monthly_1926-03_33_3/page/159|издание=[[American Mathematical Monthly]]|том=33|номер=3|страницы=159|doi=10.2307/2300153|автор=Beatty, Samuel; <!-- this comment stops Citation bot adding irrelevant authors here-->|год=1926|язык=en|тип=journal}}</ref><ref>{{статья|заглавие=Solutions to Problem 3173|ссылка=https://archive.org/details/sim_american-mathematical-monthly_1927-03_34_3/page/159|издание=[[American Mathematical Monthly]]|том=34|страницы=159—160|doi=10.2307/2298716|jstor=2298716|номер=3|автор=S. Beatty; A. Ostrowski; J. Hyslop; A. C. Aitken|год=1927|язык=en|тип=journal}}</ref>. Это, вероятно, одна из наиболее часто цитируемых проблем, когда-либо поставленных в данном журнале. Однако даже раньше, в 1894 году, такие последовательности были кратко упомянуты [[Стретт, Джон Уильям (лорд Рэлей)|Рэлеем]] во втором издании его книги ''«Теория звука»''<ref name="Strutt1894">{{книга|заглавие=The Theory of Sound|издательство=Macmillan|том=1|издание=Second|год=1894|страницы=123|ссылка=https://books.google.com/books?id=EGQSAAAAIAAJ&pg=PA123|автор=[[Стретт, Джон Уильям (лорд Рэлей)|John William Strutt, 3rd Baron Rayleigh]]}}</ref>.

== Теорема Рэлея о последовательности Битти (теорема Битти) ==
{{не путать|Теорема Рэлея о точке перегиба|одноимённой теоремой Рэлея о точке перегиба}}'''[[Теорема Рэлея (о последовательности Битти)|Теорема Рэлея]]''', названная в честь [[Стретт, Джон Уильям (лорд Рэлей)|лорда Рэлея]], утверждает, что дополнение последовательности Битти, состоящее из положительных целых чисел, которые не находятся в последовательности, само по себе является последовательностью Битти, порожденной другим иррациональным числом<ref name="Strutt1894" />.
{{Теорема|Всегда существует <math>s>1</math>, такое, что последовательности <math>\mathcal{B}_r,\ \mathcal{B}_s</math> разбивают множество <math>\mathbb{Z}^+</math> на множества натуральных чисел <math>\mathcal{N}_1...\mathcal{N}_i</math>, такие, что каждый элемент этого множества принадлежит ровно к одной из двух последовательностей.}}

=== Доказательство ===
Пусть <math>r > 1 \,</math> и <math>s = \frac{r}{r-1}</math>. Докажем, что <math>\forall x\in\mathbb{Z}^+: x\ \overset{!}{\in}\ \mathcal{B}_{r|s} </math> , где операнд "|" является операндом "[[Логические операции|или]]". Мы сделаем это, рассматривая порядковые позиции, занимаемые всеми дробями <math>\frac j r</math> и <math>\frac k s </math>, совместно перечисленными в неубывающем порядке для <math>j,k\in\mathbb{Z}^+</math>.

Чтобы увидеть, что никакие два числа не могут занимать одну и ту же позицию (как одно число), предположим, что, наоборот, <math>\exists j,k\in\mathbb{Z}^+:\frac j r = \frac k s</math>, тогда дроби <math>\frac r s=\frac j k\in\mathbb{Z}</math>, но, в то же время, <math>\frac r s =r(1-\frac 1 r)=r-1</math>, и эта дробь не принадлежит множеству целых чисел. Поэтому никакие два числа не занимают одну и ту же позицию.

Для любой дроби <math>\frac j r</math>, существует ровно <math>j</math> чисел <math>\frac i r \le \frac j r</math> и ровно <math> \lfloor js/r \rfloor</math> чисел <math>\frac k s \le \frac j r</math>, так что позиция дроби <math>\frac j r </math> в своеобразном [[Массив (тип данных)|массиве]] будет <math>j + \lfloor js /r \rfloor</math>. Уравнение <math>\frac 1 r+\frac 1 s=1</math> превращается в следующее:

: <math>j + \lfloor \frac{js}{r} \rfloor = j + \lfloor j(s - 1) \rfloor = \lfloor js \rfloor</math>.

Аналогично, позиция дроби <math>\frac{k}{s}</math> в массиве будет <math>\lfloor kr \rfloor</math>.

Вывод: каждое положительное целое число (то есть каждая позиция в списке) имеет вид <math>\lfloor nr \rfloor</math> или <math>\lfloor ns \rfloor</math>, но не оба одновременно. Обратное утверждение также верно: если <math>p,q\in\mathbb{R}</math>, так что каждое положительное целое число встречается ровно один раз в приведенном выше списке, то <math>p,q\in\mathbb{I};\ \frac 1 p + \frac 1 q =1</math>.{{Дополнить раздел|дата=2020-05-30}}

== Обобщения ==

Если немного её изменить, то [[Теорема Рэлея о точке перегиба|теорема Рэлея]] может быть обобщена на положительные действительные числа (не обязательно иррациональные), а также на отрицательные целые числа: если положительные действительные числа удовлетворяют <math>r</math> и <math>s</math> удовлетворяют <math>1/r + 1/s = 1</math>, последовательности <math>( \lfloor mr \rfloor)_{m \in \mathbb{Z}}</math> и <math>( \lceil ns \rceil -1)_{n \in \mathbb{Z}}</math> образуют раздел целых чисел. Например, белые и черные клавиши клавиатуры фортепиано распределяются в виде таких последовательностей для <math>r = 12/7</math> и <math>s = 12/5</math>.

[[Теорема Ламбека-Мозера]] обобщает теорему Рэлея и демонстрирует, что более общие пары последовательностей, определяемые из целочисленной функции и её обратной функции, обладают тем же свойством разбивать целые числа.

Теорема [[Яков Викторович Успенский|Успенского]] утверждает, что если <math>\alpha_1,\ldots,\alpha_n</math> положительные действительные числа, такие как <math>(\lfloor k\alpha_i\rfloor)_{k,i\ge1}</math>, содержат все положительные целые числа ровно один раз, тогда <math>n\le2.</math> То есть не существует эквивалента теоремы Рэлея для трех или более последовательностей Битти<ref>J. V. Uspensky, On a problem arising out of the theory of a certain game, ''Amer. Math. Monthly'' '''34''' (1927), pp. 516–521.</ref><ref>R. L. Graham, [http://www.math.ucsd.edu/~fan/ron/papers/63_01_uspensky.pdf On a theorem of Uspensky] {{Wayback|url=http://www.math.ucsd.edu/~fan/ron/papers/63_01_uspensky.pdf |date=20210217025721 }}, ''Amer. Math. Monthly'' '''70''' (1963), pp. 407–409.</ref>.

Важными темами в последовательности Битти являются: простые числа и суммы значений арифметических функций.

== Список литературы ==
{{примечания}}

== Литература для дополнительного чтения ==

* {{статья|заглавие=A generalization of Beatty's Theorem|издание=Southwest Journal of Pure and Applied Mathematics|том=2|страницы=24—29|ссылка=https://math.uncc.edu/preprint/2002/generalization-beattys-theorem|archiveurl=https://web.archive.org/web/20140419014134/https://math.uncc.edu/preprint/2002/generalization-beattys-theorem|archivedate=2014-04-19|ref=Holshouser|автор=Holshouser, Arthur; Reiter, Harold|год=2001}}
* {{статья|заглавие=Beatty sequences, continued fractions, and certain shift operators|издание={{Нп3|Canadian Mathematical Bulletin}}|том=19|номер=4|mr=0444558|страницы=473—482|doi=10.4153/CMB-1976-071-6|язык=en|тип=journal|автор=Stolarsky, Kenneth|год=1976}}

== Ссылки ==
* {{mathworld|title=Beatty Sequence|urlname=BeattySequence}}
* Alexander Bogomolny, [http://www.cut-the-knot.org/proofs/Beatty.shtml Beatty Sequences], [[Cut-the-knot]]

[[Категория:Целочисленные последовательности]]
[[Категория:Теоремы теории чисел]]
[[Категория:Диофантовы приближения]]
[[Категория:Комбинаторика слов]]