Sekwencja Sylwestra

Graficzne przedstawienie zbieżności sumy 1/2 + 1/3 + 1/7 + 1/43 + ... do 1. Każdy rząd k kwadratów o długości boku 1/ k ma powierzchnię całkowitą 1/ k , a wszystkie kwadraty razem dokładnie pokrywają większy kwadrat o polu 1. Kwadraty o długości boku 1/1807 lub mniejszej są zbyt małe, aby można je było zobaczyć na rysunku i nie są pokazane.

W teorii liczb ciąg Sylwestra jest ciągiem liczb całkowitych , w którym każdy wyraz jest iloczynem poprzednich wyrazów plus jeden. Kilka pierwszych wyrazów ciągu to

2, 3, 7, 43, 1807, 3263443, 10650056950807, 113423713055421844361000443 (sekwencja A000058 w OEIS ).

Sekwencja Sylwestra nosi imię Jamesa Josepha Sylvestra , który po raz pierwszy zbadał ją w 1880 r. Jej wartości rosną dwukrotnie wykładniczo , a suma jej odwrotności tworzy serię ułamków jednostkowych , które zbiegają się do 1 szybciej niż jakakolwiek inna seria ułamków jednostkowych. Powtarzalność uwzględnienie liczb w sekwencji niż inne liczby o tej samej wielkości , ale ze względu na szybki wzrost sekwencji kompletna rozkłady na czynniki pierwsze są znane tylko dla kilku jego warunków. Wartości pochodzące z tej sekwencji zostały również wykorzystane do skonstruowania skończonych ułamków egipskich 1, rozmaitości Sasakiana Einsteina i twardych instancji algorytmów online .

Definicje formalne

Formalnie sekwencję Sylwestra można zdefiniować za pomocą wzoru

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

₀ Iloczyn zbioru pustego wynosi 1, więc s = 2.

Alternatywnie, można zdefiniować sekwencję na podstawie powtarzalności

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

Łatwo jest pokazać przez indukcję , że jest to równoważne innej definicji.

Formuła postaci zamkniętej i asymptotyki

Liczby Sylwestra rosną podwójnie wykładniczo jako funkcja n . W szczególności można to wykazać

${\ Displaystyle s_ {n} = \ lewo \ lfloor E ^ {2 ^ {n + 1}} + {\ Frac {1} {2}} \ prawo \rfloor ,\!}$

dla liczby E , która wynosi około 1,26408473530530... (sekwencja A076393 w OEIS ). Ta formuła ma wpływ na następujący algorytm :

₀ s jest liczbą całkowitą najbliższą E2 ^; s1 ^jest liczbą całkowitą najbliższą E4 _; s2 jest liczbą ^całkowitą najbliższą E8 _; dla s _n weź E ² , podnieś do kwadratu jeszcze n razy i weź najbliższą liczbę całkowitą.

Byłby to praktyczny algorytm tylko wtedy, gdybyśmy mieli lepszy sposób obliczania E do wymaganej liczby miejsc niż obliczanie s _n i wyciąganie z niego powtarzającego się pierwiastka kwadratowego .

Podwójny wykładniczy wzrost ciągu Sylwestra nie jest zaskakujący, jeśli porówna się go z ciągiem _liczb Fermata Fn ; liczby Fermata są zwykle definiowane za pomocą podwójnie wykładniczego wzoru , $również$ zdefiniować za pomocą wzoru iloczynu bardzo podobnego do Sekwencja Sylwestra:

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

Związek z frakcjami egipskimi

Ułamki jednostkowe utworzone przez odwrotności wartości w ciągu Sylwestra generują nieskończony szereg :

${\ Displaystyle \ suma _ {i = 0} ^ {\ infty} {\ Frac {1} {s_ {i}}} = {\ Frac {1} {2}} + {\ Frac {1} {3} }+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .}$

Sumy cząstkowe tego szeregu mają postać prostą,

${\ Displaystyle \ suma _ {i = 0} ^ {j-1} {\ Frac {1} {s_ {i}}} = 1 - {\ Frac {1} {s_ {j} -1}} = { \frac {s_{j}-2}{s_{j}-1}}.}$

Można to udowodnić przez indukcję lub bardziej bezpośrednio, zauważając, że implikuje to rekurencja

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

więc suma teleskopów

${\ Displaystyle \ suma _ {i = 0} ^ {j-1} {\ Frac {1} {s_ {i}}} = \ suma _ {i = 0} ^ {j-1} \ lewo ({\ 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}}.}$

