Последовательность Битти
В математике однородная последовательность Битти — последовательность целых чисел, найденных путём взятия целой части («пола») положительных кратных положительных иррациональных чисел. Последовательности Битти названы в честь Сэмюэля Битти, написавшего о них в 1926 году. Последовательности Битти также могут быть использованы для генерации штурмианских слов.
Определение последовательности Битти
Последовательность Битти, основанием для которой служит какое-либо положительное иррациональное число, можно задать следующим образом:
B r = ⌊ r ⌋ , ⌊ 2 r ⌋ , ⌊ 3 r ⌋ , … {displaystyle {mathcal {B}}_{r}=lfloor r floor ,lfloor 2r floor ,lfloor 3r floor ,ldots }В случае, если r > 1 , {displaystyle r>1,,} то s = r / ( r − 1 ) {displaystyle s=r/(r-1)} тоже является положительным иррациональным числом. При этом эти два числа порождают следующую зависимость: 1 r + 1 s = 1 {displaystyle {frac {1}{r}}+{frac {1}{s}}=1} .
Две последовательности Битти, которые они задают, а именно,
B r = ( ⌊ n r ⌋ ) n ≥ 1 {displaystyle {mathcal {B}}_{r}=(lfloor nr floor )_{ngeq 1}} и B s = ( ⌊ n s ⌋ ) n ≥ 1 {displaystyle {mathcal {B}}_{s}=(lfloor ns floor )_{ngeq 1}} ,образуют пару комплементарных последовательностей Битти. Здесь слово «комплементарный» означает, что каждое положительное целое число принадлежит ровно к одной из этих двух последовательностей.
Примеры последовательностей Битти
В случае, где r = φ {displaystyle r=varphi } , где φ {displaystyle varphi } - золотое сечение, имеем s = r + 1 {displaystyle s=r+1} . В этом случае, последовательность B r = W ˇ {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.
Комплементарной последовательностью B s {displaystyle {mathcal {B}}_{s}} , является последовательность W ^ {displaystyle {widehat {mathcal {W}}}} - верхняя последовательность Витоффа:
- 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... последовательность A001950 в OEIS.
С другой стороны, для r = 2 {displaystyle r={sqrt {2}}} , имеем s = 2 + 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.
Для r = π {displaystyle r=pi } и s = π π − 1 {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 году. Это, вероятно, одна из наиболее часто цитируемых проблем, когда-либо поставленных в данном журнале. Однако даже раньше, в 1894 году, такие последовательности были кратко упомянуты Джоном В. Струттом (3-й барон Рэлея) во втором издании его книги «Теория звука».
Теорема Рэлея о последовательности Битти (теорема Битти)
Теорема Рэлея, названная в честь лорда Рэлея, утверждает, что дополнение последовательности Битти, состоящее из положительных целых чисел, которые не находятся в последовательности, само по себе является последовательностью Битти, порожденной другим иррациональным числом.
Первое доказательство
Считая, что r > 1 , {displaystyle r>1,,} пусть s = r / ( r − 1 ) {displaystyle s=r/(r-1)} . Докажем, что ∀ x ∈ Z + : x ∈ ! B r | s {displaystyle forall xin mathbb {Z} ^{+}:x {overset {!}{in }} {mathcal {B}}_{r|s}} , где операнд "|" является операндом "или". Мы сделаем это, рассматривая порядковые позиции, занимаемые всеми дробями j r {displaystyle {frac {j}{r}}} и k s {displaystyle {frac {k}{s}}} , совместно перечисленными в неубывающем порядке для j , k ∈ Z + {displaystyle j,kin mathbb {Z} ^{+}}
Чтобы увидеть, что никакие два числа не могут занимать одну и ту же позицию (как одно число), предположим, что, наоборот, ∃ j , k ∈ Z + : j r = k s {displaystyle exists j,kin mathbb {Z} ^{+}:{frac {j}{r}}={frac {k}{s}}} , тогда дроби r s = j k ∈ Z {displaystyle {frac {r}{s}}={frac {j}{k}}in mathbb {Z} } , но, в то же время, r s = r ( 1 − 1 r ) = r − 1 {displaystyle {frac {r}{s}}=r(1-{frac {1}{r}})=r-1} , и эта дробь не принадлежит множеству целых чисел. Поэтому никакие два числа не занимают одну и ту же позицию.
Для любой дроби j r {displaystyle {frac {j}{r}}} , существует ровно j {displaystyle j} чисел i r ≤ j r {displaystyle {frac {i}{r}}leq {frac {j}{r}}} и ровно ⌊ j s / r ⌋ {displaystyle lfloor js/r floor } чисел k s ≤ j r {displaystyle {frac {k}{s}}leq {frac {j}{r}}} , так что позиция дроби j r {displaystyle {frac {j}{r}}} в своеобразном массиве будет j + ⌊ j s / r ⌋ {displaystyle j+lfloor js/r floor } . Уравнение 1 r + 1 s = 1 {displaystyle {frac {1}{r}}+{frac {1}{s}}=1} превращается в следующее:
j + ⌊ j s / r ⌋ = j + ⌊ j ( s − 1 ) ⌋ = ⌊ j s ⌋ . {displaystyle j+lfloor js/r floor =j+lfloor j(s-1) floor =lfloor js floor .}Аналогично, позиция дроби k / s {displaystyle k/s} в массиве будет ⌊ k r ⌋ {displaystyle lfloor kr floor } .
Вывод: каждое положительное целое число (то есть каждая позиция в списке) имеет вид ⌊ n r ⌋ {displaystyle lfloor nr floor } или ⌊ n s ⌋ {displaystyle lfloor ns floor } , но не оба одновременно. Обратное утверждение также верно: если p , q ∈ R {displaystyle p,qin mathbb {R} } , так что каждое положительное целое число встречается ровно один раз в приведенном выше списке, то p , q ∈ I ; 1 p + 1 q = 1 {displaystyle p,qin mathbb {I} ; {frac {1}{p}}+{frac {1}{q}}=1} .
Обобщения
Если немного её изменить, то теорема Рэлея может быть обобщена на положительные действительные числа (не обязательно иррациональные), а также на отрицательные целые числа: если положительные действительные числа удовлетворяют r {displaystyle r} и s {displaystyle s} удовлетворяют 1 / r + 1 / s = 1 {displaystyle 1/r+1/s=1} , последовательности ( ⌊ m r ⌋ ) m ∈ Z {displaystyle (lfloor mr floor )_{min mathbb {Z} }} и ( ⌈ n s ⌉ − 1 ) n ∈ Z {displaystyle (lceil ns ceil -1)_{nin mathbb {Z} }} образуют раздел целых чисел. Например, белые и черные клавиши клавиатуры фортепиано распределяются в виде таких последовательностей для r = 12 / 7 {displaystyle r=12/7} и s = 12 / 5 {displaystyle s=12/5} .
Теорема Ламбека-Мозера обобщает теорему Рэлея и демонстрирует, что более общие пары последовательностей, определяемые из целочисленной функции и её обратной функции, обладают тем же свойством разбивать целые числа.
Теорема Успенского утверждает, что если α 1 , … , α n {displaystyle alpha _{1},ldots ,alpha _{n}} положительные действительные числа такие, как ( ⌊ k α i ⌋ ) k , i ≥ 1 {displaystyle (lfloor kalpha _{i} floor )_{k,igeq 1}} содержит все положительные целые числа ровно один раз, тогда n ≤ 2. {displaystyle nleq 2.} То есть не существует эквивалента теоремы Рэлея для трех или более последовательностей Битти.