Последовательность Битти

В математике однородная последовательность Битти — последовательность целых чисел, найденных путём взятия целой части («пола») положительных кратных положительного иррационального числа. Последовательности Битти названы в честь Сэмюэля Битти, который написал о них в 1926 году. Последовательности Битти также могут быть использованы для генерации штурмианских слов.

Определение последовательности Битти

Последовательность Битти, основанием для которой служит какое-либо положительное иррациональное число, можно задать следующим образом:

{\mathcal {B}}_{r}=\lfloor r\rfloor ,\lfloor 2r\rfloor ,\lfloor 3r\rfloor ,\ldots

В случае если $r>1\,,$ то $s=r/(r-1)$ тоже является положительным иррациональным числом, при этом эти два числа порождают следующую зависимость: ${\frac {1}{r}}+{\frac {1}{s}}=1$ .

Две последовательности Битти, которые они задают, а именно,

{\mathcal {B}}_{r}=(\lfloor nr\rfloor )_{n\geq 1}

и

{\mathcal {B}}_{s}=(\lfloor ns\rfloor )_{n\geq 1}

,

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

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

В случае, где $r=\varphi$ , где $\varphi$ - золотое сечение, имеем $s=r+1$ . В этом случае, последовательность ${\mathcal {B}}_{r}={\mathcal {\check {W}}}$ , становится нижней последовательностью Витоффа:

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... последовательность A000201 в OEIS.

Комплементарной последовательностью ${\mathcal {B}}_{s}$ , является последовательность ${\widehat {\mathcal {W}}}$ - верхняя последовательность Витоффа:

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... последовательность A001950 в OEIS.

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

1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... последовательность A001951 в OEIS и
3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... последовательность A001952 в OEIS.

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

3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ... последовательность A022844 в OEIS и
1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, ... последовательность A054386 в OEIS.

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

История

Последовательность Битти получила свое название от задачи, поставленной в Американском математическом ежемесячнике по Самуэлем Битти в 1926 году[1][2]. Это, вероятно, одна из наиболее часто цитируемых проблем, когда-либо поставленных в данном журнале. Однако даже раньше, в 1894 году, такие последовательности были кратко упомянуты Джоном В. Струттом (3-й барон Рэлея) во втором издании его книги «Теория звука».[3]

Теорема Рэлея о последовательности Битти (теорема Битти)

Теорема Рэлея, названная в честь лорда Рэлея, утверждает, что дополнение последовательности Битти, состоящее из положительных целых чисел, которые не находятся в последовательности, само по себе является последовательностью Битти, порожденной другим иррациональным числом.[3]

Всегда существует $s>1$ , такое, что последовательности ${\mathcal {B}}_{r},\ {\mathcal {B}}_{s}$ разбивают множество $\mathbb {Z} ^{+}$ на множества натуральных чисел ${\mathcal {N}}_{1}...{\mathcal {N}}_{i}$ , такие, что каждый элемент этого множества принадлежит ровно к одной из двух последовательностей.

Первое доказательство

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

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

Для любой дроби ${\frac {j}{r}}$ , существует ровно $j$ чисел ${\frac {i}{r}}\leq {\frac {j}{r}}$ и ровно $\lfloor js/r\rfloor$ чисел ${\frac {k}{s}}\leq {\frac {j}{r}}$ , так что позиция дроби ${\frac {j}{r}}$ в своеобразном массиве будет $j+\lfloor js/r\rfloor$ . Уравнение ${\frac {1}{r}}+{\frac {1}{s}}=1$ превращается в следующее:

j+\lfloor js/r\rfloor =j+\lfloor j(s-1)\rfloor =\lfloor js\rfloor .

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

Вывод: каждое положительное целое число (то есть каждая позиция в списке) имеет вид $\lfloor nr\rfloor$ или $\lfloor ns\rfloor$ , но не оба одновременно. Обратное утверждение также верно: если $p,q\in \mathbb {R}$ , так что каждое положительное целое число встречается ровно один раз в приведенном выше списке, то $p,q\in \mathbb {I$ .

Список литературы

Beatty, Samuel;. Problem 3173 (англ.) // American Mathematical Monthly : journal. — 1926. — Vol. 33, no. 3. — P. 159. — doi:10.2307/2300153.
S. Beatty; A. Ostrowski; J. Hyslop; A. C. Aitken. Solutions to Problem 3173 (англ.) // American Mathematical Monthly : journal. — 1927. — Vol. 34, no. 3. — P. 159—160. — doi:10.2307/2298716. — .
John William Strutt, 3rd Baron Rayleigh. The Theory of Sound. — Second. — Macmillan, 1894. — Т. 1. — С. 123.

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

Holshouser, Arthur; Reiter, Harold. A generalization of Beatty's Theorem // Southwest Journal of Pure and Applied Mathematics. — 2001. — Т. 2. — С. 24—29. Архивировано 19 апреля 2014 года.
Stolarsky, Kenneth. Beatty sequences, continued fractions, and certain shift operators (англ.) // Canadian Mathematical Bulletin : journal. — 1976. — Vol. 19, no. 4. — P. 473—482. — doi:10.4153/CMB-1976-071-6.

Ссылки

Weisstein, Eric W. Beatty Sequence (англ.) на сайте Wolfram MathWorld.
Alexander Bogomolny, Beatty Sequences, Cut-the-knot

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Beatty, Samuel;. Problem 3173 (англ.) // American Mathematical Monthly : journal. — 1926. — Vol. 33, no. 3. — P. 159. — doi:10.2307/2300153.

[2] S. Beatty; A. Ostrowski; J. Hyslop; A. C. Aitken. Solutions to Problem 3173 (англ.) // American Mathematical Monthly : journal. — 1927. — Vol. 34, no. 3. — P. 159—160. — doi:10.2307/2298716. — .

[Strutt1894-3] John William Strutt, 3rd Baron Rayleigh. The Theory of Sound. — Second. — Macmillan, 1894. — Т. 1. — С. 123.