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

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

Графическая демонстрация сходимости суммы 1/2 + 1/3 + 1/7 + 1/43 + … к 1. Каждая строка $k$ квадратов со стороной $1/k$ имеет общую площадь $1/k$, и все квадраты вместе в точности покрывают большой квадрат с площадью 1. Квадраты со стороной 1/1807 или меньше слишком малы, чтобы их увидеть на рисунке, и они не показаны.

2, 3, 7, 43, 1807, 3 263 443, 10 650 056 950 807, 113 423 713 055 421 850 000 000 000, … (последовательность A000058 в OEIS).

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

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

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

$s_{n}=1+\prod _{i=0}^{n-1}s_{i}$.

Произведение элементов пустого множества равно 1, так что $s_{0}=2$.

Другим образом можно определить последовательность с помощью рекуррентного соотношения:

$\displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1$, где $s_{0}=2$.

Эквивалентность определений доказывается прямой индукцией.

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

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

$s_{n}=\left\lfloor E^{2^{n+1}}+{\frac {1}{2}}\right\rfloor ,$

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

s₀ — ближайшее целое к E²; s₁ — ближайшее целое к E⁴; s₂ — ближайшее целое к E⁸; для s_n, берём E², возводим в квадрат n раз и берём ближайшее целое.

Этот алгоритм был бы приемлемым, если бы мы имели лучший путь вычисления E вместо вычисления чисел s_n с последующим вычислением квадратных корней.

Рост элементов последовательности Сильвестра со скоростью двойной экспоненты совершенно не удивителен, если сравнивать с последовательностью чисел Ферма F_n. Числа Ферма часто задаются по формуле двойной экспоненты $2^{2^{n}}+1$, но их можно также задать по формулам умножения, подобным формулам последовательности Сильвестра:

$F_{n}=2+\prod _{i=0}^{n-1}F_{i}.$

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

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

