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!
---------------------------------------------------------------------