Ponieważ ta sekwencja sum częściowych ( s _j - 2) / ( s _j - 1) zbiega się do jednego, ogólny szereg tworzy nieskończoną reprezentację ułamka egipskiego liczby jeden:

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

Można znaleźć skończone reprezentacje ułamków egipskich o dowolnej długości, obcinając ten szereg i odejmując jeden od ostatniego mianownika:

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

Suma pierwszych k wyrazów nieskończonego szeregu zapewnia najbliższe możliwe niedoszacowanie 1 przez dowolny k -członowy ułamek egipski. Na przykład pierwsze cztery wyrazy dodają się do 1805/1806, a zatem każdy ułamek egipski dla liczby w przedziale otwartym (1805/1806, 1) wymaga co najmniej pięciu wyrazów.

Ciąg Sylwestra można interpretować jako wynik zachłannego algorytmu dla ułamków egipskich , który na każdym kroku wybiera najmniejszy możliwy mianownik, który sprawia, że ​​suma cząstkowa szeregu jest mniejsza od jedności. Alternatywnie, wyrazy ciągu następujące po pierwszym można postrzegać jako mianowniki nieparzystej zachłannej ekspansji 1/2.

Wyjątkowość szybko rosnących szeregów o sumach wymiernych

Jak zauważył sam Sylvester, sekwencja Sylwestra wydaje się być wyjątkowa, ponieważ ma tak szybko rosnące wartości, a jednocześnie ma szereg odwrotności, które zbiegają się do liczby wymiernej . Ta sekwencja stanowi przykład pokazujący, że dwuwykładniczy wzrost nie wystarczy, aby sekwencja liczb całkowitych była sekwencją irracjonalności .

Aby to uściślić, z wyników Badei (1993) wynika , że ​​jeśli sekwencja liczb całkowitych rośnie wystarczająco szybko, że za $\ displaystyle a_ {n}}$

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

a jeśli seria

${\ Displaystyle A = \ suma {\ Frac {1} {a_ {i}}}}$

zbiega się do liczby wymiernej A , to dla wszystkich n po pewnym punkcie sekwencja ta musi być zdefiniowana przez tę samą rekurencję

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

które można wykorzystać do zdefiniowania sekwencji Sylwestra.

Erdős i Graham (1980) przypuszczali , że w wynikach tego typu nierówność ograniczającą wzrost ciągu można zastąpić słabszym warunkiem,

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

Badea (1995) bada postęp związany z tym przypuszczeniem ; patrz także Brown (1979) .

Podzielność i faktoryzacja

Jeżeli i < j , to z definicji wynika, że ​​s _j ≡ 1 (mod s _i ). Dlatego każde dwie liczby w ciągu Sylwestra są względnie pierwsze . Sekwencji można użyć do udowodnienia, że ​​istnieje nieskończenie wiele liczb pierwszych , ponieważ każda liczba pierwsza może dzielić co najwyżej jedną liczbę w ciągu. Co więcej, żaden czynnik pierwszy liczby w ciągu nie może być zgodny z 5 modulo 6, a ciąg może być użyty do udowodnienia, że ​​istnieje nieskończenie wiele liczb pierwszych zgodnych z 7 modulo 12.

Nierozwiązany problem z matematyki :

Czy wszystkie wyrazy ciągu Sylwestra są bezkwadratowe?

(więcej nierozwiązanych problemów z matematyki)

Wiele pozostaje nieznanych na temat faktoryzacji liczb w sekwencji Sylwestra. Na przykład nie wiadomo, czy wszystkie liczby w sekwencji są bezkwadratowe , chociaż wszystkie znane terminy są.

Jak opisuje Vardi (1991) , łatwo jest określić, którą liczbę Sylwestra (jeśli w ogóle) dzieli dana liczba pierwsza p : wystarczy obliczyć rekurencję definiującą liczby modulo p aż do znalezienia liczby, która jest zgodna z zerem (mod p ) lub znalezienia powtarzalny moduł. Korzystając z tej techniki, odkrył, że 1166 z pierwszych trzech milionów liczb pierwszych to dzielniki liczby Sylwestra i że żadna z tych liczb pierwszych nie ma kwadratu, który dzieli liczbę Sylwestra. Zbiór liczb pierwszych, które mogą występować jako czynniki liczb Sylwestra, ma gęstość zero w zbiorze wszystkich liczb pierwszych: w rzeczywistości liczba takich liczb pierwszych mniejsza niż x wynosi ${ \displaystyle O(\pi (x)/\log \log \log x)}$ .

