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

Последовательность Сильвестра — , в которой каждый очереднойчлен равен произведению предыдущих членов плюс единица. Первые несколькочленов последовательности:

 , \ldots .
 Названа по имени Джеймса Сильвестра, который первым исследовал её в 1880году. Значения её членов растут как , а сумма обратных членов образуетряд долей единицы, который сходится к 1 быстрее, чем любой другой ряддробей единицы с тем же числом членов. Рекуррентное соотношение, котороеопределяет члены последовательности, позволяет числам впоследовательности быть разложенными на множители проще, нежели другиечисла того же порядка, но ввиду очень быстрого роста членов ряда полноеразложение на простые множители известно только для некоторых членовэтой последовательности. Значения, полученные с использованием этойпоследовательности, используются для образования конечного представления1 в виде египетской дроби, и как источник данных для .

Формальныеопределения


 Формально последовательность Сильвестра можно определить формулой:

sn=1+i=0n1si.
 равно 1, так что s0=2.
 Другим образом можно определить последовательность с помощьюрекуррентного соотношения:

si=si1(si11)+1, где s0=2.
 Эквивалентность определений доказывается прямой индукцией.

Общая формула иасимптотики


 Члены последовательности Сильвестра растут со скоростью . В частности,можно показать, что:

sn=E2n+1+12,
 где число E приблизительно равно . Эта формула приводит к следующемуалгоритму:

 s0 — ближайшее целое к E2;s1 — ближайшее целое к E4;s2 — ближайшее целое к E8; дляsn, берём E2, возводим вквадрат n раз и берём ближайшее целое.
 Этот алгоритм был бы приемлемым, если бы мы имели лучший путь вычисленияE вместо вычисления чисел sn с последующимвычислением квадратных корней.
 Рост элементов последовательности Сильвестра со скоростью двойнойэкспоненты совершенно не удивителен, если сравнивать споследовательностью чисел Ферма Fn. ЧислаФерма часто задаются по формуле двойной экспоненты 22n+1, но ихможно также задать по формулам умножения, подобным формулампоследовательности Сильвестра:

Fn=2+i=0n1Fi.

Связь с египетскимидробями


 Доли единицы, образованные числами, обратными значениямпоследовательности Сильвестра, образуют бесконечный ряд:

i=01si=12+13+17+143+11807+.
 Частичные суммы этого ряда имеют простую форму

i=0j11si=11sj1=sj2sj1.
 Это можно доказать по индукции или прямо, если заметить, что из рекурсиивытекает

1si11si+11=1si,
 Таким образом, сумма телескопического ряда будет равна

i=0j11si=i=0j1(1si11si+11)=1s011sj1=11sj1.
 Поскольку последовательность частичных сумм(sj−2)/(sj−1)сходятся к единице, весь ряд образует бесконечное представление единицыв виде египетской дроби:

1=12+13+17+143+11807+.
 Можно найти конечные представления единицы в виде египетской дроби любойдлины путём обрывания этого ряда и вычитанием единицы из последнегознаменателя:

1=12+13+16,1=12+13+17+142,1=12+13+17+143+11806,.
 Сумма первых k членов бесконечного ряда даёт ближайшую нижнююоценку единицы k-членными египетскими дробями. Например, первыечетыре члена добавляются к 1805/1806, а потому любая египетская дробь воткрытом интервале (1805/1806,1) требует по меньшей мере пять членов.
 Можно рассматривать последовательность Сильвестра как результат жадногоалгоритма для египетских дробей, который на каждом шаге выбираетнаименьший возможный делитель, оставляющий частичную сумму меньшеединицы. Также члены ряда после первого можно рассматривать как делителичисла 1/2.

Единственность быстрорастущих рядов с рациональнымисуммами


 Как заметил сам Сильвестр, последовательность Сильвестра, похоже,единственная, которая имеет такую скорость роста, при этом сходясь крациональному числу. Эта последовательность показывает пример того, чтоскорость роста двойной экспоненты недостаточна для того, чтобыпоследовательность целых чисел была рациональной последовательностью.
 Из результата Бадеа следует, что если последовательность целых чиселan растёт достаточно быстро, так, что

anan12an1+1,
 и если ряд

