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

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

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

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

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

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

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

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

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

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

В случае, где ${\displaystyle r=\varphi }$, где ${\displaystyle \varphi }$ - золотое сечение, имеем ${\displaystyle s=r+1}$. В этом случае, последовательность ${\displaystyle {\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.

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

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

С другой стороны, для ${\displaystyle r={\sqrt {2}}}$, имеем ${\displaystyle 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.

Для ${\displaystyle r=\pi }$ и ${\displaystyle 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].

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

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

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

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

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

${\displaystyle j+\lfloor {\frac {js}{r}}\rfloor =j+\lfloor j(s-1)\rfloor =\lfloor js\rfloor }$.

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

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

Обобщения

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

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

Теорема Успенского утверждает, что если ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$ положительные действительные числа, такие как ${\displaystyle (\lfloor k\alpha _{i}\rfloor )_{k,i\geq 1}}$, содержат все положительные целые числа ровно один раз, тогда ${\displaystyle n\leq 2.}$ То есть не существует эквивалента теоремы Рэлея для трех или более последовательностей Битти^[4][5].

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

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

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

• 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

Эта страница в последний раз была отредактирована 29 октября 2023 в 20:31.