У теорії чисел послідовність Сильвестра — це послідовність цілих чисел, яка починається із 2, а кожен наступний член дорівнює добутку всіх попередніх членів, збільшеному на одиницю. Перші кілька її членів мають вигляд: 2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 ().

Послідовність Сильвестра названа на честь Джеймса Джозефа Сильвестра, який уперше дослідив її у 1880 році.Sylvester (1880). Її значення зростають із швидкістю, а сума їхніх обернених величин утворює ряд одиничних дробів, що збігається до 1 швидше, ніж будь-який інший ряд таких дробів.Це твердження зазвичай приписують Кертіссу (Curtiss, 1922), але Міллер (Miller, 1919), фактично формулює те саме раніше у своїй роботі. Див. також Rosenman & Underwood (1933), Salzer (1947), Soundararajan (2005) та Nathanson (2023). Рекурентність, якою задається ця послідовність, дозволяє розкладати числа в послідовності на множники значно легше, ніж інші числа тієї ж величини.Vardi (1991). Утім, через швидке зростання послідовності повні розклади на прості множники відомі лише для кількох її членів.Усі прості дільники чисел послідовності Сильвестра з та наведені у Варді. Ken Takusagawa подає розклади на прості множники до і факторизацію . Решта факторизацій взяті зі списку, який підтримує Jens Kruse Andersen (доступ 2014-06-13). Значення, отримані з цієї послідовності, також використовувалися для побудови представлень одиниці у вигляді скінченних єгипетських дробів, сасакієвих Boyer, Galicki & Kollár (2005). та складних прикладів для онлайн-алгоритмів.Galambos & Woeginger (1995); Brown (1979); Liang (1980).