A=1ai
 сходится к рациональному числу A, то для всех n, начиная снекоторого места, эта последовательность должна удовлетворятьрекуррентному соотношению

an=an12an1+1,
 что можно использовать для определения последовательности Сильвестра.
 Эрдёш высказал гипотезу, что в результатах такого типа границунеравенства роста последовательности можно заменить на более слабоеусловие

limnanan12=1.

Делимость иразложение


 Если i \textless j, из определения следует, чтоsj ≡ 1 (modsi). Таким образом, любые два членапоследовательности Сильвестра взаимно просты. Последовательность можноиспользовать для доказательства бесконечности числа простых чисел,поскольку любое простое число может делить максимум одно число впоследовательности. Никакой простой множитель числа в последовательностине может быть сравним с 5 (mod 6), и последовательность можноиспользовать для доказательства, что существует бесконечно много простыхчисел, сравнимых с 7 (mod 12).
 Много остаётся неизвестного о разложении на множители членовпоследовательности Сильвестра. Например, неизвестно, являются ли всечлены последовательности свободными от квадратов, хотя все известныечлены таковыми являются.
 Как пишет Варди , легко установить, какой из членов последовательностиСильвестра (если такой есть) делится на простое число p —просто вычисляем вычеты членов последовательности по модулю pсогласно рекуррентной формуле, пока не встретится ноль (по модулюp) или встретится такой же остаток. Используя эту технику, Вардинашёл, что 1166 из первого миллиона простых чисел являются делителямичисел Сильвестра, и ни один квадрат этих простых чисел не делит числаСильвестра. Множество простых чисел, которые могут оказаться делителямичленов ряда Сильвестра, имеет плотность ноль во множестве всех простыхчисел. Более того, согласно Джонсу число таких простых меньших xравно O(π(x)/logloglogx).
 В следующей таблице приведены известные разложения этих чисел, (заисключением первых четырёх, являющихся простыми):
nМножители sn
413 × 139
53263443, простое
6547 × 607 × 1033 × 31051
729881 × 67003 × 9119521 × 6212157481
85295435634831 × 31401519357481261 × 77366930214021991992277
9181 × 1987 × 112374829138729 × 114152531605972711 × 35874380272246624152764569191134894955972560447869169859142453622851
102287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
1173 × C416
122589377038614498251653 × 2872413602289671035947763837 × C785
1352387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
1413999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
1517881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16128551 × C13335
17635263 × 1286773 × 21269959 × C26661
1850201023123 × 139263586549 × 60466397701555612333765567 × C53313
19775608719589345260583891023073879169 × C106685
20352867 × 6210298470888313 × C213419
21387347773 × 1620516511 × C426863
2291798039513 × C853750

 Здесь Pn и Cn обозначают простые и составные числа сn десятичными цифрами.

Приложения


 Бойер, Галики и Коллар использовали свойства последовательностиСильвестра для определения большого числа , имеющих дифференциальнуютопологию сфер нечётных размерностей или экзотических сфер. Онипоказали, что число различных сасакианских эйнштейновских метрик натопологической сфере размерности 2n − 1 по меньшей мерепропорционально sn, а потому растёт соскоростью двойной экспоненты (от n).
 Как пишут Галамбос и Вогингер , Браун и Лианг использовали значения,полученные из последовательности Сильвестра, для построения примеровнижней границы для алгоритмов упаковки в контейнеры. Зайден и Вогингерподобным же образом использовали последовательность для нижней границыпроизводительности двумерного алгоритма раскроя.
 Задача Знама касается множеств чисел, таких, что каждое число вмножестве делит, но не равно произведению всех остальных множеств плюсединица. Без условия эквивалентности значения последовательностиСильвестра решают эту задачу. Если это условие ставится, имеется другоерешение, получаемое из рекуррентного соотношения, подобного определениюпоследовательности Сильвестра. Решения задачи Знама имеют приложения кклассификации особых точек поверхностей (Brenton, Hill 1988) и теории .
 Куртис описывает приложение ближайшего приближения к единицеk-членными суммами долей единицы к нижней границе числа делителейлюбого совершенного числа, а Мюллер использует то же самое свойство длячисла некоторых групп.