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

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

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

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (последовательность A000058 в OEIS ).

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

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

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

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

Произведение пустого множества равно 1, поэтому эта формула дает s ₀ = 2 без необходимости использования отдельного базового случая .

Альтернативно, можно определить последовательность с помощью повторения

$\displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1,$ с базовым случаем s ₀ = 2.

Нетрудно показать по индукции , что это эквивалентно другому определению.

Формула замкнутой формы и асимптотика

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

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

для числа E , которое примерно равно 1,26408473530530... (последовательность A076393 в OEIS ). Эта формула имеет эффект следующего алгоритма :

s ₀ — ближайшее целое число к E ² ; s ₁ — ближайшее целое число к E ⁴ ; s ₂ — ближайшее целое число к E ⁸ ; вместо sn _​ возьми E ² , в квадрат возведите его еще n раз и возьмите ближайшее целое число.

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

Двойной экспоненциальный рост последовательности Сильвестра неудивителен, если сравнить его с последовательностью чисел Ферма 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) требует как минимум пяти членов.

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

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

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

Точнее, из результатов Бадеа (1993) следует , что если последовательность целых чисел $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$

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

Эрдеш и Грэм (1980) предположили , что в результатах такого типа неравенство , ограничивающее рост последовательности, можно заменить более слабым условием:

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

Бадеа (1995) исследует прогресс, связанный с этой гипотезой ; см. также Браун (1979) .

Делимость и факторизация

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

Нерешенная задача по математике :

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

(еще нерешенные задачи по математике)

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

Как описывает Варди (1991) , легко определить, какое число Сильвестра (если оно есть) делит данное простое число p : просто вычислите рекуррентность, определяющую числа по модулю p, до тех пор, пока не будет найдено либо число, конгруэнтное нулю (mod p ), либо не будет найдено повторяющийся модуль. Используя этот метод, он обнаружил, что 1166 из первых трех миллионов простых чисел являются делителями чисел Сильвестра. и что ни одно из этих простых чисел не имеет квадрата, делящего число Сильвестра. Набор простых чисел, которые могут встречаться как множители чисел Сильвестра, имеет нулевую плотность в наборе всех простых чисел: действительно, число таких простых чисел меньше x равно $O(\pi (x)/\log \log \log x)$.

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

н	Факторы s n
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 × С416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
14	13999 x 74203 x 9638659 x 57218683 x 10861631274478494529 x 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

Как обычно, P n и C n обозначают простые числа и нефакторизованные составные числа длиной n цифр.

Приложения

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

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

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

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

См. также

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

Ссылки

