Silvestrovská sekvence

Sylvesterova posloupnost je celočíselná posloupnost , ve které je každý následující člen roven součinu předchozích členů plus jedna. Prvních několik členů sekvence je:

2 , 3 , 7 , 43 , 1807, 3263443, 10650056950807, 113423713055421850000000000, … (sekvence A000058 v OEIS ).

Pojmenovaný po Jamesi Sylvesterovi , který jej poprvé prozkoumal v roce 1880 . Hodnoty jejích členů rostou jako dvojitý exponent a součet reciprokých členů tvoří řadu zlomků jedničky , která konverguje k 1 rychleji než jakákoli jiná řada zlomků jedničky se stejným počtem členů. Rekurentní vztah , který definuje členy posloupnosti, umožňuje, aby čísla v posloupnosti byla rozdělena snadněji než jiná čísla stejného řádu, ale vzhledem k velmi rychlému nárůstu členů řady, kompletní rozklad na prvočíslo faktory jsou známy pouze pro některé členy této sekvence. Hodnoty získané pomocí této sekvence jsou použity k vytvoření konečné reprezentace 1 jako egyptského zlomku , sasakovského Einsteinova manifoldu a jako zdroj dat pro online algoritmy .

Formální definice

Formálně může být Sylvesterova sekvence definována vzorcem:

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

Součin prvků prázdné množiny je roven 1, takže. $s_{0}=2$

Dalším způsobem, jak definovat sekvenci, je vztah opakování :

\displaystyle s_{i}=s_{i-1}(s_{i-1}-1)+1

, kde .

s_{0}=2

Ekvivalence definic se dokazuje přímou indukcí.

Obecný vzorec a asymptotika

Členy posloupnosti Sylvester rostou rychlostí dvojitého exponentu . Zejména lze prokázat, že:

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

kde číslo je přibližně 1,264084735305302 [1] . Tento vzorec vede k následujícímu algoritmu : $E$

s 0 je nejbližší celé číslo k E2 ; s1 je nejbližší celé číslo k E4 ; s2 je nejbližší celé číslo k E8 ; pro s n vezměte E 2 , umocněte jej nkrát a vezměte nejbližší celé číslo.

Tento algoritmus by byl přijatelný, kdybychom měli lepší způsob, jak vypočítat E namísto počítání sn a následného počítání odmocnin .

Růst prvků Sylvesterovy posloupnosti dvojnásobnou exponenciální rychlostí není vůbec překvapivý ve srovnání s posloupností Fermatových čísel Fn . Fermatova čísla jsou často dána vzorcem s dvojitým exponentem , ale mohou být také dána vzorcem pro násobení podobným těm ze Sylvesterovy posloupnosti: $2^{{2^{n}}}+1$

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

Spojení s egyptskými zlomky

Zlomky jednoty , tvořené čísly reciproční k hodnotám Sylvesterovy sekvence, tvoří nekonečnou řadu :

\sum _{i=0}^{\infty }{\frac {1}{s_{i))}={\frac {1}{2))+{\frac {1}{3} }+{\frac {1}{7}}+{\frac {1}{43}}+{\frac {1}{1807}}+\cdots .

Dílčí součty této řady mají jednoduchý tvar

\sum _{i=0}^{j-1}{\frac {1}{s_{i}}}=1-{\frac {1}{s_{j}-1}}={ \frac {s_{j}-2}{s_{j}-1}}.

To lze dokázat indukcí nebo přímo poznámkou, že rekurze implikuje

{\frac {1}{s_{i}-1}}-{\frac {1}{s_{i+1}-1}}={\frac {1}{s_{i}}} ,

Tedy součet teleskopické řady bude roven

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

Protože posloupnost dílčích součtů ( s j −2)/( s j −1) konverguje k 1, celá řada tvoří nekonečnou egyptskou zlomkovou reprezentaci 1 :

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

Konečné znázornění jednoty lze najít jako egyptský zlomek libovolné délky ukončením této řady a odečtením jednoho od posledního jmenovatele:

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 .

Součet prvních k členů nekonečné řady dává nejbližší dolní mez pro jednotu v egyptských zlomcích k -term. [2] Například první čtyři členy jsou přidány k 1805/1806, takže jakýkoli egyptský zlomek v otevřeném intervalu (1805/1806.1) vyžaduje alespoň pět členů.

