Последовательность сильвестров - Sylvesters sequence

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

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

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

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

В произведение пустого множества равно 1, поэтому s₀ = 2.

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

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

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

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

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

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

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

s₀ ближайший целое число к E²; s₁ это ближайшее целое число к E⁴; s₂ это ближайшее целое число к E⁸; за s_п, брать E², квадрат п еще раз и возьмите ближайшее целое число.

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

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

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

Связь с египетскими фракциями

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

${\displaystyle \sum _{i=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египетская фракция.^[2] Например, первые четыре члена складываются в 1805/1806, и, следовательно, любая египетская дробь для числа в открытый интервал (1805/1806, 1) требует не менее пяти терминов.

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

Уникальность быстрорастущих серий с рациональными суммами

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

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

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

и если сериал

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

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

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

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

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

Если я < j, из определения следует, что s_j ≡ 1 (мод s_я). Следовательно, каждые два числа в последовательности Сильвестра равны относительно простой. Последовательность может использоваться, чтобы доказать, что существует бесконечно много простые числа, поскольку любое простое число может делить не более одного числа в последовательности. Более того, никакой простой множитель числа в последовательности не может быть сравним с 5 по модулю 6, и последовательность может использоваться, чтобы доказать, что существует бесконечно много простых чисел, конгруэнтных 7 по модулю 12.^[4]

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

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

В качестве Варди (1991) описывает, легко определить, какое число Сильвестра (если имеется) данное простое число п делит: просто вычислить повторение, определяя числа по модулю п до тех пор, пока не будет найдено число, конгруэнтное нулю (mod п) или нахождение повторяющегося модуля. Используя эту технику, он обнаружил, что 1166 из первых трех миллионов простых чисел делители чисел Сильвестра,^[5] и что ни у одного из этих простых чисел нет квадрата, который делит число Сильвестра. Множество простых чисел, которые могут быть множителями чисел Сильвестра, имеет нулевую плотность во множестве всех простых чисел:^[6] действительно, количество таких простых чисел меньше, чем Икс является ${\displaystyle O(\pi (x)/\log \log \log x)}$.^[7]

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

п	Факторы sп
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п и Cп обозначают штрих и составной числа п цифры длинные.

Приложения

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

В качестве Галамбос и Вегингер (1995) описывать, Коричневый (1979) и Лян (1980) использовали значения, полученные из последовательности Сильвестра, для построения примеров нижней границы для онлайн упаковка бункера алгоритмы. Сейден и Вегингер (2005) аналогичным образом используйте последовательность для нижней границы производительности двумерного алгоритма раскроя заготовки.^[9]

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

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

Смотрите также

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

Примечания

1. Грэм, Кнут и Паташник (1989) установите это как упражнение; смотрите также Голомб (1963).
2. Это утверждение обычно приписывают Кертисс (1922), но Миллер (1919) похоже, делает то же самое в более ранней статье. Смотрите также Розенман и Андервуд (1933), Зальцер (1947), и Саундарараджан (2005).
3. Парень (2004).
4. Гай и Новаковски (1975).
5. Это похоже на опечатку, поскольку Андерсен находит 1167 простых делителей в этом диапазоне.
6. Джонс (2006).
7. Одони (1985).
8. Все основные факторы п чисел Сильвестра s_п с п < 5×10⁷ и п ≤ 200 перечислены Варди. Кен Такусагава перечисляет факторизации до s₉ и факторизация s₁₀. Остальные факторизации взяты из список факторизаций последовательности Сильвестра поддерживается Йенсом Крузом Андерсеном. Проверено 13 июня 2014.
9. В своей работе Сейден и Вегингер называют последовательность Сильвестра «последовательностью Зальцера» после работы Зальцер (1947) по самому близкому приближению.
10. Domaratzki et al. (2005).

Рекомендации

• Бадеа, Каталин (1993). «Теорема об иррациональности бесконечных серий и приложений». Acta Arithmetica. 63 (4): 313–323. Дои:10.4064 / aa-63-4-313-323. МИСТЕР  1218459.
• Бадеа, Каталин (1995). «О некоторых критериях иррациональности ряда положительных рациональностей: опрос» (PDF). Архивировано из оригинал (PDF) 11 сентября 2008 г.
• Boyer, Charles P .; Галицкий, Кшиштоф; Коллар, Янош (2005). «Метрики Эйнштейна на сферах». Анналы математики. 162 (1): 557–580. arXiv:math.DG / 0309408. Дои:10.4007 / анналы.2005.162.557. МИСТЕР  2178969.
• Брентон, Лоуренс; Хилл, Ричард (1988). "О диофантовом уравнении 1 = Σ1 /п_я + 1 / Πп_я и класс гомологически тривиальных комплексных особенностей поверхности ». Тихоокеанский математический журнал. 133 (1): 41–67. Дои:10.2140 / pjm.1988.133.41. МИСТЕР  0936356.
• Браун, Д. Дж. (1979). «Нижняя граница для алгоритмов одномерной упаковки онлайн». Tech. Репортаж R-864. Скоординированная научная лаборатория, Univ. Иллинойс, Урбана-Шампейн.
• Кертисс, Д. (1922). «О диофантовой проблеме Келлогга». Американский математический ежемесячный журнал. 29 (10): 380–387. Дои:10.2307/2299023. JSTOR  2299023.
• Домарацки, Майкл; Эллул, Кейт; Шаллит, Джеффри; Ван, Мин-Вэй (2005). «Неединственность и радиус циклических унарных НКА». Международный журнал основ информатики. 16 (5): 883–896. Дои:10.1142 / S0129054105003352. МИСТЕР  2174328.
• Эрдеш, Пол; Грэм, Рональд Л. (1980). Старые и новые проблемы и результаты комбинаторной теории чисел. Монографии де L'Enseignement Mathématique, № 28, Univ. де Женева. МИСТЕР  0592420.
• Галамбос, Габор; Вёгингер, Герхард Дж. (1995). «Бункерная упаковка в режиме онлайн - ограниченный обзор». Математические методы исследования операций. 42 (1): 25. Дои:10.1007 / BF01415672. МИСТЕР  1346486.
• Голомб, Соломон В. (1963). «О некоторых нелинейных повторяющихся последовательностях». Американский математический ежемесячный журнал. 70 (4): 403–405. Дои:10.2307/2311857. JSTOR  2311857. МИСТЕР  0148605.
• Грэм, Р.; Кнут, Д. Э.; Паташник, О. (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:2006математика ..... 12415J. Дои:10.1112 / jlms / jdn034.
• Лян, Фрэнк М. (1980). «Нижняя граница для бункерной упаковки в режиме онлайн». Письма об обработке информации. 10 (2): 76–79. Дои:10.1016 / S0020-0190 (80) 90077-0. МИСТЕР  0564503.
• Миллер, Г. А. (1919). «Группы, обладающие малым числом наборов сопряженных операторов». Труды Американского математического общества. 20 (3): 260–270. Дои:10.2307/1988867. JSTOR  1988867.
• Одони, Р. В. К. (1985). "О простых делителях последовательности w_{п + 1} = 1 + w₁⋯ w_п". Журнал Лондонского математического общества. Серия II. 32: 1–11. Дои:10.1112 / jlms / s2-32.1.1. Zbl  0574.10020.
• Розенман, Мартин; Андервуд, Ф. (1933). «Проблема 3536». Американский математический ежемесячный журнал. 40 (3): 180–181. Дои:10.2307/2301036. JSTOR  2301036.
• Зальцер, Х. Э. (1947). «Приближение чисел как суммы обратных величин». Американский математический ежемесячный журнал. 54 (3): 135–142. Дои:10.2307/2305906. JSTOR  2305906. МИСТЕР  0020339.
• Сейден, Стивен С .; Вёгингер, Герхард Дж. (2005). «Возвращение к двумерной проблеме раскроя». Математическое программирование. 102 (3): 519–530. Дои:10.1007 / s10107-004-0548-1. МИСТЕР  2136225.
• Саундарараджан, К. (2005). "Аппроксимация 1 снизу с помощью п Египетские фракции ». arXiv:math.CA/0502247.
• Сильвестр, Дж. Дж. (1880 г.). «Об одном пункте теории вульгарных дробей». Американский журнал математики. 3 (4): 332–335. Дои:10.2307/2369261. JSTOR  2369261.
• Варди, Илан (1991). Вычислительные развлечения в системе Mathematica. Эддисон-Уэсли. С. 82–89. ISBN  0-201-52989-0.

внешняя ссылка

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