Sylvester sekvens

Sylvester-sekvensen  är en heltalssekvens där varje successiv medlem är lika med produkten av föregående medlemmar plus en. De första medlemmarna i sekvensen är:

2 , 3 , 7 , 43 , 1807, 3263443, 10650056950807, 113423713055421850000000000, … (sekvens A000058 i OEIS ).

Uppkallad efter James Sylvester , som först utforskade den 1880 . Värdena på dess termer växer som den dubbla exponenten , och summan av de ömsesidiga termerna bildar en serie bråkdelar av en som konvergerar till 1 snabbare än någon annan serie bråkdelar av en med samma antal termer. Upprepningsrelationen , som definierar termerna för sekvensen, gör att talen i sekvensen kan faktoriseras lättare än andra tal av samma ordning, men på grund av den mycket snabba tillväxten av termerna i serien, en fullständig faktorisering till primtal faktorer är kända endast för vissa medlemmar av denna sekvens. Värdena som erhålls med denna sekvens används för att bilda den slutliga representationen av 1 som en egyptisk bråkdel , Sasakian Einstein-grenrör och som en datakälla för onlinealgoritmer [ .

Formella definitioner

Formellt kan Sylvester-sekvensen definieras med formeln:

.

Produkten av elementen i den tomma mängden är lika med 1, så.

Ett annat sätt att definiera en sekvens är med en återkommande relation :

, var .

Likvärdigheten mellan definitionerna bevisas genom direkt induktion.

Allmän formel och asymptotik

Termerna för Sylvester-sekvensen växer i takt med den dubbla exponenten . I synnerhet kan det visas att:

där antalet är ungefär 1,264084735305302 [1] . Denna formel leder till följande algoritm :

s 0  är det närmaste heltal till E 2 ; s1 är  det närmaste heltal till E4 ; s2 är det närmaste  heltal till E8 ; för s n , ta E 2 , kvadrat det n gånger och ta närmaste heltal.

Denna algoritm skulle vara acceptabel om vi hade ett bättre sätt att beräkna E istället för att beräkna s n och sedan beräkna kvadratrötter .

Tillväxten av elementen i Sylvester-sekvensen med en dubbel exponentiell hastighet är inte alls förvånande jämfört med sekvensen av Fermat - tal Fn . Fermat-tal ges ofta av den dubbla exponentformeln , men de kan också ges av multiplikationsformler som liknar dem i Sylvester-sekvensen:

Koppling med egyptiska bråk

Bråkdelar av enhet , bildade av siffror som är ömsesidiga med värdena i Sylvester-sekvensen, bildar en oändlig serie :

Delsummorna i denna serie har den enkla formen

Detta kan bevisas genom induktion eller direkt genom att notera att rekursionen innebär

Således kommer summan av den teleskopiska raden att vara lika med

Eftersom sekvensen av partiella summor ( s j −2)/( s j −1) konvergerar till 1, bildar hela serien en oändlig egyptisk bråkrepresentation av 1 :

Man kan hitta de slutliga representationerna av enhet som en egyptisk bråkdel av valfri längd genom att avsluta denna serie och subtrahera en från den sista nämnaren:

Summan av de första k termerna i en oändlig serie ger den närmaste nedre gränsen för enhet i k -term egyptiska bråk. [2] Till exempel läggs de första fyra termerna till 1805/1806, så varje egyptisk bråkdel i det öppna intervallet (1805/1806.1) kräver minst fem termer.

Man kan tänka på Sylvester-sekvensen som resultatet av en girig algoritm för egyptiska bråk , som vid varje steg väljer den minsta möjliga divisor som lämnar delsumman mindre än en. Dessutom kan termerna i serien efter den första betraktas som delare av den giriga approximationen med udda tal av talet 1/2.

Det unika med snabbväxande serier med rationella summor

Som Sylvester själv noterade verkar Sylvester-sekvensen vara den enda som har en sådan tillväxthastighet, samtidigt som den konvergerar till ett rationellt tal. Denna sekvens visar ett exempel på att tillväxthastigheten för en dubbel exponent inte är tillräcklig för att en sekvens av heltal ska vara en rationell sekvens [3] .

Det följer av Badeas resultat [4] att om en sekvens av heltal växer tillräckligt snabbt så att

och om raden

konvergerar till ett rationellt tal A , sedan för alla n , utgående från någon plats, måste denna sekvens uppfylla återfallsrelationen

,

som kan användas för att bestämma Sylvester-sekvensen.

Erdős [5] antog att i resultat av denna typ kan gränsen för sekvenstillväxtojämlikheten ersättas av ett svagare tillstånd

Delbarhet och sönderdelning

Om i < j , följer det av definitionen att s j ≡ 1 (mod s i ). Sålunda är två valfria termer i Sylvester-sekvensen coprime . Sekvensen kan användas för att bevisa oändligheten av antalet primtal , eftersom vilket primtal som helst kan dela högst ett tal i sekvensen. Ingen primtalsfaktor för ett tal i sekvensen kan jämföras med 5 (mod 6), och sekvensen kan användas för att bevisa att det finns oändligt många primtal jämförbara med 7 (mod 12). [6]

Olösta problem i matematik : Är alla termer i Sylvestersekvensen fria från kvadrater ?

Mycket är fortfarande okänt om faktoriseringen av termerna för Sylvester-sekvensen. Till exempel är det inte känt om alla medlemmar av sekvensen är kvadratfria , även om alla termer för vilka primtalsfaktorisering är känd är det.

Som Vardi ( 1991 ) skriver är det lätt att avgöra vilka av termerna i Sylvester-sekvensen (om några) som är delbara med ett primtal p  - beräkna bara resterna av termerna i sekvensen mod p enligt den rekursiva formeln tills noll (mod p ) påträffas eller samma återstod. Med denna teknik fann Vardy att 1166 av de första miljonerna primtal är divisorer av Sylvestertalen, [7] och ingen kvadrat av dessa primtal delar Sylvestertalen. Uppsättningen av primtal som kan vara delare av termerna i Sylvester-serien har densitet noll i uppsättningen av alla primtal. Dessutom, enligt Jones [8] är antalet sådana primtal mindre än x lika med . [9]

Följande tabell listar de kända expansionerna av dessa tal (med undantag för de fyra första, som är primtal): [10]

n Faktorer s n
fyra 13×139
5 3263443, enkelt
6 547×607×1033×31051
7 29881 × 67003 × 9119521 × 6212157481
åtta 5295435634831 × 31401519357481261 × 77366930214021991992277
9 181  × 1 987
tio 2287 × 2271427 × 21430986826194127130578627950810640891005487 × P156
elva 73  × C416
12 2589377038614498251653 × 2872413602289671035947763837 × C785
13 52387 × 5020387 × 5783021473 × 401472621488821859737 × 287001545675964617409598279 × C1600
fjorton 13999 × 74203 × 9638659 × 57218683 × 10861631274478494529 × C3293
femton 17881 × 97822786011310111 × 54062008753544850522999875710411 × C6618
16 128551 × C13335
17 635263 × 1286773 × 21269959 × C26661
arton 50201023123 × 139263586549 × 60466397701555612333765567 × C53313
19 775608719589345260583891023073879169 × C106685
tjugo 352867 × 6210298470888313 × C213419
21 387347773 × 1620516511 × C426863
22 91798039513 × C853750

Här betecknar P n och C n primtal och sammansatta tal med n decimalsiffror.

Applikationer

Boyer, Galicki och Kollár ( Boyer, Galicki, Kollár 2005 ) använde egenskaperna hos Sylvester-sekvensen för att definiera ett stort antal Sasakian Einstein-grenrör som har differentialtopologin för udda-dimensionella sfärer eller exotiska sfärer . De visade att antalet olika Sasakian Einstein-mått på en topologisk sfär med dimensionen 2 n − 1 är åtminstone proportionell mot s n , och därför växer med en hastighet av dubbel exponentiell (från n ).

Som Galambos och Woeginger ( 1995 ) skriver använde Brown ( Brown 1979 ) och Liang ( Liang 1980 ) värden härledda från Sylvester-sekvensen för att konstruera exempel på en nedre gräns för online ] containerpackningsalgoritmer . Seiden och Woeginger ( Seiden, Woeginger 2005 ) använde på liknande sätt en sekvens för den lägre prestandagränsen för 2D - kapslingsalgoritmen [11] .

