SPOILER A: - - - - - - - - - - - - - - - - - - - - - - - - - - - Conway Sequence: 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... CCh: Conway's Recursive Sequence (series): 1, 11, 21, 1211, 111221, 312211, ... CCh- J. H. Conway, Eureka 46 (1986) 5-16, reprinted in: CCh Open Problems in Communications and Computations, Springer, 1987, 173-188 CCh The Weird and Wonderful Chemistry of Audioactive Decay CCh (Correction of the final asymptotic formula: Ilan Vardi) CCh- Ilan Vardi, Computational Recreations in Mathematica, Chapter 1. CCh ilan@leland.Stanford.EDU (ilan vardi) CCh Organization: DSG, Stanford University, CA 94305, USA CCh- Hilgemeier, M., Die Gleichniszahlen-Reihe, BdW (Dec. 1986) 19 CCh- "One Metaphor Fits All" : A Fractal Voyage With Conway's Audioactive Decay CCh http://www.is-bremen.de/~mhi/frahor00.htm CCh- Endless self-description (Hilgemeier's "likeness sequence", CCh [Die Gleichniszahlen-Reihe]) Qanntum 4:1 (1993) 17 CCh- P 958 R"atselhafter Folgenanfang? Praxis der Mathematik, 33:3 (1991) 136 CCh- Lsg P 958: Praxis der Mathematik, 34:1 (1992) 42-43 -> C. Stoll. CCh Folge: 1, 11, 21, 1211, 111221 = a1, a2, a3, a4, a5 gegeben. CCh Lsg I: V(n) = N(n-1) V(n-1) : 1, 1, 2, 12, ... (n >= 2 auŞer n=3) CCh N(n) = V(n-2) N(n-2) : -, 1, 1, 11, ... (n >= 3) CCh a(n) = V(n) N(n) CCh Lsg II: Fibonacci Lsg von Paasche ist Quatsch. CCh Lsg III: a(n) sei in Trinaersystem dargestellt, dies gibt im CCh Dezimalsystem 1, 4, 7, 49, 376, ... CCh Interpoliere durch ein Polynom 4ten Grades. CCh Lsg IV: Ersetze: 11->21, 1->11, 2->12 indem man immer die erste CCh moegliche Ersetzung (links nach rechts) macht. CCh- Clifford Stoll, Kuckucksei, Fischer Verlag, Kap. 48, S. 358 CCh- 1, 11, 21, 1211, 1231, 131221, ..., REC 7:4 (Sep 1992) 4-5 CCh- On a Curious Property of Counting Sequences, AMM 101 (1994) 560-563 CCh- XXX math.CO/9808077 Shalosh B. Ekhad, Doron Zeilberger CCh Proof of Conway's Lost Cosmological Theorem Date: Fri, 2 May 1997 18:56:39 -0400 TO: math-fun FROM: Bill Dubuque Below are textified versions of Zeilberger's announcement and the Mathsoft page on Conway's constant. Note that Conway's original paper is in the same volume as his FRACTRAN paper, which I mentioned earlier when discussing the 3x+1 problem, and Conway's proof of the undecidability of related congruential iteration problems, and occurrence of such in small busy beavers Turing machines, etc. -Bill Dubuque Source: http://www.math.temple.edu/~zeilberg/mamarim/mamarimTeX/horton.tex PROOF of CONWAY'S LOST COSMOLOGICAL THEOREM Shalosh B. Ekhad and Doron Zeilberger Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. [ekhad,zeilberg]@math.temple.edu http://www.math.temple.edu/~[ekhad,zeilberg] First version: May 1, 1997. This version: May 2, 1997. One of the most celebrated sequences ([F][SP][V]), is Conway's[C] 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... It is defined by the rule C_1:=1, and C_{i+1}:=JHC(C_i), for i>1, where JHC is Conway's audioactive operator: JHC(a^r b^s ... f^w) := rasb ... wf, where a^r is shorthand for ``a repeated r times'' (and we agree that the description is optimal, i.e. a != b, ...). We assume familiarity with Conway's charming article[C]. Conway proved that the above sequence has the property length(C_{i+1})/length(C_i) -> \lambda, where \lambda=1.303577269.. is Conway's constant. He also stated that, more generally, if one starts with an *arbitrary* finite string of integers, B_1, and defines, B_{i+1}:=JHC(B_i), i>1, then still length(B_{i+1})/length(B_i) -> \lambda. Conway called this the `Cosmological Theorem', and stated that two independent proofs *used to exist*, one by himself and Richard Parker, and another one by Mike Guy. Unfortunately both proofs are lost. Here we announce a new proof, which furthermore is one-line (modulo purely routine computer-verification, and routine Maple programming). The proof is an immediate consequence of the following finitely checkable lemma: LEMMA: The maximal length of an atom in the splitting of a 50-day-old string is 74. Every such atom decays, in at most 17 days, into stable or transuranic elements. The lemma is *proved* by typing Cosmo(50); in the Maple package HORTON, accompanying this announcement. The procedure Cosmo computes iteratively all strings of length 2i (i=1,2, ...) that might conceivably be substrings (`chunks') of a 50-day-old-string (by backtracking, examining its possible ancestors up to (at most) 50 generations and rejecting those that lead to grammatically incorrect ancestors, or that split in the middle). Every time a string of length 2i is accepted, its lifetime (number of days it takes to decay to stable or transuranic elements) is computed, and checked whether it is finite (the maximal longevity turned out to be 17). If the program halts (it did for us), then the lemma, and hence the Cosmological Theorem, would be proved. In fact it halted after i=37, implying that there do not exist atoms of length >74 that occur in *mature* (i.e. 50-day-old) sequences. The output file may be obtained from our website. The Maple package HORTON, available free of charge from the second author's website, also rederives many other results in Conway's paper, in particular it finds all the stable and transuranic elements *from scratch*, finds the minimal polynomial for \lambda, finds the relative frequencies of all the stable elements (procedures PT or PTlam, and computes the longevity of any sequence. We refer the reader to the on-line documentation and to the source code. REFERENCES [C] J.H. Conway, The weird and wonderful chemistry of audioactive decay, in: Open Problems in Communication and Computation, T.M. Cover and B. Gopinath, eds., Springer, 1987, pp. 173-188. [F] S. Finch, Favorite Mathematical Constants Website http://www.mathsoft.com. [SP] N.J.A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995. [V] I. Vardi, Computational Recreations in Mathematica, Addison-Wesley, 1991. Note: Conway's Constant (lowercase greek lambda) is denoted by Y below. The two tables [Uranium to Silver], [Palladium to Hydrogen] are not included below. Source: http://www.mathsoft.com/asolve/constant/cnwy/cnwy.html CONWAY'S CONSTANT Suppose we start with a string of digits, for example, 13 We might describe this as "one one, one three" and thus write the *derived* string: 1113 This in turn we describe as "three ones, one three", giving: 3113 Continuing, we obtain the following sequence of strings: 132113 1113122113 311311222113 13211321322113 1113122113121113222113 31131122211311123113322113 132113213221133112132123222113 11131221131211132221232112111312111213322113 31131122211311123113321112131221123113111231121123222113 1321132132211331121321231231121113112221121321133112132112211213322113 11131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222113 3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112211322112211213322113 132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222113 111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312113221133211322112211213322113 We've given the first 17 strings of this sequence above (k=1 to k=17). It can be proved that only the digits 1, 2 and 3 appear at any step, so the process can be continued indefinitely. What can be said about the length of the kth string? Its growth appears to be exponential and at first glance one would expect this to be impossibly difficult to characterize more precisely. Conway, in a remarkable paper([1]), proved that the growth is asymptotic to C Y^k where Y = 1.303577269... is the largest zero of the polynomial 71 69 68 67 66 65 64 63 62 61 60 (d6) x - x - 2 x - x + 2 x + 2 x + x - x - x - x - x 59 58 57 56 55 54 53 52 51 50 - x + 2 x + 5 x + 3 x - 2 x - 10 x - 3 x - 2 x + 6 x + 6 x 49 48 47 46 45 44 43 42 41 40 + x + 9 x - 3 x - 7 x - 8 x - 8 x + 10 x + 6 x + 8 x - 5 x 39 38 37 36 35 34 33 32 31 30 - 12 x + 7 x - 7 x + 7 x + x - 3 x + 10 x + x - 6 x - 2 x 29 28 27 26 25 24 23 21 20 - 10 x - 3 x + 2 x + 9 x - 3 x + 14 x - 8 x - 7 x + 9 x 19 18 17 16 15 14 13 12 11 + 3 x - 4 x - 10 x - 7 x + 12 x + 7 x + 2 x - 12 x - 4 x 10 9 7 6 5 4 3 2 - 2 x + 5 x + x - 7 x + 7 x - 4 x + 12 x - 6 x + 3 x - 6 = X^71 -X^69-2*X^68 -X^67+2*X^66 +2*X^65 +X^64 -X^63 -X^62 -X^61 -X^60 -X^59+2*X^58 +5*X^57+3*X^56 -2*X^55-10*X^54 -3*X^53-2*X^52 +6*X^51+6*X^50 +X^49+9*X^48 -3*X^47-7*X^46 -8*X^45 -8*X^44+10*X^43+6*X^42 +8*X^41-5*X^40 -12*X^39+7*X^38 -7*X^37+7*X^36 +X^35 -3*X^34+10*X^33 +X^32 -6*X^31-2*X^30 -10*X^29-3*X^28 +2*X^27+9*X^26 -3*X^25+14*X^24 -8*X^23 -7*X^21+9*X^20 +3*X^19-4*X^18-10*X^17-7*X^16+12*X^15 +7*X^14 +2*X^13-12*X^12-4*X^11-2*X^10 +5*X^ 9 + X^ 7-7*X^ 6+ 7*X^ 5 -4*X^ 4+12*X^ 3 -6*X^ 2+3*X -6; This polynomial and Y were first computed by A.O.L. Atkin; I. Vardi[2] noticed a typographical error in [1] (the x^35 term is off by a sign). Moreover, the same constant Y applies to the growth rates of ~all~ such sequences, regardless of the starting string, with two trivial exceptions. We started with {1,3} above; the constant Y is ~universally applicable~ except for the empty initial string {} and the string {2,2}. This astonishing fact, known as the *Cosmological Theorem*, is evidentally very difficult to prove. (See the Postscript for an update.) Even more can be said. Sometimes a string factors as the concatenation of two strings L and R whose descendents never interfere with each other. We say that the string LR *splits* as L.R and LR is called a *compound*. A string with no nontrivial splittings is called an *element* or *atom*. It turns out that there are 92 special atoms (named after the chemical elements Hydrogen, Helium, ..., Uranium). ~Every~ string of 1's, 2's and/or 3's eventually decays into a compound of these elements. Additionally, the relative abundances of the elements approach fixed positive limits, independent of the initial string. Thus, of every million atoms, about 91790 on average will be of Hydrogen (the most common) while about 27 will be of Arsenic (the least common). We give here Conway's Periodic Table in two parts: [Uranium to Silver] and [Palladium to Hydrogen]. The tables trace the evolution of the string 13 as above (n=92-k), but indicate the evolution in terms of elements rather than long ternary strings. For example, when k=1 to k=6, the strings are the elements Pa, Th, Ac, Ra, Fr and Rn, but when k=7, the first compound emerges: 13211321322113 which may be rewritten as Ho.At because Ho is 1321132 and At is 1322113. As another example, when k=91, Helium derives to the compound Hf.Pa.H.Ca.Li because H is 22. Let us illustrate further. If we start with {1,1}, we obtain 11 21 1211 111221 312211 13112221 1113213211 = 11132.13211 = Hf.Sn If we start with {1,2}, the first string is already an element: 12 = Ca while starting with {3,2} or {3,3} gives: 32 33 1312 23 11131112 = 1113.1112 = Th.K 1213 11121113 = 1112.1113 = K.Th There is also the more general case of strings containing digits other than 1, 2 or 3. If we start with, say, {1,4} or {5,5}, the theorem regarding relative abundances still applies, but we allow just two additional elements (*isotopes* of Plutonium and Neptunium) Pu4 = 312211322212221121123222114 Np4 = 13112221133211322112211213322114 Pu5 = 312211322212221121123222115 Np5 = 13112221133211322112211213322115 whose relative abundances tend to 0. This is true for strings with digits 6, 7, 8, 9,... as well. Returning to Conway's constant Y : it is the (unique) largest eigenvalue (in modulus) of the 92x92 transition matrix M whose (i,j)th element is the number of atoms of element j resulting from the decay of one atom of element i. The relative abundancies also arise in the careful eigenanalysis of M. Does an expression for Y (an algebraic irrational number of degree 71) exist in terms of radicals? Postscript Doron Zeilberger has kindly informed me of [5], which provides a proof of the Cosmological Theorem. (John Conway explained in [1] that the two independent proofs of this particular theorem were lost, so until [5] appeared the Cosmological Theorem lacked an extant proof!) Ekhad and Zeilberger's tour-de-force is a splendid illustration of the use of software in proving theorems. *References* 1. J. H. Conway, The weird and wonderful chemistry of audioactive decay, in ~Open Problems in Communication and Computation~, ed. T. M. Cover and B. Gopinath, Springer-Verlag, 1987. 2. I. Vardi, ~Computational Recreations in Mathematica~, Addison Wesley 1991. 3. USENET newsgroup rec.puzzles FAQ, available at [[MIT]] and [[Utrecht University, the Netherlands]]; search for "series/series.07.p". 4. J. Sauerberg and L. Shu, The long and the short on counting sequences, ~Amer. Math. Monthly~ 104 (1997) 306-317. 5. S. B. Ekhad and D. Zeilberger, Proof of Conway's lost Cosmological Theorem, submitted (1997), postscript file and Maple file {available here}. ~This page was modified May 02, 1997 Copyright 1997 MathSoft, Inc. All rights reserved.~ Date: 3. May 1997 TO: math-fun FROM: John Conway I was pleased to see Doron Zeilberger's article on this, but would like to make a few comments: 1) The sequence isn't actually "mine" - I heard it by word of mouth from a Cambridge undergraduate whose name I don't at this moment recall. My article first appeared in the Cambridge undergraduate math journal "Eureka", where it was accompanied by a note by him (or maybe another student) that traced its history back a few steps. 2) The theorem that the nth root of the length of the nth term of 1,11,21,1211,111221,312211,... tends to the positive root (lambda) of a certain irreducible equuation of degree 71 IS mine. 3) The "Cosmological Theorem" was my conjecture, but is only half my theorem, since the first of the two lost proofs was joint with Richard Parker. 4) It was slightly wrongly stated in Zeilberger's message - the sequence starting 22 ("Hydrogen") is constant: 22, 22, 22, 22, ... . The CT asserts that with any OTHER nonempty start the nth root of the length of the nth term tends to lambda. 5) Ilan Vardi pointed out that the last few of the 40-odd digits of lambda as given in my article are wrong, and there's a sign error or something in the printed form of the equation for it. 6) Unfortunately Zeilberger's proof doesn't give the stronger form of CT that follows from the second of the lost proofs (due to Mike Guy) - namely his identification of the longest-lived "exotic element" (called Methuselum). I'm hoping to persuade him to rederive this, too. 7) Funsters might like to explore the Roman numeral version: I, II, III, IIII, IIV, IIIIV, IVIIV, ... . I got very excited by this when David Park suggested it, because it seemed for a while that ITs lambda might have very large degree. But unfortunately the degree is comparatively small. I've just read right through the message I just replied to, and note that one of the questions raised was really answered in my old article. I proved that the 71st degree equation has Galois group S71, so that lambda can't be expressed by radicals. [I can't remember whether the proof was actually given there, but can remember what it was.] To my mind, lambda is the current record holder for finding the most complicated algebraic number from the silliest source. I hope more math-funsters will get into this stuff and produce other challengers! ---------------------------------------------------------------------