• Бадеа, Кэтрин (1993). «Теорема об иррациональности бесконечных рядов и приложения » Акта Арифметика 63 (4): 313–323. дои : 10.4064/aa-63-4-313-323 . МР   1218459 .
• Бадеа, Каталин (1995). «О некоторых критериях иррациональности ряда положительных рациональных идей: обзор» (PDF) . Архивировано из оригинала (PDF) 11 сентября 2008 г.
• Бойер, Чарльз П.; Галицкий, Кшиштоф; Коллар, Янош (2005). «Метрики Эйнштейна на сферах». Анналы математики . 162 (1): 557–580. arXiv : math.DG/0309408 . дои : 10.4007/анналы.2005.162.557 . МР   2178969 . S2CID   13945306 .
• Брентон, Лоуренс; Хилл, Ричард (1988). «О диофантовом уравнении 1=Σ1/ n _i + 1/Π n _i и одном классе гомологически тривиальных комплексных особенностей поверхности» . Тихоокеанский математический журнал . 133 (1): 41–67. дои : 10.2140/pjm.1988.133.41 . МР   0936356 .
• Браун, ди-джей (1979). Нижняя граница для онлайн-алгоритмов одномерной упаковки контейнеров . Тех. Реп. Р-864. Координированная научная лаборатория, Univ. Иллинойс, Урбана-Шампейн.
• Шентуф, А. Анас (2020). «О последовательности Сильвестра и некоторых ее свойствах» (PDF) . Парабола . 56 (2).
• Кертисс, Д.Р. (1922). «О диофантовой задаче Келлога». Американский математический ежемесячник . 29 (10): 380–387. дои : 10.2307/2299023 . JSTOR   2299023 .
• Домарацкий, Майкл; Эллул, Кейт; Шалит, Джеффри ; Ван, Мин-Вэй (2005). «Неединственность и радиус циклических унарных НКА» . Международный журнал основ компьютерных наук . 16 (5): 883–896. дои : 10.1142/S0129054105003352 . МР   2174328 .
• Эрдеш, Пол ; Грэм, Рональд Л. (1980). Старые и новые проблемы и результаты комбинаторной теории чисел . Монографии по математическому образованию, № 28, Унв. из Женевы. МР   0592420 .
• Галамбос, Габор; Вегингер, Герхард Дж. (1995). «Упаковка контейнеров в режиме онлайн — опрос с ограниченным доступом». Математические методы исследования операций . 42 (1): 25. дои : 10.1007/BF01415672 . МР   1346486 . S2CID   26692460 .
• Голомб, Соломон В. (1963). «О некоторых нелинейных повторяющихся последовательностях». Американский математический ежемесячник . 70 (4): 403–405. дои : 10.2307/2311857 . JSTOR   2311857 . МР   0148605 .
• Грэм, Рональд ; Кнут, Дональд Э .; Паташник, Орен (1989). Конкретная математика (2-е изд.). Аддисон-Уэсли . ISBN  978-0-201-55802-9 .
• Гай, Ричард К. (2004). «E24 Последовательности иррациональности». Нерешенные проблемы теории чисел (3-е изд.). Спрингер-Верлаг . п. 346. ИСБН  0-387-20860-7 . Збл   1058.11001 .
• Гай, Ричард; Новаковски, Ричард (1975). «Открытие простых чисел с помощью Евклида». Дельта (Ваукеша) . 5 (2): 49–63. МР   0384675 .
• Джонс, Рэйф (2006). «Плотность простых делителей в арифметической динамике квадратных многочленов». Журнал Лондонского математического общества . 78 (2): 523–544. arXiv : math.NT/0612415 . Бибкод : 2006math.....12415J . дои : 10.1112/jlms/jdn034 . S2CID   15310955 .
• Лян, Фрэнк М. (1980). «Нижняя граница для упаковки контейнеров в режиме онлайн». Письма об обработке информации . 10 (2): 76–79. дои : 10.1016/S0020-0190(80)90077-0 . МР   0564503 .
• Нешетрил, Ярослав ; Матушек, Иржи (1998). Приглашение к дискретной математике . Издательство Оксфордского университета. Мистер. 12. ISBN  0-19-850207-9 .
• Миллер, Джорджия (1919). «Группы, обладающие малым числом наборов сопряженных операторов» . Труды Американского математического общества . 20 (3): 260–270. дои : 10.2307/1988867 . JSTOR   1988867 .
• Натансон, Мелвин Б. (январь 2023 г.). «Занижение египетскими дробями». Журнал теории чисел . 242 : 208–234. arXiv : 2202.00191 . дои : 10.1016/j.jnt.2022.07.005 .
• Одони, RWK (1985). «О простых делителях последовательности w _n+1 =1+w ₁ ⋯w _n «. Журнал Лондонского математического общества . Серия II. 32 : 1–11. дои : 10.1112/jlms/s2-32.1.1 . Збл   0574.10020 .
• Розенман, Мартин; Андервуд, Ф. (1933). «Задача 3536». Американский математический ежемесячник . 40 (3): 180–181. дои : 10.2307/2301036 . JSTOR   2301036 .
• Зальцер, HE (1947). «Приближение чисел суммами обратных величин». Американский математический ежемесячник . 54 (3): 135–142. дои : 10.2307/2305906 . JSTOR   2305906 . МР   0020339 .
• Сейден, Стивен С.; Вегингер, Герхард Дж. (2005). «Ещё раз к проблеме двумерного режущего материала». Математическое программирование . 102 (3): 519–530. дои : 10.1007/s10107-004-0548-1 . МР   2136225 . S2CID   35815524 .
• Саундарараджан, К. (2005). «Приближение 1 снизу с помощью n египетских дробей». arXiv : math.CA/0502247 .
• Сильвестр, Джей-Джей (1880). «Об одном пункте теории обыкновенных дробей». Американский журнал математики . 3 (4): 332–335. дои : 10.2307/2369261 . JSTOR   2369261 .
• Варди, Илан (1991). Вычислительные развлечения в системе Mathematica . Аддисон-Уэсли. стр. 82–89. ISBN  0-201-52989-0 .

Внешние ссылки

• Иррациональность квадратичных сумм , из MathPages К.С. Брауна.
• Вайсштейн, Эрик В. «Последовательность Сильвестра» . Математический мир .