3
$\begingroup$

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
$\endgroup$
3
  • 4
    $\begingroup$ Wikipedia reference: en.wikipedia.org/wiki/Look-and-say_sequence $\endgroup$ – complexist May 23 '14 at 14:32
  • $\begingroup$ For one thing, it's very easy to prove that no digit apart from 1,2 and 3 will occur in the sequence. $\endgroup$ – sayantankhan May 23 '14 at 14:34
  • 1
    $\begingroup$ Well that's boring! It's already been studied! $\endgroup$ – derekdreery May 23 '14 at 14:34
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.