SPOILER B: - - - - - - - - - - - - - - - - - - - - - - - - - - -
                                            Torsten Sillke, 7. Apr. 1993

   The binary form of Conway's sequence:
   1, 11, 101, 111011, 11110101, 100110111011, ...

The Rule:
  binary-run-length-encoding

      100110111011 is 

   (1 times 1, 2 times 0, 2 times 1, 1 times 0, 3 times 1, 1 times 0, 2 times 1)  and binary
   (1 times 1, 10 times 0, 10 times 1, 1 times 0, 11 times 1, 1 times 0, 10 times 1)
   and concatenating all strings gives:

      111001011011110101


Question:
  How many digits has the n-th term?

Hint:
  Find the 'atoms' in this series. This is a very easy problem.
  The term atom originates from Conway (Eureka 46).
  Then you can compute the lenght of the n-th iterate.


Atom Decay:  10 Atoms are in use for the decay of A1.

( A0       ->  A10 )
  A1       ->  A11
  A11      ->  A10 A1
( A111     ->  A111         (stable) )
( A1111    ->  A100 A1 )
  A10      ->  A1110
  A110     ->  A10 A110
  A1110    ->  A11110
  A11110   ->  A100 A110
  A100     ->  A11100
  A1100    ->  A10 A1100
  A11100   ->  A111100
  A111100  ->  A100 A1100

  Writing the series in the atom notation gives:

  A1
  A11
  A10 | A1
  A1110 | A11
  A11110 | A10 | A1
  A100 A110 | A1110 | A11
  A11100 A10 | A110 A11110 | A10 | A1
  A111100 A1110 A10 A110 | A100 A110 | A1110 | A11
  A100 A1100 A11110 A1110 A10 A110 | A11100 A10 | A110 A11110 | A10 | A1

  The transition-matrix T of the 10 used atoms has the form:

  [01........]
  [101.......]
  [..00100000]
  [..11000000]
  [..00010000]
  [..01001000]  =  T
  [..00000010]
  [..10000100]
  [..00000001]
  [..00001100]

  Note that '.' stands for 0. T is a block triangular matrix.
  The characteristic polynomial det(xI - T) gives a recurrence relation for the
  number of atom as well as the number of '0' or '1' or the total number of 
  digits.  The largest eigenvalue of this matrix gives the asymtotic
  length of the n-th term.


The first 30 term of the number of digits of the series:

  1 2 3 6 8 12 18 27 39 58 85 125 183 269 394 578 847 1242 1820 2668
    3910 5731 8399 12310 18041 26441 38751 56793 83234 121986 178779

  Asymtotic:  c1 * 1.465571232^n
  

The number of atoms of the series beginning with A10:

  1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 595 872 1278
    1873 2745 4023 5896 8641 12664 18560 27201 39865 58425 85626 125491

  recurrence: a = ( 4 a   + 2 a   + 3 a   + 2 a   - a   + a   )/5
               n       n-1     n-2     n-3     n-4   n-5   n-6

  Asymtotic:  a_n = c2 * 1.465571232^n


Reference: (Conway's sequence)

- J. H. Conway,
   The Weird and Wonderful Chemistry of Audioactive Decay,
   Eureka 46 (1986) 5-16, reprinted in:
   Open Problems in Communications and Computations, Springer, 1987, 173-188

Decay Diagram: 
   A loop is indicated by ().

                      1
                      ^
                      |
                      v
                     11
                      |
                      v
       () 1100 --->  10
             ^        | ^
             |        v  \
        111100     1110   110 ()
       ^     |        |   ^
      /      v        v  /
  11100 <- 100 <- 11110