Sekvence Sylvesters - Sylvesters sequence - Wikipedia

Grafické znázornění konvergence součtu 1/2 + 1/3 + 1/7 + 1/43 + ... k 1. Každý řádek k čtverce délky strany 1 /k má celkovou plochu 1 /ka všechny čtverce společně přesně pokrývají větší čtverec s plochou 1. Čtverce s délkou strany 1/1807 nebo menší jsou příliš malé, aby je bylo možné vidět na obrázku, a nejsou zobrazeny.

v teorie čísel, Sylvestrova sekvence je celočíselná sekvence ve kterém je každý člen posloupnosti výsledkem předchozích výrazů plus jeden. Prvních několik termínů sekvence je

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

Sylvesterova sekvence je pojmenována po James Joseph Sylvester, který to poprvé prozkoumal v roce 1880. Jeho hodnoty rostou dvojnásobně exponenciálně a součet jeho reciproční tvoří a série z jednotkové zlomky který konverguje k 1 rychleji než jakákoli jiná řada jednotkových zlomků se stejným počtem členů. The opakování kterým je definována, umožňuje být čísla v pořadí započteno snadněji než jiná čísla stejné velikosti, ale díky rychlému růstu sekvence úplná primární faktorizace jsou známé pouze pro několik jejích výrazů. Hodnoty odvozené z této sekvence byly také použity ke konstrukci konečné Egyptská část reprezentace 1, Sasakian Einsteinova potrubí a těžké instance pro online algoritmy.

Formální definice

Formálně lze Sylvestrovu sekvenci definovat podle vzorce

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

The produkt prázdné sady je 1, takže s₀ = 2.

Alternativně lze definovat sekvenci pomocí opakování

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

Je to jednoduché ukázat indukce že je to ekvivalentní s druhou definicí.

Vzorec uzavřené formy a asymptotika

Čísla Sylvestrů rostou dvojnásobně exponenciálně jako funkce n. Konkrétně lze ukázat, že

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

pro číslo E to je přibližně 1,26408473530530 ...^[1] (sekvence A076393 v OEIS ). Tento vzorec má následující účinek algoritmus:

s₀ je nejbližší celé číslo na E²; s₁ je nejbližší celé číslo E⁴; s₂ je nejbližší celé číslo E⁸; pro s_n, vzít E², srovnejte to n vícekrát a vezměte nejbližší celé číslo.

To by byl praktický algoritmus, jen kdybychom měli lepší způsob výpočtu E na požadovaný počet míst než výpočet s_n a jeho opakování odmocnina.

Dvojitý exponenciální růst Sylvestrovy sekvence není překvapující, pokud ji porovnáme se sekvencí Fermat čísla F_n; Fermatova čísla jsou obvykle definována dvojnásobně exponenciálním vzorcem, ${ displaystyle 2 ^ {2 ^ {n}} + 1}$, ale mohou být také definovány produktovým vzorcem velmi podobným tomu, který definuje Sylvestrovu sekvenci:

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

Spojení s egyptskými frakcemi

The jednotkové zlomky vytvořený reciproční hodnot v sekvenci Sylvestera vygeneruje nekonečná řada:

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

The částečné částky této série mají jednoduchou formu,

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

To může být prokázáno indukcí nebo více přímo poznámkou, že to znamená rekurze

${ displaystyle { frac {1} {s_ {i} -1}} - { frac {1} {s_ {i + 1} -1}} = { frac {1} {s_ {i}}} ,}$

takže součet dalekohledy