Формальні визначення Формально, послідовність Сильвестра можна визначити формулою:Sloane, N. J. А. (ред.). «Sequence A000058 (Sylvester's sequence)». The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

Порожній добуток множини дорівнює одиниціNešetřil & Matoušek (1998)., тому ця формула дає , без потреби в окремому базовому випадку.

Альтернативно, можна визначити послідовність за допомогою рекурентності , із базовим випадком .

Легко показати за допомогою індукції, що це еквівалентно іншому визначенню.Доведення методом індукції наведено в роботі: Sylvester (1880), c. 333.

Формула замкненої форми та асимптотика Числа Сильвестра зростають як функція від . Зокрема, можна показати, що , де  — це константа, яка приблизно дорівнює 1.26408473530530…Graham, Knuth & Patashnik (1989), формула 4.17, с. 109, та вправа 4.37, с. 147; див. також Golomb (1963). (). Ця формула має вигляд наступного алгоритму:  — це найближче ціле число до ;  — найближче ціле число до ;  — найближче ціле число до ; загалом для обчислення необхідно взяти , піднести до квадрата ще разів і округлити до найближчого цілого. Такий підхід мав би практичне значення лише за умови існування ефективнішого способу обчислення числа з необхідною точністю, ніж обчислення члена з подальшим добуванням квадратного кореня.Graham, Knuth & Patashnik (1989), c. 109.

Подвійне експоненціальне зростання послідовності Сильвестра не є несподіваним, якщо порівняти її з послідовністю чисел Ферма . Числа Ферма зазвичай визначаються подвійно експоненціальною формулою, , але їх також можна визначити формулою добутку, дуже подібною до тієї, що визначає послідовність Сильвестра:Sloane, N. J. А. (ред.). «Sequence A000215 (Fermat numbers)». The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

Зв'язок з єгипетськими дробами Одиничні дроби, утворені оберненими величинами значень у послідовності Сильвестра, генерують нескінченний ряд:Цей ряд є відправною точкою дослідження Сильвестра (1880).

Часткові суми цього ряду мають простий вигляд , що вже є нескоротним дробом.Sylvester (1880), с. 334. Це можна довести індукцією або безпосередньо зазначивши, що із рекурентного співвідношення слідує .

Отже, сума згортається .

Оскільки ця послідовність частинних сум збігається до одиниці, то загальний ряд утворює нескінченне представлення числа 1 у вигляді єгипетського дробу:

Можна знайти скінченні представлення 1 у вигляді єгипетських дробів будь-якої довжини, скоротивши цей ряд і віднявши одиницю від останнього знаменника:

Сума перших членів нескінченного ряду забезпечує найкраще можливе наближення знизу до числа 1 будь-яким -членним єгипетським дробом. Наприклад, перші чотири члени в сумі дають 1805/1806, і тому будь-який єгипетський дріб для числа у відкритому інтервалі (1805/1806, 1) потребує щонайменше п'яти членів.

Послідовність Сильвестра можна інтерпретувати як результат жадібного алгоритму для єгипетських дробів, який на кожному кроці обирає найменший можливий знаменник, за якого часткова сума відповідного ряду залишається меншою за одиницю.Nathanson (2023).

Унікальність швидкозростаючих рядів з раціональними сумами Як зазначав сам Сильвестр, його послідовність є унікальною тим, що має такі швидко зростаючі значення, але водночас має ряд обернених величин, що збігаються до раціонального числа. Ця послідовність є прикладом того, що подвійного експоненціального зростання недостатньо, щоб цілочисельна послідовність була ірраціональною послідовністю.Guy (2004).

Більш строго це випливає з результатів Бадеа (1993): якщо послідовність цілих чисел зростає так швидко, що , і якщо ряд

збігається до раціонального числа , то для всіх , починаючи з певного моменту, ця послідовність має бути визначена тією ж рекурентністю

що й послідовність Сильвестра.Badea (1993).

У праці 1980 року Пол Ердеш (Paul Erdős) і Рональд Грем (Ronald Graham) висловили гіпотезу, що в результатах такого типу нерівність, яка обмежує швидкість зростання послідовності, можна замінити слабшою умовоюErdős & Graham (1980).

Бадеа (1995) подає огляд результатів, пов'язаних із цією гіпотезою; див. також Браун (1979).Badea (1995); Brown (1979).

Подільність і розклади на множники Якщо , то з означення безпосередньо випливає, що . Отже, будь-які два числа з послідовності Сильвестра є взаємно простими. Цю послідовність можна використовувати для доведення того, що простих чисел існує нескінченно багато, оскільки кожне просте число може ділити щонайбільше один член цієї послідовності. Більш того, жоден простий дільник числа з послідовності не може бути конгруентним до 5 за модулем 6, а сама послідовність дозволяє довести існування нескінченно багатьох простих чисел, конгруентних до 7 за модулем 12.Guy & Nowakowski (1975). Жоден член послідовності не може бути досконалим степенем.Makki Naciri (2024).

Наразі про розклад чисел послідовності Сильвестра на множники відомо небагато. Наприклад, невідомо, чи всі числа в послідовності є безквадратними, хоча всі відомі члени задовольняють цю умову.Graham, Knuth & Patashnik (1989), наукове дослідження 4.65, с. 151; Vardi (1991); див. також Chentouf (2020).

Як описує Варді (1991), легко визначити, яке саме число Сильвестра (якщо таке існує) ділиться на задане просте число : для цього достатньо обчислити рекурентність за модулем , доти, доки не знайдеться або число, що конгруентне нулю (mod ), або повторюваний модуль. Використовуючи цей метод, він встановив, що 1166 із перших трьох мільйонів простих чисел є дільниками чисел Сильвестра,Це, швидше за все, друкарська помилка в оригінальному джерелі, оскільки Андерсен виявив 1167 простих дільників у цьому діапазоні. причому жодне з цих простих чисел не має властивості, щоб його квадрат ділив якийсь член послідовності. Множина простих чисел, які можуть бути дільниками чисел Сильвестра, має нульову щільність у множині всіх простих чисел:Jones (2006). зокрема, кількість таких простих чисел, менших за , оцінюється як .Odoni (1985).

У таблиці нижче наведено відомі розклади цих чисел на множники (за винятком членів від до , які є простими):

+ Відомі розклади чисел Сильвестра на множники 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 × 6046639770155612333765567 × C53313 19 775608719589345260583891023073879169 × C106685 20 352867 × 6210298470888313 × C213419 21 387347773 × 1620516511 × C426863 22 91798039513 × 7919244169465663354953966404923 × C853719

Загальноприйняті позначення та позначають прості та не розкладені на фактори складені числа довжиною у знаків.

Застосування Бойєр, Галіцкі та Коллар (2005) використовують властивості послідовності Сильвестра для побудови великої кількості сасакієвих многовидів Ейнштейна, що мають диференціальну топологію непарновимірних або екзотичних сфер. Вони показали, що кількість різних сасакієвих метрик Ейнштейна на топологічній сфері розмірності є принаймні пропорційною , а отже, зростає подвійно експоненційно зі збільшенням .

Як описують Галамбос і Вегінгер (1995), Браун (1979) і Лян (1980) використовували значення, отримані з послідовності Сильвестра, для побудови прикладів нижньої межі для онлайн-алгоритмів упаковки в контейнери. Зайден і Вегінгер (2005) схожим чином застосували послідовність для оцінки нижньої межі ефективності двовимірного алгоритму розкрою.У своїй роботі Зайден і Вегінгер називають послідовність Сильвестра «послідовністю Салзера» на честь праці Салзера (Salzer, 1947), присвяченої задачі найкращого наближення.

Задача Знама полягає у знаходженні множин чисел, у яких кожне число ділить, але не дорівнює добутку всіх інших чисел, збільшеному на одиницю. Якщо не вимагати виконання цієї нерівності, то значення послідовності Сильвестра утворювали б розв'язок задачі. За умови її виконання задача має інші розв'язки, отримані з рекурентностей, подібних до тих, що визначають послідовність Сильвестра. Розв'язки задачі Знама мають застосування в класифікації поверхневих сингулярностей (Брентон і Гілл, 1988) та в теорії недетермінованих скінченних автоматів.Domaratzki et al. (2005).

Кертісс (1922) описує застосування найближчих наближень до 1 через -членні суми одиничних дробів, для отримання нижніх меж кількості дільників будь-якого досконалого числа, а Міллер (1919) використовує цю ж властивість для встановлення верхніх меж порядку певних груп.Curtiss (1922); Miller (1919).

Див. також

Числа Леонардо

Примітки

Література

Посилання Ірраціональність квадратичних сум, MathPages К. С. Брауна