Znams problem handlar om uppsättningar av tal så att varje tal i mängden delar, men inte är lika med, produkten av alla andra mängder plus ett. Utan ekvivalensvillkoret löser Sylvester-sekvensvärdena detta problem. Om detta villkor är inställt, finns det en annan lösning som erhålls från en återfallsrelation som liknar definitionen av Sylvester-sekvensen. Lösningar på Znam-problemet har tillämpningar på klassificeringen av singulära punkter på ytor (Brenton, Hill 1988) och teorin om icke-deterministiska finita automater . [12]

Curtis ( Curtiss 1922 ) beskriver tillämpningen av den närmaste approximationen till enhet med k -term summor av bråkdelar av enhet till en nedre gräns för antalet divisorer av ett perfekt tal , och Müller ( Miller 1919 ) använder samma egenskap för ett lägre bunden på antalet av vissa grupper .

Se även

Anteckningar

  1. ↑ I Graham, Knuth och Patashnik ( 1989 ) ges detta uttalande som en övning. Se även Golomb ( Golomb 1963 ).
  2. ↑ Detta påstående tillskrivs vanligtvis Curtis ( Curtiss 1922 ), men Miller ( Miller 1919 ) gjorde samma påstående i ett tidigare verk. Se även Rosenman och Underwood 1933 , Salzer 1947 och ( Soundararajan 2005 ).
  3. ↑ Guy, 2004 .
  4. ↑ ( Badea 1993 )
  5. ↑ ( Erdős 1980 ), för en genomgång av arbeten om denna hypotes - ( Badea 1995 ), se även Brown, 1979 .
  6. ↑ Guy, Nowakowski, 1975 .
  7. ↑ Det verkar finnas ett stavfel här, eftersom Andersen hittade 1167 primtalare i detta intervall.
  8. ↑ Jones, 2006 .
  9. ↑ Odoni, 1985 .
  10. ↑ Alla primtalsfaktorer p av Sylvestertal s n med p < 5⋅10 7 och n ≤ 200 är listade av Vardy. Ken Takusagawa listade expansioner upp till 9 Arkiverad 25 december 2014 på Wayback Machine och expansioner 10 Arkiverade 25 december 2014 på Wayback Machine . De återstående expansionerna är hämtade från listan över expansioner av Sylvester-sekvensen Arkiverad 29 november 2014 på Wayback Machine , underhållen av Jens Kruse Andersen. Från och med 2014-06-13.
  11. ↑ I sin tidning hänvisar Seiden och Voginger till Sylvester-sekvensen som "Salzer-sekvensen", som bygger på Salzers arbete ( Salzer 1947 ) på närmaste approximation.
  12. ↑ Domaratzki, Ellul, Shallit, Wang, 2005 .

Litteratur

Länkar