Gijswijts sekvens
Inom matematik är Gijswijts sekvens (uppkallad efter Dion Gijswijt av Neil Sloane ) en självbeskrivande sekvens där varje term räknar det maximala antalet upprepade block av siffror i sekvensen omedelbart före den termen .
Sekvensen börjar med:
Sekvensen liknar definitionen av Kolakoski-sekvensen , men istället för att räkna den längsta serien av enstaka termer, räknar sekvensen den längsta serien av block av termer oavsett längd. Gijswijts sekvens är känd för sin anmärkningsvärt långsamma tillväxttakt. Till exempel, de första 4 visas vid den 220:e termen, och de första 5 visas nära den e termen.
Definition
Processen för att generera termer i sekvensen kan definieras genom att se sekvensen som en serie bokstäver i alfabetet av naturliga siffror :
- , och
- , där är det största naturliga talet så att ordet kan skrivas i formen för vissa ord och , där har en längd som inte är noll.
Sekvensen är basagnostisk . Det vill säga, om en körning av 10 upprepade block hittas, skulle nästa term i sekvensen vara ett enda nummer 10, inte en 1 följt av en 0.
Förklaring
Sekvensen börjar med 1 per definition. 1:an i den andra termen representerar då längden 1 av blocket av 1:or som finns omedelbart före den i den första termen. 2:an i den tredje termen representerar längden 2 av blocket av 1:or som finns i den första och andra termen. Vid denna tidpunkt minskar sekvensen för första gången: 1:an i den fjärde termen representerar längden 1 av blocket av 2s i den 3:e termen, såväl som längden 1 av blocket "1, 2" som spänner över den andra och tredje mandatperioden. Det finns inget block av någon upprepad sekvens omedelbart före den fjärde termen som är längre än längd 1. Blocket med två ettor i den första och andra termen kan inte övervägas för den fjärde termen eftersom de är åtskilda med ett annat nummer i den 3:e termen .
1:an i den femte termen representerar längden 1 av de "upprepande" blocken "1" och "2, 1" och "1, 2, 1" och "1, 1, 2, 1" som omedelbart föregår den femte termen. Inget av dessa block upprepas mer än en gång, så den femte termen är 1. 2:an i den sjätte termen representerar längden på det upprepade blocket av 1:or som omedelbart leder fram till den sjätte termen, nämligen de i 4:e och 5:e termen. 2:an i den sjunde termen representerar de 2 upprepningarna av blocket "1, 1, 2" som spänner över termerna 1-3 och sedan 4-6. Detta "3-talsord" förekommer två gånger omedelbart fram till den sjunde termen - så värdet på den sjunde termen är 2.
2:an i den åttonde termen representerar längden på det upprepade blocket av 2:or omedelbart fram till den åttonde termen, nämligen tvåorna i sjätte och sjunde termen. 3:an i den 9:e termen representerar det tre gånger upprepade blocket av enstaka 2:or omedelbart fram till den 9:e termen, nämligen tvåorna i sjätte, sjunde och åttonde termen.
Egenskaper
Endast begränsad forskning har fokuserat på Gijswijts sekvens. Som sådan har mycket lite bevisats om sekvensen och många öppna frågor förblir olösta.
Tillväxttakt
Med tanke på att 5 inte visas förrän runt , skulle brute force-sökningstekniker aldrig hitta den första förekomsten av en term större än 4. Det har dock bevisats att sekvensen innehåller varje naturligt tal. Den exakta tillväxttakten är inte känd, men antas växa superlogaritmiskt , med den första förekomsten av något naturligt placerat nära .
Genomsnittligt värde
Även om det är känt att varje naturligt tal förekommer vid en ändlig position inom sekvensen, har det antagits att sekvensen kan ha ett ändligt medelvärde . För att definiera detta formellt på en oändlig sekvens, där omordning av termerna kan ha betydelse, är gissningen att:
Likaså är tätheten för ett givet naturligt tal i sekvensen inte känd.
Rekursiv struktur
Sekvensen kan delas upp i diskreta "block"- och "lim"-sekvenser, som kan användas för att rekursivt bygga upp sekvensen. Till exempel, på basnivån, kan vi definiera och som det första blocket respektive limsekvenserna. Tillsammans kan vi se hur de bildar början av sekvensen:
Nästa steg är att rekursivt bygga upp sekvensen. Definiera . Observera att sekvensen börjar med , vi kan definiera en limsträng vilket ger:
Vi tilldelade till en viss sekvens som ger egenskapen att förekommer också överst i sekvensen.
Denna process kan fortsätta i oändlighet med . Det visar sig att vi kan upptäcka en limsträng genom att notera att aldrig kommer att ha en 1, och att den stannar när den når den första 1:an till följ . Det har också bevisats att Gijswijts sekvens kan byggas upp på detta sätt i all oändlighet - det vill säga och är alltid ändliga i längd för alla .
Smart manipulation av limsekvenserna i denna rekursiva struktur kan användas för att visa att Gijswijts sekvens innehåller alla naturliga tal, bland andra egenskaper hos sekvensen.
Se även
externa länkar
- Första 50 miljoner termer
- OEIS- sekvens A091579 (Längder på suffixblock associerade med A090822) -- (längden på limsekvenserna)