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

Графическая демонстрация сходимости суммы 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, сасакиевских многообразий Эйнштейна и сложных экземпляров для онлайн-алгоритмов.

• 1 Формальные определения
• 2 Формула в замкнутой форме и асимптотика
• 3 Связь с египетскими фракциями
• 4 Уникальность быстрорастущих рядов с рациональными суммами
• 5 Делимость и факторизация
• 6 приложений
• 7 См. Также
• 8 Примечания
• 9 ссылки
• 10 Внешние ссылки

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

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

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

В качестве альтернативы можно определить последовательность повторением

${\ displaystyle \ displaystyle s_ {i} = s_ {i-1} (s_ {i-1} -1) +1,}$с s 0 = 2.

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

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

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

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

s 0 - ближайшее целое число к E ² ; s 1 - ближайшее целое число к E ⁴ ; s 2 - ближайшее целое число к E ⁸ ; в качестве s n возьмите E ², возведите его в квадрат еще n раз и возьмите ближайшее целое число.

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

Двойной экспоненциальный рост последовательности Сильвестра неудивителен, если сравнить ее с последовательностью чисел Ферма F n ; числа Ферма обычно определяются с помощью двояко экспоненциальной формулы, но они также могут быть определены с помощью формулы произведения, очень похожей на формулу, определяющую последовательность Сильвестра: ${\ displaystyle 2 ^ {2 ^ {n}} + 1}$

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

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

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

В частичных суммах этой серии имеют простую форму,

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

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

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

так что сумма телескопов

${\ displaystyle \ 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) сходится к единице, общий ряд образует представление бесконечной египетской дроби числа один:

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

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