$\sum _{i=0}^{\infty }{\frac {1}{s_{i}}}={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .$

Частичные суммы этого ряда имеют простую форму

$\sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=1-{\frac {1}{s_{j}-1}}={\frac {s_{j}-2}{s_{j}-1}}.$

Это можно доказать по индукции или прямо, если заметить, что из рекурсии вытекает

${\frac {1}{s_{i}-1}}-{\frac {1}{s_{i+1}-1}}={\frac {1}{s_{i}}},$

Таким образом, сумма телескопического ряда будет равна

$\sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=\sum _{i=0}^{j-1}\left({\frac {1}{s_{i}-1}}-{\frac {1}{s_{i+1}-1}}\right)={\frac {1}{s_{0}-1}}-{\frac {1}{s_{j}-1}}=1-{\frac {1}{s_{j}-1}}.$

Поскольку последовательность частичных сумм (s_j−2)/(s_j−1) сходятся к единице, весь ряд образует бесконечное представление единицы в виде египетской дроби:

$1={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .$

Можно найти конечные представления единицы в виде египетской дроби любой длины путём обрывания этого ряда и вычитанием единицы из последнего знаменателя:

$1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{6}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{42}},\quad 1={\tfrac {1}{2}}+{\tfrac {1}{3}}+{\tfrac {1}{7}}+{\tfrac {1}{43}}+{\tfrac {1}{1806}},\quad \dots .$

Сумма первых k членов бесконечного ряда даёт ближайшую нижнюю оценку единицы k-членными египетскими дробями. Например, первые четыре члена добавляются к 1805/1806, а потому любая египетская дробь в открытом интервале (1805/1806,1) требует по меньшей мере пять членов.

Можно рассматривать последовательность Сильвестра как результат жадного алгоритма для египетских дробей, который на каждом шаге выбирает наименьший возможный делитель, оставляющий частичную сумму меньше единицы. Также члены ряда после первого можно рассматривать как делители жадного приближения нечётными числами числа 1/2.

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

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

Из результата Бадеа следует, что если последовательность целых чисел $a_{n}$ растёт достаточно быстро, так, что

$a_{n}\geq a_{n-1}^{2}-a_{n-1}+1,$

и если ряд

$A=\sum {\frac {1}{a_{i}}}$

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

$a_{n}=a_{n-1}^{2}-a_{n-1}+1$,

что можно использовать для определения последовательности Сильвестра.

Эрдёш высказал гипотезу, что в результатах такого типа границу неравенства роста последовательности можно заменить на более слабое условие

$\lim _{n\rightarrow \infty }{\frac {a_{n}}{a_{n-1}^{2}}}=1.$

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

Если i < j, из определения следует, что s_j ≡ 1 (mod s_i). Таким образом, любые два члена последовательности Сильвестра взаимно просты. Последовательность можно использовать для доказательства бесконечности числа простых чисел, поскольку любое простое число может делить максимум одно число в последовательности. Никакой простой множитель числа в последовательности не может быть сравним с 5 (mod 6), и последовательность можно использовать для доказательства, что существует бесконечно много простых чисел, сравнимых с 7 (mod 12).

Нерешённые проблемы математики: Все ли члены последовательности Сильвестра свободны от квадратов?

Много остаётся неизвестного о разложении на множители членов последовательности Сильвестра. Например, неизвестно, являются ли все члены последовательности свободными от квадратов, хотя все члены, для которых известно разложение на простые, таковыми являются.

Как пишет Варди (Vardi 1991), легко установить, какой из членов последовательности Сильвестра (если такой есть) делится на простое число p — просто вычисляем вычеты членов последовательности по модулю p согласно рекуррентной формуле, пока не встретится ноль (по модулю p) или встретится такой же остаток. Используя эту технику, Варди нашёл, что 1166 из первого миллиона простых чисел являются делителями чисел Сильвестра, и ни один квадрат этих простых чисел не делит числа Сильвестра. Множество простых чисел, которые могут оказаться делителями членов ряда Сильвестра, имеет плотность ноль во множестве всех простых чисел. Более того, согласно Джонсу число таких простых меньших x равно $O(\pi (x)/\log \log \log x)$.

В следующей таблице приведены известные разложения этих чисел, (за исключением первых четырёх, являющихся простыми):

n	Множители sn
4	13 × 139
5	3263443, простое
6	547 × 607 × 1033 × 31051
7	29881 × 67003 × 9119521 × 6212157481
8	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × 35874380272246624152764569191134894955972560447869169859142453622851
10	2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
11	73 × C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
14	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
15	17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
18	50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19	775608719589345260583891023073879169 × C106685
20	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

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

Приложения

Бойер, Галики и Коллар (Boyer, Galicki, Kollár 2005) использовали свойства последовательности Сильвестра для определения большого числа сасакианских многообразий Эйнштейна, имеющих дифференциальную топологию сфер нечётных размерностей или экзотических сфер. Они показали, что число различных сасакианских эйнштейновских метрик на топологической сфере размерности 2n − 1 по меньшей мере пропорционально s_n, а потому растёт со скоростью двойной экспоненты (от n).

Как пишут Галамбос и Вогингер (Galambos, Woeginger 1995), Браун (Brown 1979) и Лианг (Liang 1980) использовали значения, полученные из последовательности Сильвестра, для построения примеров нижней границы для онлайновых алгоритмов упаковки в контейнеры. Зайден и Вогингер (Seiden, Woeginger 2005) подобным же образом использовали последовательность для нижней границы производительности двумерного алгоритма раскроя.

Задача Знама касается множеств чисел, таких, что каждое число в множестве делит, но не равно произведению всех остальных множеств плюс единица. Без условия эквивалентности значения последовательности Сильвестра решают эту задачу. Если это условие ставится, имеется другое решение, получаемое из рекуррентного соотношения, подобного определению последовательности Сильвестра. Решения задачи Знама имеют приложения к классификации особых точек поверхностей (Brenton, Hill 1988) и теории недетерминированных конечных автоматов.

Куртис (Curtiss 1922) описывает приложение ближайшего приближения к единице k-членными суммами долей единицы к нижней границе числа делителей любого совершенного числа, а Мюллер (Miller 1919) использует то же самое свойство для нижней границы числа некоторых групп.

См. также

• Константа Каэна
• Простое псевдосовершенное число

Литература

• Catalin Badea. A theorem on irrationality of infinite series and applications // Acta Arithmetica. — 1993. — Т. 63. — С. 313—323.
• Badea, Catalin. On some criteria for irrationality for series of positive rationals: a survey (англ.). — 1995.
• Charles P. Boyer, Krzysztof Galicki, János Kollár. Einstein metrics on spheres // Annals of Mathematics. — 2005. — Т. 162, вып. 1. — С. 557—580. — doi:10.4007/annals.2005.162.557. — arXiv:math.DG/0309408.
• Lawrence Brenton, Richard Hill. On the Diophantine equation 1=Σ1/n_i + 1/Πn_i and a class of homologically trivial complex surface singularities // Pacific Journal of Mathematics. — 1988. — Т. 133, вып. 1. — С. 41—67. — doi:10.2140/pjm.1988.133.41.
• D. J. Brown. A lower bound for on-line one-dimensional bin packing algorithms. — Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign, 1979. — Вып. Tech. Rep. R—864.
• D. R. Curtiss. On Kellogg's diophantine problem // American Mathematical Monthly. — 1922. — Т. 29, вып. 10. — С. 380—387. — doi:10.2307/2299023. — .
• Michael Domaratzki, Keith Ellul, Jeffrey Shallit, Ming-Wei Wang. Non-uniqueness and radius of cyclic unary NFAs // International Journal of Foundations of Computer Science. — 2005. — Т. 16, вып. 5. — С. 883—896. — doi:10.1142/S0129054105003352.
• Paul Erdős, Ronald L. Graham. Old and new problems and results in combinatorial number theory. — Monographies de L'Enseignement Mathématique, No. 28, Univ. de Genève, 1980.
• Gábor Galambos, Gerhard J. Woeginger. On-line bin packing — A restricted survey (англ.) // Mathematical Methods of Operations Research. — 1995. — Vol. 42, iss. 1. — P. 25. — doi:10.1007/BF01415672.
• Solomon W. Golomb. On certain nonlinear recurring sequences // American Mathematical Monthly. — 1963. — Т. 70, вып. 4. — С. 403—405. — doi:10.2307/2311857. — .
• R. Graham, D. E. Knuth, O. Patashnik. Concrete Mathematics. — 2nd. — Addison-Wesley, 1989. — ISBN 0-201-55802-5.
• Richard K. Guy. Unsolved Problems in Number Theory. — 3rd. — Springer-Verlag, 2004. — С. 346. — ISBN 0-387-20860-7.
• Richard Guy, Richard Nowakowski. Discovering primes with Euclid // Delta (Waukesha). — 1975. — Т. 5, вып. 2. — С. 49—63.
• Rafe Jones. The density of prime divisors in the arithmetic dynamics of quadratic polynomials. — 2006. — arXiv:math.NT/0612415.
• Frank M. Liang. A lower bound for on-line bin packing // Information Processing Letters. — 1980. — Т. 10, вып. 2. — С. 76—79. — doi:10.1016/S0020-0190(80)90077-0.
• G. A. Miller. Groups possessing a small number of sets of conjugate operators (англ.) // Transactions of the American Mathematical Society. — 1919. — Vol. 20, iss. 3. — P. 260—270. — doi:10.2307/1988867. — .
• R. W. K. Odoni. On the prime divisors of the sequence w_n+1 =1+w₁⋯w_n // J. Lond. Math. Soc., II. Ser.. — 1985. — Т. 32. — С. 1—11.
• Martin Rosenman, F. Underwood. Problem 3536 // American Mathematical Monthly. — 1933. — Т. 40, вып. 3. — С. 180—181. — .
• H. E. Salzer. The approximation of numbers as sums of reciprocals // American Mathematical Monthly. — 1947. — Т. 54, вып. 3. — С. 135—142. — doi:10.2307/2305906. — .
• Steven S. Seiden, Gerhard J. Woeginger. The two-dimensional cutting stock problem revisited // Mathematical Programming. — 2005. — Т. 102, вып. 3. — С. 519—530. — doi:10.1007/s10107-004-0548-1.
• K. Soundararajan. Approximating 1 from below using n Egyptian fractions. — 2005. — arXiv:math.CA/0502247.
• J. J. Sylvester. On a point in the theory of vulgar fractions // American Journal of Mathematics. — 1880. — Т. 3, вып. 4. — С. 332—335. — doi:10.2307/2369261. — .
• Ilan Vardi. Computational Recreations in Mathematica. — Addison-Wesley, 1991. — С. 82—89. — ISBN 0-201-52989-0.

Ссылки

• Irrationality of Quadratic Sums, from K. S. Brown’s MathPages.
• Weisstein, Eric W. Sylvester's Sequence (англ.) на сайте Wolfram MathWorld.