В теории чисел , последовательность Сильвестра представляет собой целое число , последовательность , в которой каждый член последовательности является продуктом предыдущих терминов, плюс один. Первые несколько членов последовательности:
- 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (последовательность A000058 в OEIS ).
Последовательность Сильвестра названа в честь Джеймса Джозефа Сильвестра , который первым исследуемом его в 1880. Его значения растут вдвое по экспоненте , и сумма его обратными образует ряд из единичных фракций , что сходится к 1 быстрее , чем любые другие серии единичных фракций с тем же количество терминов. Рецидивы которой она определяется позволяет числа в последовательности , которые будут учитываться более легко , чем другие номера одинаковой величины, но, в связи с быстрым ростом последовательности, полные простые множители известны только некоторые из его условий. Значения, полученные из этой последовательности, также использовались для построения конечных египетских представлений дроби 1, сасакиевских многообразий Эйнштейна и сложных экземпляров для онлайн-алгоритмов .
Формальные определения
Формально последовательность Сильвестра можно определить формулой
Произведение пустого множества равно 1, так что ев 0 = 2.
В качестве альтернативы можно определить последовательность повторением
- с s 0 = 2.
По индукции легко показать, что это эквивалентно другому определению.
Формула замкнутой формы и асимптотика
Числа Сильвестра растут двукратно экспоненциально в зависимости от n . В частности, можно показать, что
для числа E , которое приблизительно равно 1,26408473530530 ... [1] (последовательность A076393 в OEIS ). Эта формула действует по следующему алгоритму :
- s 0 - ближайшее целое число к E 2 ; s 1 - ближайшее целое число к E 4 ; s 2 - ближайшее целое число к E 8 ; в качестве s n возьмите E 2 , возведите его в квадрат еще n раз и возьмите ближайшее целое число.
Это был бы практический алгоритм только в том случае, если бы у нас был лучший способ вычисления E с требуемым количеством знаков, чем вычисление s n и извлечение его повторяющегося квадратного корня .
Двойной экспоненциальный рост последовательности Сильвестра неудивителен, если сравнить ее с последовательностью чисел Ферма F n ; числа Ферма обычно определяются дважды экспоненциальной формулой:, но они также могут быть определены формулой произведения, очень похожей на формулу, определяющую последовательность Сильвестра:
Связь с египетскими фракциями
В блоке фракции , образованная обратные значений в последовательности Сильвестра обеспечить создание бесконечной серии :
В частичных суммах этой серии имеют простую форму,
Это можно доказать по индукции или, более прямо, отметив, что из рекурсии следует, что
так что сумма телескопов
Поскольку эта последовательность частичных сумм ( s j - 2) / ( s j - 1) сходится к единице, общий ряд образует представление бесконечной египетской дроби числа один:
Можно найти конечные египетские дробные представления единицы любой длины, усекая этот ряд и вычитая единицу из последнего знаменателя:
Сумма первых k членов бесконечного ряда дает максимально возможное занижение единицы любой k- членной египетской дробью. [2] Например, первые четыре члена складываются в 1805/1806, и поэтому любая египетская дробь для числа в открытом интервале (1805/1806, 1) требует как минимум пяти членов.
Можно интерпретировать последовательность Сильвестра как результат жадного алгоритма для египетских дробей , который на каждом шаге выбирает наименьший возможный знаменатель, делающий частичную сумму ряда меньше единицы. В качестве альтернативы, члены последовательности после первого можно рассматривать как знаменатели нечетного жадного расширения 1/2.
Уникальность быстрорастущих серий с рациональными суммами
Как заметил сам Сильвестр, последовательность Сильвестра кажется уникальной тем, что имеет такие быстро растущие значения, одновременно имея ряд обратных величин, сходящихся к рациональному числу . Эта последовательность представляет собой пример, показывающий, что двухэкспоненциального роста недостаточно для того, чтобы целочисленная последовательность была последовательностью иррациональности . [3]
Чтобы уточнить это, из результатов Badea (1993) следует, что если последовательность целых чисел растет достаточно быстро, чтобы
и если сериал
сходится к рациональному числу A , то для всех n после некоторой точки эта последовательность должна определяться той же рекуррентностью
который можно использовать для определения последовательности Сильвестра.
Эрдеш и Грэм (1980) предположили, что в результатах такого типа неравенство, ограничивающее рост последовательности, может быть заменено более слабым условием:
Badea (1995) рассматривает прогресс, связанный с этой гипотезой; см. также Brown (1979) .
Делимость и факторизации
Если i < j , из определения следует, что s j ≡ 1 (mod s i ). Следовательно, каждые два числа в последовательности Сильвестра взаимно простые . Последовательность может использоваться, чтобы доказать, что существует бесконечно много простых чисел , так как любое простое число может делить не более одного числа в последовательности. Более того, никакой простой множитель числа в последовательности не может быть сравним с 5 по модулю 6, и последовательность может использоваться для доказательства того, что существует бесконечно много простых чисел, сравнимых с 7 по модулю 12. [4]
Все ли члены в последовательности Сильвестра свободны от квадратов?
Многое остается неизвестным о факторизации чисел в последовательности Сильвестра. Например, неизвестно, все ли числа в последовательности свободны от квадратов , хотя все известные термины таковыми являются.
Как описывает Варди (1991) , легко определить, какое число Сильвестра (если есть) делит данное простое число p : просто вычислите рекуррентность, определяющую числа по модулю p, пока не найдете либо число, конгруэнтное нулю (mod p ), либо найдите повторяющийся модуль. Используя эту технику, он обнаружил, что 1166 из первых трех миллионов простых чисел являются делителями чисел Сильвестра [5], и что ни одно из этих простых чисел не имеет квадрата, который делит число Сильвестра. Множество простых чисел, которые могут встречаться как множители чисел Сильвестра, имеет нулевую плотность во множестве всех простых чисел: [6] действительно, количество таких простых чисел меньше x равно. [7]
В следующей таблице показаны известные факторизации этих чисел (кроме первых четырех, которые все простые): [8]
п | Факторы 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 & Woeginger (2005) аналогичным образом используют последовательность для нижней границы производительности двумерного алгоритма раскроя материала. [9]
Проблема Знама касается таких наборов чисел, что каждое число в наборе делится, но не равно произведению всех остальных чисел плюс один. Без требования неравенства значения в последовательности Сильвестра решили бы проблему; с этим требованием у него есть другие решения, полученные из повторений, аналогичные тому, который определяет последовательность Сильвестра. Решения проблемы Знама имеют приложения к классификации особенностей поверхностей (Брентон, Хилл, 1988) и к теории недетерминированных конечных автоматов . [10]
Д.Кертисс ( 1922 ) описывает применение наиболее близких приближений к сумме единичных k- членов единичных дробей при оценке снизу числа делителей любого совершенного числа , а Миллер (1919) использует то же свойство для верхней границы размера. определенных групп .
Смотрите также
- Постоянная каэна
- Первичное псевдосовершенное число
- Число Леонардо
Заметки
- ^ Грэм, Кнут и Паташник (1989) использовали это как упражнение; см. также Голомб (1963) .
- ^ Это утверждение обычно приписывают Кертиссу (1922) , но Миллер (1919), похоже, делает то же утверждение в более ранней статье. См. Также Rosenman & Underwood (1933) , Salzer (1947) и Soundararajan (2005) .
- Перейти ↑ Guy (2004) .
- ^ Гай и Новаковски (1975) .
- ^ Это похоже на опечатку, поскольку Андерсен находит 1167 простых делителей в этом диапазоне.
- ^ Джонс (2006) .
- ^ Odoni (1985) .
- ^ Все простые множители p чисел Сильвестра s n с p <5 × 10 7 и n ≤ 200 перечислены Варди. Кен Такусагава перечисляет факторизации до s 9 и факторизацию s 10 . Остальные факторизации взяты из списка факторизаций последовательности Сильвестра, поддерживаемого Йенсом Крузом Андерсеном. Проверено 13 июня 2014.
- ^ В своей работе Зайден и Вегингер называют последовательность Сильвестра «последовательностью Зальцера» после работы Зальцера (1947) о наиболее близком приближении.
- ^ Domaratzki et al. (2005) .
Рекомендации
- Бадеа, Каталин (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 .