From: chris@questrel.com (Chris Cole)
Newsgroups: rec.puzzles
Subject: Re: Sequence (How to get the FAQL)
Date: 18 Nov 92 08:33:33 GMT
Organization: Questrel, Inc.

In article <19921116.170715143595.NETNEWS@BLEKUL11> pirard@vm1.ulg.ac.be (Andre' Pirard) writes:
>1
>11
>21
>1211
>111221
>?
>
This question is on the rec.puzzles Frequently Asked Questions List (FAQL).
To request a copy of the index to the FAQL, send a letter to
faql-request@questrel.com
containing the line:
send index

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>

The FAQL has been posted to news.answers.  News.answers is archived in
the periodic posting archive on pit-manager.mit.edu [18.172.1.27].
Postings are located in the anonymous ftp directory
/pub/usenet/news.answers, and are archived by "Archive-name".  Other
subdirectories of /pub/usenet contain periodic postings that may not
appear in news.answers.

Other news.answers/FAQ archives (which carry some or all of the FAQs
in the pit-manager archive) are:

	ftp.cs.ruu.nl [131.211.80.17] in the anonymous ftp
		directory /pub/NEWS.ANSWERS (also accessible via mail
		server requests to mail-server@cs.ruu.nl)
	cnam.cnam.fr [192.33.159.6] in the anonymous ftp directory /pub/FAQ
	ftp.uu.net [137.39.1.9 or 192.48.96.9] in the anonymous ftp
		directory /usenet
	ftp.win.tue.nl [131.155.70.100] in the anonymous ftp directory
		/pub/usenet/news.answers
	grasp1.univ-lyon1.fr [134.214.100.25] in the anonymous ftp
		directory /pub/faq (also accessible via mail server
		requests to listserv@grasp1.univ-lyon1.fr), which is
		best used by EASInet sites and sites in France that do
		not have better connectivity to cnam.cnam.fr (e.g.
		Lyon, Grenoble)

Note that the periodic posting archives on pit-manager.mit.edu are
also accessible via Prospero and WAIS (the database name is "usenet"
on port 210).

From the FAQL, the answer is:


********
series/series.07.s
********
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.
Newsgroups: rec.puzzles