Interesting sequence question

Question

I saw a puzzle the other day and it was as follows:

Find the next number in the sequence: 1 11 21 1211 111221 312211 ...

If anyone wants to have a go at the puzzle I'll put the solution in a spoiler

Next number: 13112221 - 1 three, 1 one, 2 twos, 2 ones

My question is - what mathematical machinery is there to analyse a sequence like this? I can see that $2^n$ is an upper bound for the number of digits (if all digits in the previous number are different), but I'm wondering if one could do better, or get a lower bound as well, or maybe analyse it from a completely different direction.

I wrote a simple python script to calculate the sequence as follows (note: the actual value can get very big - and you can remove it from the array)

import math

def next_number(num):
  num = list(str(num))
  position = -2
  output = []
  prev_char = None # anything other than a number
  for char in num:
    if char == prev_char:
      output[position] += 1
    else:
      output += [1, int(char)]
      position += 2
      prev_char = char
  output = [str(i) for i in output]
  return int(''.join(output))

def calculate_sequence(count):
  num = 1
  ans = []
  for count in xrange(count):
    length = math.floor(math.log10(num)) + 1
    ans.append([count+1, length, num])
    num = next_number(num)
  return ans

Answer 1

As complexist said, there's a wikipedia article about it which links to some good sources with explanations of the statements of key theorems (including the famous Cosmological Theorem, which says that there is a global bound after which every look-and-say sequence breaks up into a bunch of predictable pieces) whose original proofs have been lost.

Litherland and Ekhad and Zeilberger both have computerized proofs of things approaching Conway's original claims, but they don't achieve the bounds Conway claimed, and these proofs are difficult to verify.

More recently, Kevin Watkins at CMU wrote a paper and slides explaining how you could use Haskell and words to produce an explicitly human-understandable computer-aided proof of the main theorems (which still doesn't yield the originally claimed bounds).

There has also been a tidy blog post by Nathaniel Johnston explaining the derivation of the asymptotic growth rate.