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

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

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

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

${\mathcal{B}}_r=\lfloor <!--\; \lfloor \; -->r\rfloor <!--\; \rfloor \; -->,\lfloor <!--\; \lfloor \; -->2r\rfloor <!--\; \rfloor \; -->,\lfloor <!--\; \lfloor \; -->3r\rfloor <!--\; \rfloor \; -->,\dots <!--\; \dots \; -->$${\mathcal {B}}_{r}=\lfloor r\rfloor ,\lfloor 2r\rfloor ,\lfloor 3r\rfloor ,\ldots$ 

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

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

${\mathcal{B}}_r=(\lfloor <!--\; \lfloor \; -->nr\rfloor <!--\; \rfloor \; -->{)}_{n\ge <!--\; \ge \; -->1}$${\mathcal {B}}_{r}=(\lfloor nr\rfloor )_{n\geq 1}$  и

${\mathcal{B}}_s=(\lfloor <!--\; \lfloor \; -->ns\rfloor <!--\; \rfloor \; -->{)}_{n\ge <!--\; \ge \; -->1}$${\mathcal {B}}_{s}=(\lfloor ns\rfloor )_{n\geq 1}$ ,

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

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

В случае, где $r=\mathrm{\phi <!--\; \phi \; -->}$$r=\varphi$ , где $\mathrm{\phi <!--\; \phi \; -->}$$\varphi$  - золотое сечение, имеем $s=r+1$$s=r+1$ . В этом случае, последовательность ${\mathcal{B}}_r=\stackrel{\mathcal{ˇ<!--\; ˇ\; -->}}{\mathcal{W}}$${\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$${\mathcal {B}}_{s}$ , является последовательность $\stackrel{^<!--\; ^\; -->}{\mathcal{W}}$${\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}$$r={\sqrt {2}}$ , имеем $s=2+\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=\mathrm{\pi <!--\; \pi \; -->}$$r=\pi$  и $s=\frac{\mathrm{\pi <!--\; \pi \; -->}}{\mathrm{\pi <!--\; \pi \; -->}-<!--\; -\; -->1}$$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 году. Это, вероятно, одна из наиболее часто цитируемых проблем, когда-либо поставленных в данном журнале. Однако даже раньше, в 1894 году, такие последовательности были кратко упомянуты Джоном В. Струттом (3-й барон Рэлея) во втором издании его книги «Теория звука».

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

Не следует путать с одноимённой теоремой Рэлея о точке перегиба.

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

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

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

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

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

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

$j+\lfloor <!--\; \lfloor \; -->js/r\rfloor <!--\; \rfloor \; -->=j+\lfloor <!--\; \lfloor \; -->j(s-<!--\; -\; -->1)\rfloor <!--\; \rfloor \; -->=\lfloor <!--\; \lfloor \; -->js\rfloor <!--\; \rfloor \; -->$$j+\lfloor js/r\rfloor =j+\lfloor j(s-1)\rfloor =\lfloor js\rfloor$ .

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

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

ОбобщенияПравить

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

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

Теорема Успенского утверждает, что если ${\mathrm{\alpha <!--\; \alpha \; -->}}_1,\dots <!--\; \dots \; -->,{\mathrm{\alpha <!--\; \alpha \; -->}}_n$$\alpha _{1},\ldots ,\alpha _{n}$  положительные действительные числа, такие как $(\lfloor <!--\; \lfloor \; -->k{\mathrm{\alpha <!--\; \alpha \; -->}}_i\rfloor <!--\; \rfloor \; -->{)}_{k,i\ge <!--\; \ge \; -->1}$$(\lfloor k\alpha _{i}\rfloor )_{k,i\geq 1}$ , содержат все положительные целые числа ровно один раз, тогда $n\le <!--\; \le \; -->2.$$n\leq 2.$  То есть не существует эквивалента теоремы Рэлея для трех или более последовательностей Битти.

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

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

• 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