Poniższa tabela przedstawia znane rozkłady na czynniki tych liczb (z wyjątkiem pierwszych czterech, z których wszystkie są liczbami pierwszymi):

N	Czynniki s n
4	13 × 139
5	3263443, czyli liczba pierwsza
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

Jak zwykle, Pn i Cn oznaczają liczby pierwsze i nierozkładane liczby złożone o długości n cyfr.

Aplikacje

Galicki i Kollár (2005) wykorzystują właściwości sekwencji Sylwestra do zdefiniowania dużej liczby rozmaitości Sasakian Einsteina o topologii różniczkowej sfer nieparzystowymiarowych lub sfer egzotycznych . Pokazują one, że liczba różnych metryk Sasakowskiego Einsteina na sferze topologicznej o wymiarze 2 n - 1 jest co najmniej proporcjonalna do s _n , a zatem ma podwójny wykładniczy wzrost wraz z n .

Jak opisują Galambos i Woeginger (1995) , Brown (1979) i Liang (1980) wykorzystali wartości pochodzące z sekwencji Sylwestra do skonstruowania przykładów dolnej granicy dla algorytmów pakowania w pojemniki online . Seiden i Woeginger (2005) podobnie wykorzystują tę sekwencję do dolnego ograniczenia wydajności dwuwymiarowego algorytmu materiału skrawającego.

Problem Známa dotyczy zbiorów liczb takich, że każda liczba w zbiorze dzieli się, ale nie jest równa iloczynowi wszystkich innych liczb plus jeden. Bez wymogu nierówności wartości w sekwencji Sylwestra rozwiązałyby problem; z tym wymaganiem ma inne rozwiązania wyprowadzone z nawrotów, podobne do tego, które definiuje sekwencję Sylwestra. Rozwiązania problemu Známa mają zastosowanie w klasyfikacji osobliwości powierzchniowych (Brenton i Hill 1988) oraz w teorii niedeterministycznych automatów skończonych .

DR Curtiss ( 1922 ) opisuje zastosowanie najbliższych przybliżeń do k - terminowych sum ułamków jednostkowych w dolnym ograniczeniu liczby dzielników dowolnej liczby doskonałej , a Miller (1919) używa tej samej własności do górnego ograniczenia rozmiaru pewnych grup .

Zobacz też

• stała Cahena
• Pierwotna liczba pseudodoskonała
• Numer Leonarda

Notatki

