Conway-suite
Den Conway suite er en matematisk suite oppfunnet i 1986 av matematikeren John Horton Conway , først under navnet "audioactive pakke". Det er også kjent med det engelske navnet Look and Say . I denne sekvensen bestemmes et begrep ved å kunngjøre tallene som danner forrige periode.
Definisjon
Den første termen i Conway-sekvensen er satt til lik 1. Hver term i sekvensen konstrueres ved å kunngjøre den forrige termen, det vil si ved å indikere hvor mange ganger hvert av sifrene gjentas.
Konkret:
Dette begrepet inneholder ganske enkelt en "1". Derfor er neste periode:
Dette består av to "1":
Ved å fortsette prosessen:
Og så videre.
Det er mulig å generalisere prosessen ved å ta en annen innledende periode enn 1. I resten av artikkelen vil vi anta at den innledende termen er lik 1.
De første 20 terminene
| Begrep | |
|---|---|
| 1 | 1 |
| 2 | 11 |
| 3 | 21 |
| 4 | 12 11 |
| 5 | 11 12 21 |
| 6 | 31 22 11 |
| 7 | 13 11 22 21 |
| 8 | 11 13 21 32 11 |
| 9 | 31 13 12 11 13 12 21 |
| 10 | 13 21 13 11 12 31 13 11 22 11 |
| 11 | 11 13 12 21 13 31 12 13 21 13 21 22 21 |
| 12 | 31 13 11 22 21 23 21 12 11 13 12 21 13 12 11 32 11 |
| 1. 3 | 13 21 13 21 32 11 12 13 12 21 12 31 13 11 22 21 13 11 12 21 13 12 21 |
| 14 | 11 13 12 21 13 12 11 13 12 31 12 11 13 11 22 21 12 13 21 13 21 32 21 13 31 22 21 13 11 22 11 |
| 15 | 31 13 11 22 21 13 11 12 31 13 11 12 13 21 12 31 13 21 32 21 12 11 13 12 21 13 12 11 13 22 21 23 11 32 21 13 21 22 21 |
| 16 | 13 21 13 21 32 21 13 31 12 13 21 13 31 12 11 13 12 21 12 13 21 13 12 11 13 22 21 12 31 13 11 22 21 13 11 12 31 13 32 11 12 13 21 13 22 21 13 12 11 32 11 |
| 17 | 11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 21 23 21 12 31 13 11 22 21 12 11 13 12 21 13 11 12 31 13 32 21 12 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 12 21 13 32 21 13 11 12 21 13 12 21 |
| 18 | 31 13 11 22 21 13 11 12 31 13 32 11 12 13 12 21 12 31 13 11 22 11 12 13 12 21 12 13 21 13 21 32 21 12 31 13 11 22 21 13 31 12 13 21 23 22 21 12 11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 11 12 13 11 12 13 21 12 31 13 11 22 21 23 22 21 13 31 22 21 13 11 22 11 |
| 19 | 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 11 22 21 12 13 21 13 21 22 31 12 11 13 11 22 21 12 11 13 12 21 13 12 11 13 22 21 12 13 21 13 21 32 21 23 21 12 11 13 12 11 12 13 32 21 12 31 13 11 22 21 13 11 12 31 13 32 11 12 13 12 21 12 31 13 11 12 31 12 11 13 31 12 11 13 12 21 12 13 21 13 21 32 11 12 13 32 21 23 11 32 21 13 21 22 21 |
| 20 | 11 13 12 21 13 12 11 13 22 21 23 21 12 11 13 12 11 12 13 11 12 13 21 12 31 13 21 32 21 12 11 13 12 21 13 12 11 22 13 21 12 31 13 21 32 21 12 31 13 11 22 21 13 11 12 31 13 32 21 12 11 13 12 21 13 12 11 13 22 11 12 13 12 21 12 31 13 11 12 31 12 11 23 22 21 12 13 21 13 21 32 21 13 31 12 13 21 23 12 31 12 11 13 11 22 21 12 13 21 13 31 12 13 21 12 31 23 21 12 31 13 11 22 21 12 11 13 12 21 13 12 11 13 12 31 12 11 23 22 11 12 13 21 13 22 21 13 12 11 32 11 |
Eiendommer
Conways suite har flere egenskaper. Noen av dem er angitt nedenfor, med, for den enkleste, de tilsvarende demonstrasjonene.
- Ingen betegnelser i sekvensen har et tall større enn 3.
Legg først merke til at 1, 2 og 3 ser bra ut (se for eksempel X (6)). Anta at tallet 4 først vises i X (n). Det indikerer en sekvens på 4 identiske sifre i X (n-1) (ellers ville det allerede vært til stede i X (n-1)). Så X (n-1) inneholdt xxxx (x = 1, 2 eller 3). Dette er imidlertid umulig fordi uansett posisjon og innhold i dette settet med 4 identiske sifre, burde det vært skrevet annerledes i X (n-1). Så tallet 4 kan ikke vises, og heller ikke, av samme resonnement, de høyere tallene.
- Alle ordene i sekvensen har et jevnt antall sifre, unntatt den innledende termen.
Alle ordene i sekvensen, bortsett fra den første av dem, er resultatet av å "lese" forrige term. Nå gir denne "lesingen" ved konstruksjon en sekvens av par med sifre: for eksempel "3" leser gir "13", "111" leser gir "31", "22" lesing gir "22", etc. (unntatt den første ) består av par med sifre, derfor består det av et jevnt antall sifre.
- Fra fjerde periode slutter vilkårene for jevn rang med 211 og vilkårene for odd rang med 221.
La oss bevise denne egenskapen ved induksjon. Hvis X (n) slutter med "211", slutter X (n + 1) med "x221" så faktisk "221". Hvis X (n) slutter med "221", er det enten "1221", noe som gir "x12211" i X (n + 1) derfor faktisk "211"; eller det er "2221" som gir "3211" derfor faktisk "211"; eller til slutt er det "3221" som gir "x32211" så bra "211". Så siden X (4) slutter med 211, må X (5) slutte med 221, og deretter avsluttes alle andre X (n) vekselvis med 211 (jevn n) eller 221 (odd n).
- Fra 8. termin begynner begrepene syklisk med "1113", "3113" og "1321".
Legg merke til at X (11) = "111312 ...." deretter starter X (12) = "3113 ..." og X (13) = "1321 .." henholdsvis som X (8), X (9) og X (10).
Mer generelt hvis X (n) begynner med "1113x" (x # 3), begynner X (n + 1) med "3113", deretter X (n + 2) med "1321" og X (n + 3) med "111312 "som gir den samme egenskap som X (n).
Men X (8) har denne egenskapen. Derfor:
- alle X (n) (n = 8 + 3p) starter med 1113x x # 3 (og til og med 111312 for p> 0)
- alle X (n) (n = 9 + 3p) starter med 3113
- alle X (n) (n = 10 + 3p) starter med 1321
- Conway-sekvensen øker strengt, så vel som for L (n) der L (n) er antall sifre som utgjør den n-termen for Conway-sekvensen.
Vi ser at dette faktisk er tilfelle for X (n) opp til X (10) i det minste, så vel som for L (n) fra L (6).
Merk at i konstruksjonen av X (n + 1) fra X (n) blir et singleton (et isolert heltall) til et par (øker lengden L (n) med 1), et par forblir et par (uten støt i lengderetningen) og en triplett (tre påfølgende identiske heltall) blir en jevn (reduseres med 1 av L (n)).
La oss først vise at L (n + 1) er større enn eller lik L (n), vel vitende om at disse to tallene er jevne (se forrige egenskap).
For dette er det nødvendig og tilstrekkelig at S (n) (antall singletoner i X (n)) er større enn eller lik T (n) (antall tripletter i X (n)).
Hvis X (n) ikke inneholder en triplett, blir egenskapen åpenbart verifisert.
Hvis X (n) inneholder minst en triplett, la oss kalle T (1, n) den første tripletten av X (n) som oppstår fra slutten av X (n).
Det siste sifferet i X (n) er jevnt, fordi L (n) er jevnt. Siden de første og siste sifrene i en hvilken som helst triplett har ulik rang, er det derfor et oddetall sifre mellom T (1, n) og slutten av X (n). Så minst 1 singleton (siden det ikke ved hypotesen kan være en triplett mellom T (1, n) og slutten av X (n)). Ved å gjenta resonnementet på T (2, n) og det følgende, viser vi at det alltid er minst en singleton bak en triplett, plassert før neste triplett hvis det er en. Så minst like mange singler som det er tripler i X (n). Så L (n + 1) er større enn eller lik L (n).
Så hver X (n) har minst like mange singler som det er tripler i sin del, og begynner med sin første triplett (fra venstre).
Nå viser egenskapen som gjelder de første sifrene i X (n) at alle X (n) starter enten med en singleton eller med "111" etterfulgt av 2 singletoner: derfor har X (n) i alle tilfeller flere singletoner enn trillinger . Så L (n) er en streng økende sekvens (n> = 6), og derfor også X (n).
- I gjennomsnitt har ordene i sekvensen 50% av sifrene 1, 31% av 2 og 19% av 3.
- Antallet sifre i n- th term i sekvensen er tilsvarende til C λ n , hvor λ ≈ 1,303 577 er et algebraisk tall med grad 71 kalles Conway konstant , og C er en konstant. Spesielt :
Conways konstant er den unike virkelige positive løsningen på følgende polynomligning :
"Audioactive decay"
John Conway refererte opprinnelig til denne oppfølgeren som " lydaktivt forfall ", et spill på radioaktivt forfall , og bemerket oppførselen til de forskjellige begrepene i oppfølgeren.
I sin kosmologiske teorem demonstrerte han at nesten alle vilkårene i sekvensen fra et visst punkt kan brytes ned i 92 underord (kalt elementer, analogt med de kjemiske elementene ) som nedbrytes ved det følgende begrepet i et antall andre elementer.
For eksempel er det enkleste elementet, kalt hydrogen , sekvensen som i seg selv gir det følgende begrepet. Sekvensen kalles mangan ; ved neste periode gir det som spaltes i sekvensene prometium ( ) og natrium ( ).
Det er vist at hvis vi starter sekvensen med begrepet uran , vil de 91 andre elementene ha dukket opp i ett eller annet begrep etter 91 iterasjoner. Denne suiten bærer også navnet Conways rekkefølge på engelsk .
I litteraturen
Bernard Werber tok opp denne fortsettelsen i sine arbeider Les fourmis og i The Encyclopedia of relative and absolute knowledge .
Referanser
(no) Denne artikkelen er delvis eller helt hentet fra Wikipedia-artikkelen på engelsk med tittelen " Se og si-sekvens " ( se listen over forfattere ) .- (i) John H. Conway , " det merkverdige Audioactive Chemistry of Decay " , Eureka , Cambridge University , n o 46,1986, s. 5-18 ( ISSN 0071-2248 ).
- For desimaler, se mer A014715 av OEIS - opptil 20000 e .
- (i) Eric W. Weisstein , " Conway's Constant " på MathWorld .
- " A Derivation of Conway's Degree-71" Look-and-Say "Polynomial " , på Nathaniel Johnston ,1 st november 2010(åpnet 4. april 2021 )
- (in) Michael J. Bradley, Ph.D., Mathematics Frontiers: 1950 to the Present , Infobase Publishing ,1997( ISBN 978-0-8160-5427-5 , leses online ) , s. 45.
-
OEIS Suite A137275 .
- [video] To (to?) Minutter for Conways oppfølgere på YouTube
Vedlegg
Relaterte artikler
Eksterne linker
- (no) Se og si sekvens: beskriv forrige ord! (metode A - første begrep er 1) : suite A005150 til OEIS
- (no) Eric W. Weisstein , “ Look and Say Sequence ” , på MathWorld
- (no) Henry Bottomley, “ Evolution of Conways 92 Look and Say audioactive elements ”: en samling av de 92 “audioactive” elementene i suiten
- Generasjonsalgoritmer på forskjellige språk på Rosetta Code