Conway Suite
Die Conway-Suite ist eine mathematische Suite , die 1986 vom Mathematiker John Horton Conway erfunden wurde , ursprünglich unter dem Namen "Audioactive Suite". Es ist auch unter dem englischen Namen Look and Say bekannt . In dieser Reihenfolge wird ein Term bestimmt, indem die Nummern bekannt gegeben werden, die den vorherigen Term bilden.
Definition
Der erste Term der Conway-Sequenz wird auf 1 gesetzt. Jeder Term der Sequenz wird durch Ansagen des vorhergehenden Terms konstruiert, dh durch Angabe, wie oft jede seiner Ziffern wiederholt wird.
Konkret:
Dieser Begriff enthält einfach eine "1". Daher lautet der nächste Begriff:
Dies besteht aus zwei "1":
Indem Sie den Prozess fortsetzen:
Und so weiter.
Es ist möglich, den Prozess zu verallgemeinern, indem ein anderer Anfangsbegriff als 1 verwendet wird. Im Rest des Artikels wird angenommen, dass der Anfangsbegriff gleich 1 ist.
Die ersten 20 Begriffe
| Begriff | |
|---|---|
| 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 |
| 13 | 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 |
| fünfzehn | 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 |
Eigenschaften
Conways Suite verfügt über mehrere Eigenschaften. Einige von ihnen sind nachstehend mit den entsprechenden Demonstrationen angegeben.
- Kein Term in der Sequenz hat eine Zahl größer als 3.
Beachten Sie zunächst, dass 1, 2 und 3 gut aussehen (siehe z. B. X (6)). Angenommen, die Nummer 4 erscheint zuerst in X (n). Es zeigt eine Folge von 4 identischen Ziffern in X (n-1) an (andernfalls wäre es bereits in X (n-1) vorhanden gewesen). Also enthielt X (n-1) xxxx (x = 1, 2 oder 3). Dies ist jedoch unmöglich, da unabhängig von der Position und dem Inhalt dieses Satzes von 4 identischen Ziffern in X (n-1) anders geschrieben werden sollte. Die Zahl 4 kann also nicht erscheinen, und nach derselben Überlegung auch nicht die höheren Zahlen.
- Alle Begriffe in der Sequenz haben eine gerade Anzahl von Ziffern, mit Ausnahme des ursprünglichen Begriffs.
Alle Begriffe in der Sequenz, mit Ausnahme des ersten, sind das Ergebnis des "Lesens" des vorhergehenden Begriffs. Dieses "Lesen" ergibt konstruktionsbedingt eine Folge von Ziffernpaaren: Zum Beispiel ergibt "3" Lesen "13", "111" Lesen ergibt "31", "22" Lesen ergibt "22" usw. (mit Ausnahme des ersten ) besteht aus Ziffernpaaren und besteht daher aus einer geraden Anzahl von Ziffern.
- Ab dem vierten Term enden die Begriffe des geraden Ranges mit 211 und die Begriffe des ungeraden Ranges mit 221.
Lassen Sie uns diese Eigenschaft durch Induktion beweisen. Wenn X (n) mit "211" endet, endet X (n + 1) mit "x221", also tatsächlich "221". Wenn X (n) mit "221" endet, dann ist es entweder "1221", was "x12211" in X (n + 1) ergibt, also tatsächlich "211"; oder es ist "2221", was "3211" ergibt, also tatsächlich "211"; oder schließlich ist es "3221", was "x32211" so gut "211" ergibt. Da also X (4) mit 211 endet, muss X (5) mit 221 enden und dann enden alle anderen X (n) abwechselnd mit 211 (gerade n) oder 221 (ungerade n).
- Ab dem 8. Term beginnen die Terme zyklisch mit "1113", "3113" und "1321".
Beachten Sie, dass X (11) = "111312 ...". dann beginnen X (12) = "3113 ..." und X (13) = "1321 ..." jeweils als X (8), X (9) und X (10).
Allgemeiner, wenn X (n) mit "1113x" (x # 3) beginnt, dann beginnt X (n + 1) mit "3113", dann X (n + 2) mit "1321" und X (n + 3) mit "111312" "was ihm die gleiche Eigenschaft wie X (n) gibt.
Aber X (8) hat diese Eigenschaft. Deshalb:
- Alle X (n) (n = 8 + 3p) beginnen mit 1113x x # 3 (und sogar 111312 für p> 0).
- Alle X (n) (n = 9 + 3p) beginnen mit 3113
- Alle X (n) (n = 10 + 3p) beginnen mit 1321
- Die Conway-Sequenz nimmt ebenso wie die von L (n) streng zu, wobei L (n) die Anzahl der Stellen ist, die den n-ten Term der Conway-Sequenz bilden.
Wir sehen, dass dies tatsächlich zumindest für X (n) bis X (10) sowie für L (n) ab L (6) der Fall ist.
Es ist zu beachten, dass bei der Konstruktion von X (n + 1) aus X (n) ein Singleton (eine isolierte ganze Zahl) ein Paar wird (wodurch die Länge L (n) um 1 erhöht wird), ein Paar ein Paar bleibt (ohne Längsaufprall) und ein Triplett (drei aufeinanderfolgende identische ganze Zahlen) wird gerade (Abnahme von L (n) um 1).
Lassen Sie uns zunächst zeigen, dass L (n + 1) größer oder gleich L (n) ist, wobei wir wissen, dass diese beiden Zahlen gerade sind (siehe vorherige Eigenschaft).
Hierzu ist es notwendig und ausreichend, dass S (n) (die Anzahl der Singletons in X (n)) größer oder gleich T (n) (die Anzahl der Tripletts in X (n)) ist.
Wenn X (n) kein Triplett enthält, wird die Eigenschaft offensichtlich verifiziert.
Wenn X (n) mindestens ein Triplett enthält, nennen wir T (1, n) das erste Triplett von X (n), das ab dem Ende von X (n) angetroffen wird.
Die letzte Ziffer von X (n) ist gerade, weil L (n) gerade ist. Da die erste und die letzte Ziffer eines Tripletts einen ungeraden Rang haben, gibt es daher eine ungerade Anzahl von Ziffern zwischen T (1, n) und dem Ende von X (n). Also mindestens 1 Singleton (da es hypothetisch kein Triplett zwischen T (1, n) und dem Ende von X (n) geben kann). Indem wir die Argumentation zu T (2, n) und das Folgende wiederholen, beweisen wir, dass sich immer mindestens ein Singleton hinter einem Triplett befindet, das sich vor dem nächsten Triplett befindet, falls es eines gibt. Also mindestens so viele Singletons, wie es in X (n) Tripel gibt. Also ist L (n + 1) größer oder gleich L (n).
Jedes X (n) hat also mindestens so viele Singletons, wie es in seinem Teil Tripel gibt, beginnend mit seinem ersten Tripel (beginnend von links).
Die Eigenschaft, die sich auf die ersten Ziffern von X (n) bezieht, zeigt nun, dass alle X (n) entweder mit einem Singleton oder mit "111" beginnen, gefolgt von 2 Singletons. Daher hat X (n) in allen Fällen mehr Singletons als Tripletts . L (n) ist also eine streng ansteigende Folge (n> = 6) und daher auch X (n).
- Im Durchschnitt haben die Begriffe in der Sequenz 50% der Ziffern 1, 31% von 2 und 19% von 3.
- Die Zahl der Stellen in der n- ten Term in der Sequenz ist äquivalent zu C λ n , wobei λ ≈ 1,303 577 eine ist algebraische ganze Zahl von 71 Grad genannt Conway-Konstante , und C ist eine weitere Konstante ist . Bestimmtes :
Die Conway-Konstante ist die einzigartige echte positive Lösung für die folgende Polynomgleichung :
"Audioaktiver Zerfall"
John Conway nannte es zunächst das Ergebnis von "Desintegration Audioactive" ( Audioaktiver Zerfall auf Englisch), einem Wortspiel über radioaktiven Zerfall , bei dem das Verhalten der verschiedenen Begriffe der Sequenz bemerkt wurde.
In seinem kosmologischen Theorem hat er gezeigt, dass ab einem bestimmten Punkt fast alle Terme der Sequenz in 92 Unterterme (in Analogie zu den chemischen Elementen Elemente genannt ) zerlegt werden können, die sich im folgenden Term in eine Reihe anderer zerlegen Elemente.
Zum Beispiel ist das einfachste Element, Wasserstoff genannt , die Sequenz, die selbst den folgenden Begriff ergibt. Die Sequenz heißt Mangan ; beim nächsten Term gibt es, was sich in die Sequenzen Promethium ( ) und Natrium ( ) zersetzt .
Es wurde gezeigt, dass, wenn wir die Sequenz mit dem Begriff Uran beginnen , die 91 anderen Elemente nach 91 Iterationen in dem einen oder anderen Begriff erschienen sind. Diese Suite trägt auch den Namen Conways Sequenz in englischer Sprache .
In der Literatur
Bernard Werber hat diese Fortsetzung in seinen Werken Les fourmis und in The Encyclopedia of Relative and Absolute Knowledge aufgegriffen .
Verweise
(en) Dieser Artikel teilweise oder vollständig aus dem Wikipedia - Artikel in genommen englischen Titeln „ Conway-Folge “ ( siehe die Liste der Autoren ) .- (in) John H. Conway , " The Weird and Wonderful Audioactive Chemistry of Decay " , Eureka , Cambridge University , n o 46,1986, p. 5-18 ( ISSN 0071-2248 ).
- Für Dezimalstellen siehe mehr A014715 von OEIS - bis zu 20000 e .
- (in) Eric W. Weisstein , " Conway's Constant " auf MathWorld .
- " Eine Ableitung von Conways Grad-71" Look-and-Say "-Polynom " über Nathaniel Johnston ,1 st November 2010(abgerufen am 4. April 2021 )
- (in) Michael J. Bradley, Ph.D., Mathematics Frontiers: 1950 bis heute , Infobase Publishing ,1997( ISBN 978-0-8160-5427-5 , online lesen ) , p. 45.
-
OEIS Suite A137275 .
- [Video] Zwei (zwei?) Minuten für Conways Fortsetzungen auf YouTube
Anhänge
Zum Thema passende Artikel
Externe Links
- (de) Look and Say-Sequenz: Beschreiben Sie den vorherigen Begriff! (Methode A - Anfangsterm ist 1) : Suite A005150 des OEIS
- (de) Eric W. Weisstein , „ Look and Say Sequence “ , auf MathWorld
- (en) Henry Bottomley, „ Evolution von Conways 92 Audio and Look Say Audioactive-Elementen “: eine Zusammenstellung der 92 „Audioactive“ -Elemente der Suite
- Generierungsalgorithmen in verschiedenen Sprachen auf Rosetta Code