•   Badea, Catalin (1993). „Twierdzenie o irracjonalności nieskończonych szeregów i zastosowań” . Acta Arithmetica . 63 (4): 313–323. doi : 10.4064/aa-63-4-313-323 . MR 1218459 .
• Badea, Catalin (1995). „O niektórych kryteriach irracjonalności dla serii pozytywnych wymiernych: ankieta” (PDF) . Zarchiwizowane od oryginału (PDF) w dniu 11.09.2008 r.
•    Boyer, Karol P.; Galicki, Krzysztof; Kollár, János (2005). „Metryki Einsteina dotyczące sfer”. Roczniki matematyki . 162 (1): 557–580. arXiv : math.DG/0309408 . doi : 10.4007/annals.2005.162.557 . MR 2178969 . S2CID 13945306 .
•   Brenton, Lawrence; Hill, Richard (1988). „O równaniu diofantyny 1 = Σ1/ n _i + 1/Π n _i i klasie homologicznie trywialnych złożonych osobliwości powierzchniowych” . Pacific Journal of Mathematics . 133 (1): 41–67. doi : 10.2140/pjm.1988.133.41 . MR 0936356 .
• Brązowy, DJ (1979). „Dolna granica jednowymiarowych algorytmów pakowania w pojemniki on-line”. Technika Reprezentant R-864. Skoordynowane Laboratorium Naukowe, Univ. Illinois, Urbana-Champaign. {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
•   Curtiss, DR (1922). „O problemie diofantycznym Kellogga”. Amerykański miesięcznik matematyczny . 29 (10): 380–387. doi : 10.2307/2299023 . JSTOR 2299023 .
•   Domaracki, Michał; Ellul, Keith; Szallit, Jeffrey ; Wang, Ming-Wei (2005). „Nieunikalność i promień cyklicznych jednoargumentowych NFA” . Międzynarodowy Dziennik Podstaw Informatyki . 16 (5): 883–896. doi : 10.1142/S0129054105003352 . MR 2174328 .
•   Erdős, Paweł ; Graham, Ronald L. (1980). Stare i nowe problemy i wyniki kombinatorycznej teorii liczb . Monografie de L'Enseignement Mathématique, nr 28, Univ. de Genève. MR 0592420 .
•    Galambos, Gabor; Woeginger, Gerhard J. (1995). „Pakowanie do pojemników on-line - ankieta ograniczona” . Matematyczne metody badań operacyjnych . 42 (1): 25. doi : 10.1007/BF01415672 . MR 1346486 . S2CID 26692460 .
•    Golomb, Solomon W. (1963). „O pewnych nieliniowych powtarzających się sekwencjach”. Amerykański miesięcznik matematyczny . 70 (4): 403–405. doi : 10.2307/2311857 ​​. JSTOR 2311857 ​​. MR 0148605 .
•   Graham, R .; Knuth, DE ; Patashnik, O. (1989). Matematyka konkretna (wyd. 2). Addison-Wesley. Ćwiczenie 4.37. ISBN 0-201-55802-5 .
•    Facet, Richard K. (2004). „Sekwencje irracjonalności E24”. Nierozwiązane problemy w teorii liczb (wyd. 3). Springer-Verlag . P. 346. ISBN 0-387-20860-7 . Zbl 1058.11001 .
•   Facet, Richard; Nowakowski, Ryszard (1975). „Odkrywanie liczb pierwszych z Euclid”. Delta (Waukesha) . 5 (2): 49–63. MR 0384675 .
•   Jones, Rafe (2006). „Gęstość dzielników pierwszych w dynamice arytmetycznej wielomianów kwadratowych”. Journal of London Mathematical Society . 78 (2): 523–544. arXiv : math.NT/0612415 . Bibcode : 2006math.....12415J . doi : 10.1112/jlms/jdn034 . S2CID 15310955 .
•   Liang, Frank M. (1980). „Dolna granica pakowania w pojemniki on-line” . Listy dotyczące przetwarzania informacji . 10 (2): 76–79. doi : 10.1016/S0020-0190(80)90077-0 . MR 0564503 .
•   Miller, GA (1919). „Grupy posiadające niewielką liczbę zestawów operatorów sprzężonych” . Transakcje Amerykańskiego Towarzystwa Matematycznego . 20 (3): 260–270. doi : 10.2307/1988867 . JSTOR 1988867 .
•   Odoni, RWK (1985). „Na dzielnikach pierwszych ciągu w _n+1 =1+w ₁ ⋯w _n ”. Journal of London Mathematical Society . Seria II. 32 : 1–11. doi : 10.1112/jlms/s2-32.1.1 . Zbl 0574.10020 .
•   Rosenman, Marcin; Underwood, F. (1933). „Problem 3536”. Amerykański miesięcznik matematyczny . 40 (3): 180–181. doi : 10.2307/2301036 . JSTOR 2301036 .
•    Salzer, JE (1947). „Zbliżenie liczb jako sum odwrotności”. Amerykański miesięcznik matematyczny . 54 (3): 135–142. doi : 10.2307/2305906 . JSTOR 2305906 . MR 0020339 .
•    Seiden, Steven S.; Woeginger, Gerhard J. (2005). „Ponowne spojrzenie na dwuwymiarowy problem materiału tnącego”. Programowanie matematyczne . 102 (3): 519–530. doi : 10.1007/s10107-004-0548-1 . MR 2136225 . S2CID 35815524 .
• Soundararajan, K. (2005). „W przybliżeniu 1 od dołu przy użyciu n ułamków egipskich”. arXiv : math.CA/0502247 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
•   Sylwester, JJ (1880). „W punkcie w teorii ułamków wulgarnych”. American Journal of Mathematics . 3 (4): 332–335. doi : 10.2307/2369261 . JSTOR 2369261 .
•   Vardi, Ilan (1991). Rekreacje obliczeniowe w Mathematica . Addison-Wesley. s. 82–89. ISBN 0-201-52989-0 .

Linki zewnętrzne

• Irracjonalność sum kwadratowych , z MathPages KS Browna.
• Weisstein, Eric W. „Sekwencja Sylwestra” . MathWorld .