Sylvesterovu posloupnost si lze představit jako výsledek chamtivého algoritmu pro egyptské zlomky , který v každém kroku volí nejmenšího možného dělitele, který ponechá částečný součet menší než jedna. Také členy řady po prvním lze považovat za dělitele chamtivé aproximace lichými čísly čísla 1/2.

Jedinečnost rychle rostoucích řad s racionálními součty

Jak sám Sylvester poznamenal, sekvence Sylvester se zdá být jedinou, která má takové tempo růstu, a přitom konverguje k racionálnímu číslu. Tato posloupnost ukazuje příklad, že rychlost růstu dvojitého exponentu není dostatečná, aby posloupnost celých čísel byla racionální posloupností [3] .

Z Badeova výsledku [4] vyplývá, že pokud posloupnost celých čísel roste dostatečně rychle tak, že $a_n$

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

a pokud řada

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

konverguje k racionálnímu číslu A , pak pro všechna n , počínaje od nějakého místa, musí tato posloupnost splňovat rekurenci opakování

a_{n}=a_{n-1}^{2}-a_{n-1}+1

které lze použít k určení Sylvesterovy posloupnosti.

Erdős [5] předpokládal , že ve výsledcích tohoto typu může být hranice sekvenční růstové nerovnosti nahrazena slabší podmínkou

\lim _{n\rightarrow \infty }{\frac {a_{n}}{a_{n-1}^{2}}}=1.

Dělitelnost a rozklad

Pokud i < j , z definice vyplývá, že s j ≡ 1 (mod s i ). Tak nějaké dva termíny Sylvester sekvence jsou coprime . Posloupnost může být použita k prokázání nekonečnosti počtu prvočísel , protože jakékoli prvočíslo může dělit nejvýše jedno číslo v posloupnosti. Žádný prvočinitel čísla v posloupnosti nelze přirovnat k 5 (mod 6) a posloupnost lze použít k prokázání, že existuje nekonečně mnoho prvočísel srovnatelných s 7 (mod 12). [6]

Nevyřešené úlohy v matematice : Jsou všechny členy Sylvesterovy posloupnosti bez čtverců ?

O faktorizaci podmínek Sylvesterovy sekvence zůstává mnoho neznámého. Například není známo, zda jsou všechny členy posloupnosti bez čtverců , ačkoli všechny termíny, pro které je známa rozklad na prvočíslo, ano.

Jak píše Vardi ( 1991 ), je snadné určit, který z členů Sylvesterovy posloupnosti (pokud existuje) je dělitelný prvočíslem p – stačí vypočítat zbytky členů posloupnosti mod p podle rekurzivního vzorce, dokud nula (mod p ) nebo stejný zbytek. Pomocí této techniky Vardy zjistil, že 1166 z prvního milionu prvočísel jsou dělitelé Sylvesterových čísel [7] a žádná druhá mocnina těchto prvočísel nedělí Sylvestrova čísla. Množina prvočísel, která mohou být děliteli členů řady Sylvester, má v množině všech prvočísel hustotu nulu. Navíc podle Jonese [8] je počet takových prvočísel menších než x roven . [9] $O(\pi (x)/\log \log \log x)$

V následující tabulce jsou uvedeny známé expanze těchto čísel (s výjimkou prvních čtyř, která jsou prvočísla): [10]

n	Faktory s n
čtyři	13×139
5	3263443, jednoduché
6	547×607×1033×31051
7	29881 × 67003 × 9119521 × 6212157481
osm	5295435634831 × 31401519357481261 × 77366930214021991992277
9	181 × 1987 × 112374829138729 × 114152531605972711 × 3587438027224662415276456919113489495559726595691448
deset	2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
jedenáct	73 × C416
12	2589377038614498251653 × 2872413602289671035947763837 × C785
13	52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
čtrnáct	13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
patnáct	17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16	128551 × C13335
17	635263 × 1286773 × 21269959 × C26661
osmnáct	50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19	775608719589345260583891023073879169 × C106685
dvacet	352867 × 6210298470888313 × C213419
21	387347773 × 1620516511 × C426863
22	91798039513 × C853750

Zde P n a C n označují prvočísla a složená čísla s n desetinnými číslicemi.

Aplikace