${ displaystyle 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 tato posloupnost částečných součtů (s_j − 2)/(s_j - 1) konverguje k jedné, celková řada tvoří nekonečno Egyptská část reprezentace jedničky:

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

Lze najít konečné egyptské zlomkové reprezentace jedné libovolné délky zkrácením této řady a odečtením jedné od posledního jmenovatele:

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

Součet prvního k podmínky nekonečné řady poskytují nejbližší možné podhodnocení 1 kterýmkoli k- přechodná egyptská část.^[2] Například první čtyři výrazy se přidají k 1805/1806, a tedy jakýkoli egyptský zlomek pro číslo v otevřený interval (1805/1806, 1) vyžaduje alespoň pět termínů.

Je možné interpretovat Sylvestrovu sekvenci jako výsledek a chamtivý algoritmus pro egyptské zlomky, že v každém kroku zvolí nejmenší možný jmenovatel, díky kterému je dílčí součet řady menší než jeden. Alternativně lze pojmy posloupnosti za první považovat za jmenovatele zvláštní chamtivá expanze 1/2.

Jedinečnost rychle rostoucích sérií s racionálními částkami

Jak poznamenal sám Sylvester, zdá se, že Sylvestrova sekvence je jedinečná v tom, že má tak rychle rostoucí hodnoty a současně má řadu recipročních, které konvergují racionální číslo. Tato posloupnost poskytuje příklad, který ukazuje, že dvojitý exponenciální růst nestačí k tomu, aby celočíselná posloupnost byla posloupnost iracionality.^[3]

Abychom to zpřesnili, vyplývá to z výsledků Badea (1993) to, pokud posloupnost celých čísel ${ displaystyle a_ {n}}$ roste dostatečně rychle na to

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

a pokud série

${ displaystyle A = sum { frac {1} {a_ {i}}}}$

konverguje na racionální číslo Apak tedy pro všechny n po určitém okamžiku musí být tato sekvence definována stejným opakováním

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

které lze použít k definování Sylvestrovy sekvence.

Erdős & Graham (1980) domnělý že ve výsledcích tohoto typu může být nerovnost ohraničující růst posloupnosti nahrazena slabší podmínkou,

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

Badea (1995) průzkumy pokroku souvisejícího s touto domněnkou; viz také Brown (1979).

Dělitelnost a faktorizace

Li i < j, z definice vyplývá, že s_j ≡ 1 (mod s_i). Proto jsou každé dvě čísla v posloupnosti Sylvestera relativně prime. Sekvence může být použita k prokázání, že jich je nekonečně mnoho prvočísla, protože libovolné prvočíslo může rozdělit nanejvýš jedno číslo v pořadí. Více silně, žádný primární faktor čísla v posloupnosti nemůže být shodný s 5 modulo 6, a posloupnost může být použita k prokázání, že existuje nekonečně mnoho prvočísel shodných se 7 modulo 12.^[4]

Nevyřešený problém v matematice: Jsou všechny výrazy v Sylvestrově sekvenci čtvercové? (více nevyřešených úloh z matematiky)

O faktorizaci čísel v Sylvestrově posloupnosti zůstává mnoho neznámého. Například není známo, zda jsou všechna čísla v pořadí bez čtverce, i když všechny známé výrazy jsou.

Tak jako Vardi (1991) popisuje, je snadné určit, které Sylvesterovo číslo (pokud existuje) dané prvočíslo p dělí: jednoduše spočítejte opakování definující čísla modulo p dokud nenajdete číslo, které je shodné s nulou (mod p) nebo nalezení opakovaného modulu. Pomocí této techniky zjistil, že 1166 z prvních tří milionů prvočísel jsou dělitele čísel Sylvester,^[5] a že žádná z těchto prvočísel nemá čtverec, který rozděluje Sylvestrovo číslo. Sada prvočísel, která mohou nastat jako faktory Sylvestrova čísla, má v sadě všech prvočísel nulovou hustotu:^[6] ve skutečnosti je počet takových prvočísel menší než X je ${ displaystyle O ( pi (x) / log log log x)}$.^[7]

Následující tabulka ukazuje známé faktorizace těchto čísel (kromě prvních čtyř, které jsou všechny prvočíselné):^[8]

Jak je obvyklé, P.n a C.n označit prime a kompozitní čísla n dlouhé číslice.

Aplikace

Boyer, Galicki & Kollár (2005) použijte vlastnosti Sylvestrovy sekvence k definování velkého počtu Sasakian Einsteinova potrubí mít diferenciální topologie liché-dimenzionální koule nebo exotické sféry. Ukazují, že počet zřetelných Sasakian Einstein metriky na topologická sféra dimenze 2n - 1 je alespoň úměrný s_n a proto má dvojnásobný exponenciální růst s n.

Tak jako Galambos & Woeginger (1995) popsat, Brown (1979) a Liang (1980) použité hodnoty odvozené ze Sylvestrovy sekvence byly použity ke konstrukci příkladů dolní hranice pro online balení koše algoritmy. Seiden & Woeginger (2005) podobně použijte sekvenci ke snížení meze výkonu algoritmu dvourozměrného řezného materiálu.^[9]

Známův problém obavy sady čísel tak, že každé číslo v sadě rozděluje, ale nerovná se součinu všech ostatních čísel plus jedno. Bez požadavku nerovnosti by hodnoty v Sylvestrově posloupnosti problém vyřešily; s tímto požadavkem má další řešení odvozená z opakování podobných tomu, které definuje Sylvestrovu sekvenci. Řešení Známova problému mají uplatnění v klasifikaci povrchových singularit (Brenton a Hill 1988) a v teorii nedeterministické konečné automaty.^[10]

D. R. Curtiss  (1922 ) popisuje aplikaci nejbližších aproximací jedné z k-časové součty jednotkových zlomků, v dolním ohraničení počet dělitelů libovolných perfektní číslo, a Miller (1919) používá stejnou vlastnost horní hranice velikost jisté skupiny.

Viz také

• Cahenova konstanta
• Primární pseudoperfektní číslo

Poznámky

Reference

externí odkazy

• Iracionalita kvadratických součtů, od K. S. Browna MathPages.
• Weisstein, Eric W. „Sylvestrova sekvence“. MathWorld.