Se-och-säg-sekvens

Se-och-säg-  sekvensen är en sekvens av siffror som börjar så här:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,... (sekvens A005150 i OEIS ).

Varje efterföljande nummer genereras från det föregående genom att sammanfoga siffran som utgör en grupp av identiska siffror och antalet siffror i denna grupp, för varje grupp av identiska siffror i numret. Till exempel:

Se-och-berätta-sekvensen föreslogs av John Conway [1] .

För en godtycklig siffra d , förutom en, som den initiala, har sekvensen formen:

d , 1 d , 111 d , 311 d , 13211 d , 111312211 d , 31131122211 d , …

Grundläggande egenskaper

Tillväxt

Sekvensen växer i det oändliga. Faktum är att varje variant av sekvensen med ett heltalsfrö kommer att växa på obestämd tid. Undantaget är sekvensen:

22, 22, 22, 22, 22, … (sekvens A010861 i OEIS ).

Begränsning av använda siffror

Inga andra siffror än 1, 2 och 3 förekommer i sekvensen om inte det initiala numret innehåller några andra siffror eller en grupp med fler än tre siffror [2] .

Längdtillväxt av siffror

I genomsnitt växer siffrorna med 30 % per iteration. Om anger längden på den n:e medlemmen av sekvensen, så finns det en relationsgräns :

.

Här är λ = 1,303577269034… Conways konstant [2] . Samma resultat gäller för alla varianter av sekvensen med ett annat frö än 22.

Polynom som returnerar Conways konstant

Conways konstant är den enda positiva reella roten till ett polynom:

I sin ursprungliga artikel gör Conway misstaget att skriva "−" istället för "+" före . Men värdet på λ som ges i hans papper är korrekt [3] .

Popularisering

Se-och-säg-sekvensen är också känd som Morris-nummersekvensen, efter kryptografen Robert Morris . Kallas ibland för "gökens ägg" på grund av pusslet "Vad är nästa nummer i sekvensen 1, 11, 21, 1211, 111221?" som beskrivs av Morris i Clifford Stolls bok The Cuckoo's Egg.

Variationer

Det finns många varianter av regler för att skapa se-och-säg-sekvenser. Till exempel sekvensen "ärtmönster". Det skiljer sig från Look-and-Say genom att för att få ett nytt nummer i det måste du räkna alla samma siffror i numret. Börjar med siffran 1 får vi: 1, 11 (en ettor), 21 (två ettor), 1211 (en två, en ettor), 3112 (tre ettor, en två), 132112 (en tre, två ettor, en två), 312213 (tre 1:or, två 2:or, en 3), etc. Som ett resultat kommer sekvensen till en cykel av två tal, 23322114 och 32232114. [4]

Det finns ett annat alternativ som skiljer sig från "ärtmönstret" genom att siffrorna räknas i stigande ordning, och inte som de visas. Med utgångspunkt från ett får vi sekvensen: 1, 11, 21, 1112, 3112, 211213, 312213, ...

Dessa sekvenser har anmärkningsvärda skillnader från Look-and-Say. Till skillnad från Conway-sekvensen, identifierar inte en given term i ett "ärtmönster" den föregående termen unikt. Längden på siffror i "ärtmönstret" är begränsad och för det b-ära talsystemet överstiger inte 2b och når 3b för stora initiala tal (till exempel "hundra enheter").

Med tanke på att denna sekvens är oändlig och dess längd är begränsad, måste den så småningom upprepas, enligt Dirichlet-principen . Som en konsekvens är dessa sekvenser alltid periodiska.

Se även

Anteckningar

  1. ↑ John Horton Conway. Ljudaktivt förfalls konstiga och underbara kemi   // Eureka . - 1986. - Januari ( vol. 46 ). - S. 5-16 . Arkiverad från originalet den 11 oktober 2014.
  2. ↑ 12 Oscar Martin . Titta-och-säg biokemi: exponentiellt RNA och flersträngat DNA //  American Mathematical Monthly. - 2006. - Vol. 113 , nr. 4 . - s. 289-307 . — ISSN 0002-9890 . Arkiverad från originalet den 24 december 2006.  
  3. ↑ Ilan Vardi. Computational Recreation in Mathematica.
  4. ↑ Stigande ärtmönstergenerator . Hämtad 9 augusti 2018. Arkiverad från originalet 17 oktober 2016.