From: chris@peregrine.peregrine.com (Chris Cole)
Newsgroups: rec.puzzles
Subject: Re: 1s and 2s series
Date: 15 Aug 92 04:27:08 GMT
Reply-To: chris@peregrine (Chris Cole)
Organization: Peregrine Systems, Inc.

In article <ueLgPB1w164w@cellar.org> kml@cellar.org (Lazlo Hoover Toth) writes:
>1, 11, 21, 1211, 111221, ..., ...
This puzzle is on the rec.puzzles FAQL (Frequently Asked Questions List).
For an index of the FAQL, send an email letter containing the single line:
send index
to netlib@peregrine.com

The index will be mailed via return email to the address in your
request's "From:" line.  If you are unsure of this address, and cannot
edit this line, then include in your message BEFORE the first "send" line
the line:

return_address <your_return_email_address>

From the FAQL, the answer is:
Each line is derived from the last by the transformation (for example)

... z z z x x y y y ... ->
... 3 z 2 x 3 y ...

John Horton Conway analyzed this in "The Weird and Wonderful Chemistry
of Audioactive Decay" (T M Cover & B Gopinath (eds) OPEN PROBLEMS IN
COMMUNICATION AND COMPUTATION, Springer-Verlag (1987)).  You can also
find his most complete FRACTRAN paper in this collection.

First, he points out that under this sequence, you frequently get
adjacent subsequences XY which cannot influence each other in any
future derivation of the sequence rule.  The smallest such are
called "atoms" or "elements".  As Conway claims to have proved,
there are 92 atoms which show up eventually in every sequence, no
matter what the starting value (besides <> and <22>), and always in
the same non-zero limiting proportions.

Conway named them after some other list of 92 atoms.  As a puzzle,
see if you can recreate the list from the following, in decreasing
atomic number:

U Pa Th Ac Ra Fr Rn Ho.AT Po Bi Pm.PB Tl Hg Au Pt Ir Os Re Ge.Ca.W Ta
HF.Pa.H.Ca.W Lu Yb Tm ER.Ca.Co HO.Pm Dy Tb Ho.GD EU.Ca.Co Sm PM.Ca.Zn
Nd Pr Ce LA.H.Ca.Co Ba Cs Xe I Ho.TE Eu.Ca.SB Pm.SN In Cd Ag Pd Rh
Ho.RU Eu.Ca.TC Mo Nb Er.ZR Y.H.Ca.Tc SR.U Rb Kr Br Se As GE.Na Ho.GA
Eu.Ca.Ac.H.Ca.ZN Cu Ni Zn.CO Fe Mn CR.Si V Ti Sc Ho.Pa.H.CA.Co K Ar
Cl S P Ho.SI Al Mg Pm.NA Ne F O N C B Be Ge.Ca.LI He Hf.Pa.H.Ca.Li

Uranium is 3, Protactinium is 13, etc.  Rn => Ho.AT means the following:
Radon forms a string that consists of two atoms, Holmium on the left,
and Astatine on the right.  I capitalize the symbol for At to remind
you that Astatine, and not Holmium, is one less than Radon in atomic
number.  As a check, against you or me making a mistake, Hf is 111xx,
Nd is 111xxx, In and Ni are 111xxxxx, K is 111x, and H is 22.

Next see if you can at least prove that any atom other than Hydrogen,
eventually (and always thereafter) forms strings containing all 92 atoms.

The grand Conway theorem here is that every string eventually forms (within
a universal time limit) strings containing all the 92 atoms in certain
specific non-zero limiting proportions, and that digits N greater than 3
are eventually restricted to one of two atomic patterns (ie, abc...N and
def...N for some {1,2,3} sequences abc... and def...), which Conway calls
isotopes of Np and Pu.  (For N=2, these are He and Li), and that these
transuranic atoms have a zero limiting proportion.

The longest lived exotic element is Methuselum (2233322211N) which takes
about 25 applications to reduce to the periodic table.

-Matthew P Wiener (weemba@libra.wistar.upenn.edu)

Conway gives many results on the ultimate behavior of strings under
this transformation: for example, taking the sequence derived from 1
(or any other string except 2 2), the limit of the ratio of length of
the (n+1)th term to the length of the nth term as n->infinity is a 
fixed constant, namely

            1.30357726903429639125709911215255189073070250465940...

This number is from Ilan Vardi, "Computational Recreations in Mathematica",
Addison Wesley 1991, page 13.

Another sequence that is related but not nearly as interesting is:

1, 11, 21, 1112, 3112, 211213, 312213, 212223, 114213, 31121314, 41122314,
    31221324, 21322314,

and 21322314 generates itself, so we have a cycle.