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