${\ displaystyle 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.

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

Чтобы сделать это более точным, из результатов Badea (1993) следует, что если последовательность целых чисел растет достаточно быстро, то ${\ displaystyle a_ {n}}$

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

и если сериал

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

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

${\ displaystyle a_ {n} = a_ {n-1} ^ {2} -a_ {n-1} +1}$

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

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

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

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

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

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

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

(больше нерешенных задач по математике)

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

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

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

п	Факторы 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 × 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

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

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

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

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

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

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

• Бадеа, Каталин (1993). «Теорема об иррациональности бесконечных серий и приложений». Acta Arithmetica. 63 (4): 313–323. DOI : 10,4064 / аа-63-4-313-323. Руководство по ремонту   1218459.
• Бадеа, Каталин (1995). «О некоторых критериях иррациональности для ряда положительных рациональностей: обзор» (PDF). Архивировано из оригинального (PDF) 11 сентября 2008 года.
• Boyer, Charles P.; Галицкий, Кшиштоф; Коллар, Янош (2005). «Метрики Эйнштейна на сферах». Анналы математики. 162 (1): 557–580. arXiv : math.DG / 0309408. DOI : 10.4007 / анналы.2005.162.557. Руководство по ремонту   2178969. S2CID   13945306.
• Брентон, Лоуренс; Хилл, Ричард (1988). «О диофантовом уравнении 1 = Σ1 / n i + 1 / Π n i и классе гомологически тривиальных комплексных особенностей поверхности». Тихоокеанский математический журнал. 133 (1): 41–67. DOI : 10,2140 / pjm.1988.133.41. Руководство по ремонту   0936356.
• Браун, ди-джей (1979). «Нижняя граница для онлайн-алгоритмов одномерной упаковки контейнеров». Tech. Реп. R-864. Скоординированная научная лаборатория, Univ. Иллинойс, Урбана-Шампейн. Цитировать журнал требует |journal=( помощь )
• Кертисс, DR (1922). «О диофантовой проблеме Келлогга». Американский математический ежемесячник. 29 (10): 380–387. DOI : 10.2307 / 2299023. JSTOR   2299023.
• Домарацки, Майкл; Эллул, Кейт; Шаллит, Джеффри ; Ван, Мин-Вэй (2005). «Неединственность и радиус циклических унарных НКА». Международный журнал основ информатики. 16 (5): 883–896. DOI : 10.1142 / S0129054105003352. Руководство по ремонту   2174328.
• Эрдеш, Пол ; Грэм, Рональд Л. (1980). Старые и новые проблемы и результаты комбинаторной теории чисел. Монографии де L'Enseignement Mathématique, № 28, Univ. де Женева. Руководство по ремонту   0592420.
• Галамбос, Габор; Woeginger, Герхард Дж. (1995). «Онлайн-бункерная упаковка - ограниченный обзор». Математические методы исследования операций. 42 (1): 25. DOI : 10.1007 / BF01415672. Руководство по ремонту   1346486. S2CID   26692460.
• Голомб, Соломон В. (1963). «О некоторых нелинейных повторяющихся последовательностях». Американский математический ежемесячник. 70 (4): 403–405. DOI : 10.2307 / 2311857. JSTOR   2311857. Руководство по ремонту   0148605.
• Graham, R. ; Knuth, DE ; Паташник О. (1989). Конкретная математика (2-е изд.). Эддисон-Уэсли. Упражнение 4.37. ISBN   0-201-55802-5.
• Гай, Ричард К. (2004). «E24 Последовательности иррациональности». Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag. п. 346. ISBN.   0-387-20860-7. Zbl   1058.11001.
• Гай, Ричард; Новаковски, Ричард (1975). «Открытие простых чисел с Евклидом». Дельта (Ваукеша). 5 (2): 49–63. Руководство по ремонту   0384675.
• Джонс, Рэйф (2006). «Плотность простых делителей в арифметической динамике квадратичных многочленов». Журнал Лондонского математического общества. 78 (2): 523–544. arXiv : math.NT / 0612415. Bibcode : 2006math..... 12415J. DOI : 10,1112 / jlms / jdn034. S2CID   15310955.
• Лян, Фрэнк М. (1980). «Нижняя граница для бункерной упаковки в режиме онлайн». Письма об обработке информации. 10 (2): 76–79. DOI : 10.1016 / S0020-0190 (80) 90077-0. Руководство по ремонту   0564503.
• Миллер, Г. А. (1919). «Группы, обладающие малым числом наборов сопряженных операторов». Труды Американского математического общества. 20 (3): 260–270. DOI : 10.2307 / 1988867. JSTOR   1988867.
• Одони, RWK (1985). «О простых делителях последовательности w n + 1 = 1 + w 1 ⋯ w n ». Журнал Лондонского математического общества. Серия II. 32: 1–11. DOI : 10.1112 / jlms / s2-32.1.1. Zbl   0574.10020.
• Розенман, Мартин; Андервуд, Ф. (1933). «Проблема 3536». Американский математический ежемесячник. 40 (3): 180–181. DOI : 10.2307 / 2301036. JSTOR   2301036.
• Зальцер, HE (1947). «Приближение чисел как суммы обратных величин». Американский математический ежемесячник. 54 (3): 135–142. DOI : 10.2307 / 2305906. JSTOR   2305906. Руководство по ремонту   0020339.
• Сейден, Стивен С.; Woeginger, Герхард Дж. (2005). «Возвращение к двумерной проблеме раскроя». Математическое программирование. 102 (3): 519–530. DOI : 10.1007 / s10107-004-0548-1. Руководство по ремонту   2136225. S2CID   35815524.
• Саундарараджан, К. (2005). «Приближаем 1 снизу с использованием n египетских дробей». arXiv : math.CA/0502247. Цитировать журнал требует |journal=( помощь )
• Сильвестр, Дж. Дж. (1880 г.). «Об одном пункте теории вульгарных дробей». Американский журнал математики. 3 (4): 332–335. DOI : 10.2307 / 2369261. JSTOR   2369261.
• Варди, Илан (1991). Вычислительные развлечения в системе Mathematica. Эддисон-Уэсли. С. 82–89. ISBN   0-201-52989-0.

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