WikiDer > Последовательность Сильвестров - Википедия
В теория чисел, Последовательность Сильвестра является целочисленная последовательность в котором каждый член последовательности является произведением предыдущих членов плюс один. Первые несколько членов последовательности:
- 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (последовательность A000058 в OEIS).
Последовательность Сильвестра названа в честь Джеймс Джозеф Сильвестр, который впервые исследовал его в 1880 году. вдвойне экспоненциально, а сумма его взаимные образует серии из единицы измерения который сходится к единице быстрее, чем любой другой ряд дробей с таким же числом членов. В повторение которым он определяется, позволяет числам в последовательности быть учтенный легче, чем другие числа такой же величины, но из-за быстрого роста последовательности простые факторизации известны лишь некоторые из его терминов. Значения, полученные из этой последовательности, также использовались для построения конечных Египетская фракция представления 1, Сасакян Многообразия Эйнштейна, и тяжелые экземпляры для онлайн-алгоритмы.
Формальные определения
Формально последовательность Сильвестра можно определить формулой
В произведение пустого множества равно 1, поэтому s0 = 2.
В качестве альтернативы можно определить последовательность с помощью повторение
- с s0 = 2.
Это просто показать индукция что это эквивалентно другому определению.
Формула замкнутой формы и асимптотика
Числа Сильвестра растут вдвойне экспоненциально как функция п. В частности, можно показать, что
для ряда E то есть примерно 1,26408473530530 ...[1] (последовательность A076393 в OEIS). Эта формула имеет эффект следующего алгоритм:
- s0 ближайший целое число к E2; s1 это ближайшее целое число к E4; s2 это ближайшее целое число к E8; за sп, брать E2, квадрат п еще раз и возьмите ближайшее целое число.
Это был бы практический алгоритм только в том случае, если бы у нас был лучший способ вычисления E на необходимое количество мест, чем при расчете sп и принимая его повторное квадратный корень.
Двойной экспоненциальный рост последовательности Сильвестра неудивителен, если сравнить ее с последовательностью Числа Ферма Fп; числа Ферма обычно определяются по дважды экспоненциальной формуле: , но они также могут быть определены формулой произведения, очень похожей на формулу, определяющую последовательность Сильвестра:
Связь с египетскими фракциями
В единицы измерения сформированный взаимные значений в последовательности Сильвестра генерируют бесконечная серия:
В частичные суммы этой серии имеют простую форму,
Это можно доказать по индукции или, более прямо, отметив, что из рекурсии следует, что
итак сумма телескопы
Поскольку эта последовательность частичных сумм (sj − 2)/(sj - 1) сходится к единице, общий ряд образует бесконечный Египетская фракция представление номер один:
Можно найти конечные египетские дробные представления единицы любой длины, усекая этот ряд и вычитая единицу из последнего знаменателя:
Сумма первых k члены бесконечного ряда обеспечивают максимально возможное занижение единицы любым kегипетская фракция.[2] Например, первые четыре члена складываются в 1805/1806, и, следовательно, любая египетская дробь для числа в открытый интервал (1805/1806, 1) требует не менее пяти терминов.
Последовательность Сильвестра можно интерпретировать как результат жадный алгоритм для египетских дробей, который на каждом шаге выбирает наименьший возможный знаменатель, делающий частичную сумму ряда меньше единицы. В качестве альтернативы, члены последовательности после первого можно рассматривать как знаменатели странное жадное расширение 1/2.
Уникальность быстрорастущих серий с рациональными суммами
Как заметил сам Сильвестр, последовательность Сильвестра кажется уникальной тем, что имеет такие быстро растущие значения, одновременно имея ряд обратных величин, сходящихся к Рациональное число. Эта последовательность представляет собой пример, показывающий, что двухэкспоненциального роста недостаточно для того, чтобы целочисленная последовательность была последовательность иррациональности.[3]
Чтобы уточнить это, это следует из результатов Бадеа (1993) что, если последовательность целых чисел растет достаточно быстро, чтобы
и если сериал
сходится к рациональному числу Ато для всех п после некоторой точки эта последовательность должна определяться тем же повторением
который можно использовать для определения последовательности Сильвестра.
Эрдеш и Грэм (1980) предполагаемый что в результатах такого типа неравенство, ограничивающее рост последовательности, может быть заменено более слабым условием,
Бадеа (1995) исследует прогресс, связанный с этой гипотезой; смотрите также Коричневый (1979).
Делимость и факторизации
Если я < j, из определения следует, что sj ≡ 1 (мод sя). Следовательно, каждые два числа в последовательности Сильвестра равны относительно простой. Последовательность может использоваться, чтобы доказать, что существует бесконечно много простые числа, поскольку любое простое число может делить не более одного числа в последовательности. Более того, никакой простой множитель числа в последовательности не может быть сравним с 5 по модулю 6, и последовательность может использоваться, чтобы доказать, что существует бесконечно много простых чисел, конгруэнтных 7 по модулю 12.[4]
Нерешенная проблема в математике: Все ли члены в последовательности Сильвестра свободны от квадратов? (больше нерешенных задач по математике) |
Многое остается неизвестным о факторизации чисел в последовательности Сильвестра. Например, неизвестно, все ли числа в последовательности свободный от квадратов, хотя все известные термины есть.
В качестве Варди (1991) описывает, легко определить, какое число Сильвестра (если имеется) данное простое число п делит: просто вычислить повторение, определяя числа по модулю п до тех пор, пока не будет найдено число, конгруэнтное нулю (mod п) или нахождение повторяющегося модуля. Используя эту технику, он обнаружил, что 1166 из первых трех миллионов простых чисел делители чисел Сильвестра,[5] и что ни у одного из этих простых чисел нет квадрата, который делит число Сильвестра. Множество простых чисел, которые могут быть множителями чисел Сильвестра, имеет нулевую плотность во множестве всех простых чисел:[6] действительно, количество таких простых чисел меньше, чем Икс является .[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) использует то же свойство для верхняя граница размер определенных группы.
Смотрите также
Примечания
- ^ Грэм, Кнут и Паташник (1989) установите это как упражнение; смотрите также Голомб (1963).
- ^ Это утверждение обычно приписывают Кертисс (1922), но Миллер (1919) похоже, делает то же самое в более ранней статье. Смотрите также Розенман и Андервуд (1933), Зальцер (1947), и Саундарараджан (2005).
- ^ Парень (2004).
- ^ Гай и Новаковски (1975).
- ^ Это похоже на опечатку, поскольку Андерсен находит 1167 простых делителей в этом диапазоне.
- ^ Джонс (2006).
- ^ Одони (1985).
- ^ Все основные факторы п чисел Сильвестра sп с п < 5×107 и п ≤ 200 перечислены Варди. Кен Такусагава перечисляет факторизации до s9 и факторизация s10. Остальные факторизации взяты из список факторизаций последовательности Сильвестра поддерживается Йенсом Крузом Андерсеном. Проверено 13 июня 2014.
- ^ В своей работе Сейден и Вегингер называют последовательность Сильвестра «последовательностью Зальцера» после работы Зальцер (1947) по самому близкому приближению.
- ^ Domaratzki et al. (2005).
Рекомендации
- Бадеа, Каталин (1993). «Теорема об иррациональности бесконечных серий и приложений». Acta Arithmetica. 63 (4): 313–323. Дои:10.4064 / aa-63-4-313-323. МИСТЕР 1218459.CS1 maint: ref = harv (связь)
- Бадеа, Каталин (1995). «О некоторых критериях иррациональности ряда положительных рациональностей: опрос» (PDF). Архивировано из оригинал (PDF) 11 сентября 2008 г.CS1 maint: ref = harv (связь)
- Boyer, Charles P .; Галицкий, Кшиштоф; Коллар, Янош (2005). «Метрики Эйнштейна на сферах». Анналы математики. 162 (1): 557–580. arXiv:math.DG / 0309408. Дои:10.4007 / анналы.2005.162.557. МИСТЕР 2178969.CS1 maint: ref = harv (связь)
- Брентон, Лоуренс; Хилл, Ричард (1988). "О диофантовом уравнении 1 = Σ1 /пя + 1 / Πпя и класс гомологически тривиальных комплексных особенностей поверхности ». Тихоокеанский математический журнал. 133 (1): 41–67. Дои:10.2140 / pjm.1988.133.41. МИСТЕР 0936356.CS1 maint: ref = harv (связь)
- Браун, Д. Дж. (1979). «Нижняя граница для алгоритмов одномерной упаковки онлайн». Tech. Репортаж R-864. Скоординированная научная лаборатория, Univ. Иллинойс, Урбана-Шампейн. Цитировать журнал требует
| журнал =
(помощь)CS1 maint: ref = harv (связь) - Кертисс, Д. (1922). «О диофантовой проблеме Келлогга». Американский математический ежемесячный журнал. 29 (10): 380–387. Дои:10.2307/2299023. JSTOR 2299023.CS1 maint: ref = harv (связь)
- Домарацки, Майкл; Эллул, Кейт; Шаллит, Джеффри; Ван, Мин-Вэй (2005). «Неединственность и радиус циклических унарных НКА». Международный журнал основ информатики. 16 (5): 883–896. Дои:10.1142 / S0129054105003352. МИСТЕР 2174328.CS1 maint: ref = harv (связь)
- Эрдеш, Пол; Грэм, Рональд Л. (1980). Старые и новые проблемы и результаты комбинаторной теории чисел. Монографии де L'Enseignement Mathématique, № 28, Univ. де Женева. МИСТЕР 0592420.CS1 maint: ref = harv (связь)
- Галамбос, Габор; Вёгингер, Герхард Дж. (1995). «Бункерная упаковка в режиме онлайн - ограниченный обзор». Математические методы исследования операций. 42 (1): 25. Дои:10.1007 / BF01415672. МИСТЕР 1346486.CS1 maint: ref = harv (связь)
- Голомб, Соломон В. (1963). «О некоторых нелинейных повторяющихся последовательностях». Американский математический ежемесячный журнал. 70 (4): 403–405. Дои:10.2307/2311857. JSTOR 2311857. МИСТЕР 0148605.CS1 maint: ref = harv (связь)
- Грэм, Р.; Кнут, Д. Э.; Паташник, О. (1989). Конкретная математика (2-е изд.). Эддисон-Уэсли. Упражнение 4.37. ISBN 0-201-55802-5.CS1 maint: ref = harv (связь)
- Гай, Ричард К. (2004). «E24 Последовательности иррациональности». Нерешенные проблемы теории чисел (3-е изд.). Springer-Verlag. п. 346. ISBN 0-387-20860-7. Zbl 1058.11001.CS1 maint: ref = harv (связь)
- Гай, Ричард; Новаковски, Ричард (1975). «Открытие простых чисел с Евклидом». Дельта (Ваукеша). 5 (2): 49–63. МИСТЕР 0384675.CS1 maint: ref = harv (связь)
- Джонс, Рэйф (2006). «Плотность простых делителей в арифметической динамике квадратичных многочленов». Журнал Лондонского математического общества. 78 (2): 523–544. arXiv:math.NT / 0612415. Bibcode:2006математика ..... 12415J. Дои:10.1112 / jlms / jdn034.CS1 maint: ref = harv (связь)
- Лян, Фрэнк М. (1980). «Нижняя граница для бункерной упаковки в режиме онлайн». Письма об обработке информации. 10 (2): 76–79. Дои:10.1016 / S0020-0190 (80) 90077-0. МИСТЕР 0564503.CS1 maint: ref = harv (связь)
- Миллер, Г. А. (1919). «Группы, обладающие малым числом наборов сопряженных операторов». Труды Американского математического общества. 20 (3): 260–270. Дои:10.2307/1988867. JSTOR 1988867.CS1 maint: ref = harv (связь)
- Одони, Р. В. К. (1985). "О простых делителях последовательности wп + 1 = 1 + w1⋯ wп". Журнал Лондонского математического общества. Серия II. 32: 1–11. Дои:10.1112 / jlms / s2-32.1.1. Zbl 0574.10020.CS1 maint: ref = harv (связь)
- Розенман, Мартин; Андервуд, Ф. (1933). «Проблема 3536». Американский математический ежемесячный журнал. 40 (3): 180–181. Дои:10.2307/2301036. JSTOR 2301036.CS1 maint: ref = harv (связь)
- Зальцер, Х. Э. (1947). «Приближение чисел как суммы обратных величин». Американский математический ежемесячный журнал. 54 (3): 135–142. Дои:10.2307/2305906. JSTOR 2305906. МИСТЕР 0020339.CS1 maint: ref = harv (связь)
- Сейден, Стивен С .; Вёгингер, Герхард Дж. (2005). «Возвращение к двумерной проблеме раскроя». Математическое программирование. 102 (3): 519–530. Дои:10.1007 / s10107-004-0548-1. МИСТЕР 2136225.CS1 maint: ref = harv (связь)
- Саундарараджан, К. (2005). "Аппроксимация 1 снизу с помощью п Египетские фракции ». arXiv:math.CA/0502247. Цитировать журнал требует
| журнал =
(помощь)CS1 maint: ref = harv (связь) - Сильвестр, Дж. Дж. (1880 г.). «Об одном пункте теории вульгарных дробей». Американский журнал математики. 3 (4): 332–335. Дои:10.2307/2369261. JSTOR 2369261.CS1 maint: ref = harv (связь)
- Варди, Илан (1991). Вычислительные развлечения в системе Mathematica. Эддисон-Уэсли. С. 82–89. ISBN 0-201-52989-0.CS1 maint: ref = harv (связь)
внешняя ссылка
- Иррациональность квадратичных сумм, из MathPages К. С. Брауна.
- Вайсштейн, Эрик В. "Последовательность Сильвестра". MathWorld.