Katso ja sano -sekvenssi

Katso ja sano -sekvenssi on numerosarja, joka alkaa näin:

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,… (sekvenssi A005150 OEIS : ssä ).

Jokainen seuraava numero muodostetaan edellisestä ketjuttamalla numero, joka muodostaa identtisten numeroiden ryhmän, ja tämän ryhmän numeroiden lukumäärä jokaiselle numeron identtisten numeroiden ryhmälle. Esimerkiksi:

1 luetaan "yhdeksi yksiköksi", eli 11
11 luetaan "kaksi yksikkönä", eli 21
21 luetaan "yksi kaksi, yksi yksikkö", eli 1211
1211 luetaan "yksi yksikkö, yksi kaksi, kaksi yksikköä", eli 111221
111221 luetaan nimellä "kolme yksi, kaksi kaksi, yksi yksikkö", eli 312211
312211 luetaan "yksi kolme, yksi, kaksi kaksi, kaksi yksi", eli 13112221

Katso ja kerro -sekvenssiä ehdotti John Conway [1] .

Satunnaiselle numerolle d , yhtä lukuun ottamatta, sekvenssi on muotoa:

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

Perusominaisuudet

Kasvu

Sarja kasvaa loputtomasti. Itse asiassa mikä tahansa sekvenssin variantti, jossa on kokonaisluvun siemen, kasvaa loputtomasti. Poikkeuksena on järjestys:

22, 22, 22, 22, 22, … (sekvenssi A010861 OEIS : ssä ).

Käytettyjen numeroiden rajoitus

Sarjassa ei esiinny muita numeroita kuin 1, 2 ja 3, ellei alkunumero sisällä muita numeroita tai yli kolmen numeron ryhmää [2] .

Numeroiden pituuskasvu

Keskimäärin luvut kasvavat 30 % iteraatiota kohden. Jos ilmaisee sekvenssin n:nnen jäsenen pituutta, on relaatioraja : $L_{n}$ ${\frac {L_{n+1}}{L_{n}}}$

$\lim _{n\to \infty }{\frac {L_{n+1}}{L_{n}}}=\lambda$ .

Tässä λ = 1.303577269034… on Conwayn vakio [2] . Sama tulos pätee mille tahansa sekvenssin variantille, jonka siemen on muu kuin 22.

Polynomi palauttaa Conwayn vakion

Conwayn vakio on polynomin ainoa positiivinen todellinen juuri:

${\begin{aligned}&\,\,\,\,\,\,\,x^{71}&&&&-x^{69}&&-2x^{68}&&-x^{67} &&+2x^{66}&&+2x^{65}&&+x^{64}&&-x^{63}\\&-x^{62}&&-x^{61}&&-x^{60 }&&-x^{59}&&+2x^{58}&&+5x^{57}&&+3x^{56}&&-2x^{55}&&-10x^{54}\\&-3x^{ 53}&&-2x^{52}&&+6x^{51}&&+6x^{50}&&+x^{49}&&+9x^{48}&&-3x^{47}&&-7x^{46 }&&-8x^{45}\\&-8x^{44}&&+10x^{43}&&+6x^{42}&&+8x^{41}&&-5x^{40}&&-12x^{ 39}&&+7x^{38}&&-7x^{37}&&+7x^{36}\\&+x^{35}&&-3x^{34}&&+10x^{33}&&+x^ {32}&&-6x^{31}&&-2x^{30}&&-10x^{29}&&-3x^{28}&&+2x^{27}\\&+9x^{26}&&-3x ^{25}&&+14x^{24}&&-8x^{23}&&&&-7x^{21}&&+9x^{20}&&+3x^{19}&&-4x^{18}\\&- 10x^{17}&&-7x^{16}&&+12x^{15}&&+7x^{14}&&+2x^{13}&&-12x^{12}&&-4x^{11}&&-2x ^{10}&&+5x^{9}\\&&&+x^{7}&&-7x^{6}&&+7x^{5}&&-4x^{4}&&+12x^{3}&&- 6x^{2}&&+3x&&-6\end{aligned}}$

Alkuperäisessä artikkelissaan Conway tekee sen virheen kirjoittaessaan "−" ennen "+":n sijasta . Mutta hänen kirjoituksessaan annettu λ:n arvo on oikea [3] . $x^{35}$

Popularisointi

Look-and-Say -sekvenssi tunnetaan myös Morris-numerosekvenssinä kryptografi Morrisin mukaan . Joskus sitä kutsutaan "känmunaksi" Morrisin Clifford Stollin kirjassa The Cuckoo's Egg -kirjassa kuvaileman pulman "Mikä on seuraava numero järjestyksessä 1, 11, 21, 1211, 111221?" vuoksi.

Muunnelmia

Katso ja kerro -sekvenssien luomiseen on olemassa monia eri variaatioita. Esimerkiksi sekvenssi "hernekuvio". Se eroaa Look-and-Saysta siinä, että saadaksesi siihen uuden numeron, sinun on laskettava kaikki samat numerot numerossa. Alkaen numerosta 1, saamme: 1, 11 (yksi yksi), 21 (kaksi), 1211 (yksi kaksi, yksi yksi), 3112 (kolme yksi, yksi kaksi), 132112 (yksi kolme, kaksi yksi, yksi kaksi), 312213 (kolme 1:tä, kaksi 2:ta, yksi 3) jne. Tämän seurauksena sekvenssi tulee kahden luvun sykliin, 23322114 ja 32232114. [4]

On toinenkin vaihtoehto, joka eroaa "hernekuviosta" siinä, että numerot lasketaan nousevassa järjestyksessä, ei sellaisina kuin ne näkyvät. Yhdestä alkaen saamme sekvenssin: 1, 11, 21, 1112, 3112, 211213, 312213, ...

Näillä sarjoilla on huomattavia eroja Look-and-Say:hen. Toisin kuin Conway-sekvenssi, tietty termi "hernekuviossa" ei yksilöi yksiselitteisesti edellistä termiä. Numeroiden pituus "hernekuviossa" on rajoitettu, ja b-äärilukujärjestelmässä se ei ylitä 2b:tä ja saavuttaa 3b:n suurilla alkuluvuilla (esimerkiksi "sata yksikköä").

Koska tämä sarja on ääretön ja sen pituus on rajoitettu, sen on lopulta toistettava Dirichlet-periaatteen mukaisesti . Tämän seurauksena nämä sekvenssit ovat aina jaksollisia.

Katso myös

Muistiinpanot

↑ John Horton Conway. Audioaktiivisen rappeutumisen outo ja ihmeellinen kemia // Eureka . - 1986. - tammikuu ( osa 46 ). - s. 5-16 . Arkistoitu alkuperäisestä 11. lokakuuta 2014.
↑ 12 Oscar Martin . Look-and-Say Biochemistry: Eksponentiaalinen RNA ja monijuosteinen DNA // American Mathematical Monthly. - 2006. - Voi. 113 , nro. 4 . - s. 289-307 . — ISSN 0002-9890 . Arkistoitu alkuperäisestä 24. joulukuuta 2006.
↑ Ilan Vardi. Laskennallinen virkistys Mathematicassa.
↑ Nouseva hernekuvion generaattori . Haettu 9. elokuuta 2018. Arkistoitu alkuperäisestä 17. lokakuuta 2016. (määrätön)