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

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

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

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

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

В случае, если $r>1\,$, то $s={\frac {r}{r-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 году. Это, вероятно, одна из наиболее часто цитируемых проблем, когда-либо поставленных в данном журнале. Однако даже раньше, в 1894 году, такие последовательности были кратко упомянуты Рэлеем во втором издании его книги «Теория звука».

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

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

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

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

Доказательство

Пусть $r>1\,$ и $s={\frac {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 {\frac {js}{r}}\rfloor =j+\lfloor j(s-1)\rfloor =\lfloor js\rfloor$.

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

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

Обобщения

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

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

Теорема Успенского утверждает, что если $\alpha _{1},\ldots ,\alpha _{n}$ положительные действительные числа, такие как $(\lfloor k\alpha _{i}\rfloor )_{k,i\geq 1}$, содержат все положительные целые числа ровно один раз, тогда $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