Boyer, Galicki a Kollár ( Boyer, Galicki, Kollár 2005 ) použili vlastnosti Sylvesterovy posloupnosti k definování velkého množství sasakiánských Einsteinových variet , které mají diferenciální topologii lichých-rozměrných koulí nebo exotických koulí . Ukázali, že počet různých sasakiánských Einsteinových metrik na topologické sféře dimenze 2 n − 1 je alespoň úměrný s n , a proto roste rychlostí dvojnásobné exponenciály (z n ).

Jak píší Galambos a Woeginger ( 1995 ), Brown ( Brown 1979 ) a Liang ( Liang 1980 ) použili hodnoty odvozené ze sekvence Sylvester ke konstrukci příkladů spodní hranice pro online algoritmy balení kontejnerů . Seiden a Woeginger ( Seiden, Woeginger 2005 ) podobně použili sekvenci pro dolní hranici výkonu algoritmu 2D vnořování [11] .

Znamův problém je o množinách čísel tak, že každé číslo v množině dělí, ale není rovno, součin všech ostatních množin plus jedna. Bez podmínky ekvivalence tento problém řeší hodnoty sekvence Sylvester. Je-li tato podmínka nastavena, existuje další řešení získané z rekurentního vztahu podobného definici Sylvesterovy posloupnosti. Řešení problému Znam mají aplikace pro klasifikaci singulárních bodů povrchů (Brenton, Hill 1988) a teorii nedeterministických konečných automatů . [12]

Curtis ( Curtiss 1922 ) popisuje aplikaci nejbližší aproximace k jednotě pomocí k - term součtů zlomků jednoty na spodní hranici počtu dělitelů libovolného dokonalého čísla a Müller ( Miller 1919 ) používá stejnou vlastnost pro nižší vázaný na počet některých skupin .

Viz také

Caenova konstanta
Jednoduché pseudodokonalé číslo

Poznámky

↑ V Graham, Knuth a Patashnik ( 1989 ) je toto tvrzení uvedeno jako cvičení. Viz také Golomb ( Golomb 1963 ).
↑ Tento nárok je obvykle připisován Curtisovi ( Curtiss 1922 ), ale Miller ( Miller 1919 ) učinil stejný nárok v dřívější práci. Viz také Rosenman a Underwood 1933 , Salzer 1947 a ( Soundararajan 2005 ).
↑ Chlap, 2004 .
↑ ( Badea 1993 )
↑ ( Erdős 1980 ), přehled prací o této hypotéze - ( Badea 1995 ), viz také Brown, 1979 .
↑ Guy, Nowakowski, 1975 .
↑ Zdá se, že zde došlo k překlepu, protože Andersen našel v tomto rozsahu 1167 prvočíselných dělitelů.
↑ Jones, 2006 .
↑ Odoni, 1985 .
↑ Všechny prvočinitele p Sylvesterových čísel s n s p < 5⋅10 7 an ≤ 200 uvádí Vardy. Ken Takusagawa uvedl rozšíření až do s 9 Archivováno 25. prosince 2014 na Wayback Machine a rozšíření s 10 Archivováno 25. prosince 2014 na Wayback Machine . Zbývající rozšíření jsou převzata ze seznamu rozšíření sekvence Sylvester Archived 29. listopadu 2014 na Wayback Machine , kterou spravuje Jens Kruse Andersen. Stav ke dni 13.6.2014.
↑ Seiden a Voginger ve svém článku odkazují na Sylvesterovu sekvenci jako na „Salzerovu sekvenci“, přičemž staví na Salzerově práci ( Salzer 1947 ) na nejbližší aproximaci.
↑ Domartzki, Ellul, Shallit, Wang, 2005 .

Literatura

Catalin Badea. Věta o iracionalitě nekonečných řad a aplikací // Acta Arithmetica . - 1993. - T. 63 . - S. 313-323 .
Badea, Catalin. O některých kritériích iracionality pro řadu pozitivních zdůvodnění: průzkum (anglicky) . — 1995.
Charles P. Boyer, Krzysztof Galicki, János Kollár. Einsteinovy metriky na sférách // Annals of Mathematics . - 2005. - T. 162 , čís. 1 . - S. 557-580 . - doi : 10.4007/annals.2005.162.557 . — arXiv : math.DG/0309408 .
Lawrence Brenton, Richard Hill. K diofantické rovnici 1=Σ1/ n i + 1/Π n i a třídě homologicky triviálních komplexních povrchových singularit // Pacific Journal of Mathematics . - 1988. - T. 133 , čís. 1 . - S. 41-67 . - doi : 10.2140/pjm.1988.133.41 .
DJ Brown. Dolní mez pro on-line jednorozměrné algoritmy balení do přihrádek. — Coordinated Science Lab., Univ. of Illinois, Urbana-Champaign, 1979. - Sv. Tech. Rep. R-864 .
D. R. Curtis. O Kelloggově diofantickém problému // American Mathematical Monthly . - 1922. - T. 29 , čís. 10 . - S. 380-387 . - doi : 10.2307/2299023 . — .
Michael Domaratzki, Keith Ellul, Jeffrey Shallit, Ming-Wei Wang. Nejedinečnost a poloměr cyklických unárních NFA // International Journal of Foundations of Computer Science. - 2005. - T. 16 , no. 5 . - S. 883-896 . - doi : 10.1142/S0129054105003352 .
Paul Erdős, Ronald L. Graham. Staré a nové problémy a výsledky v kombinatorické teorii čísel. — Monografie de L'Enseignement Mathematique, no. 28, Univ. de Geneve, 1980.
Gábor Galambos, Gerhard J. Woeginger. On-line bin packing - omezený průzkum // Matematické metody operačního výzkumu. - 1995. - Sv. 42 , iss. 1 . — S. 25 . - doi : 10.1007/BF01415672 .
Solomon W. Golomb. Na určitých nelineárních opakujících se sekvencích // American Mathematical Monthly. - 1963. - T. 70 , čís. 4 . - S. 403-405 . - doi : 10.2307 / 2311857 — _
R. Graham, D. E. Knuth, O. Patashnik. Konkrétní matematika. — 2. - Addison-Wesley, 1989. - ISBN 0-201-55802-5 .
Richard K Guy. Nevyřešené problémy v teorii čísel. — 3. - Springer-Verlag , 2004. - S. 346. - ISBN 0-387-20860-7 .
Richard Guy, Richard Nowakowski. Objevování prvočísel s Euklidem // Delta (Waukesha). - 1975. - V. 5 , čís. 2 . - S. 49-63 .
Rafe Jones. Hustota prvočíselných dělitelů v aritmetické dynamice kvadratických polynomů . - 2006. - arXiv : math.NT/0612415 .
Frank M. Liang. Dolní hranice pro online balení do popelnic // Dopisy pro zpracování informací. - 1980. - T. 10 , no. 2 . - S. 76-79 . - doi : 10.1016/S0020-0190(80)90077-0 .
GA Miller. Skupiny vlastnící malý počet sad konjugovaných operátorů // Transactions of the American Mathematical Society . - 1919. - Sv. 20 , iss. 3 . - S. 260-270 . - doi : 10.2307/1988867 . — .
RWK Odoni. Na prvočíselných dělitelích posloupnosti w n+1 =1+w 1 ⋯ w n // J. Lond. Matematika. soc., II. Ser.. - 1985. - T. 32 . - S. 1-11 .
Martin Rosenman, F. Underwood. Úloha 3536 // Americký matematický měsíčník. - 1933. - T. 40 , čís. 3 . - S. 180-181 . — .
H. E. Salzer. Aproximace čísel jako součtů převrácených hodnot // American Mathematical Monthly. - 1947. - T. 54 , čís. 3 . - S. 135-142 . - doi : 10.2307/2305906 . — .
Steven S. Seiden, Gerhard J. Woeginger. Znovu se vrátil problém dvourozměrného řezného materiálu // Matematické programování. - 2005. - T. 102 , no. 3 . - S. 519-530 . - doi : 10.1007/s10107-004-0548-1 .
K. Soundarajan. Aproximace 1 zdola pomocí n egyptských zlomků. - 2005. - arXiv : math.CA/0502247 .
JJ Sylvester. K bodu v teorii vulgárních zlomků // American Journal of Mathematics . - 1880. - T. 3 , čís. 4 . - S. 332-335 . - doi : 10.2307/2369261 . — .
Ilan Vardi. Výpočetní rekreace v Mathematice. - Addison-Wesley, 1991. - S. 82-89. - ISBN 0-201-52989-0 .

Odkazy

Iracionalita kvadratických součtů z MathPages KS Browna.
Weisstein, Eric W. Sylvester's Sequence (anglicky) na webových stránkách Wolfram MathWorld .