Look And Say, Revisited

March 28, 2011

We calculated the look and say sequence in a previous exercise, and mentioned there that the sequence has some fascinating mathematical properties. One of them is that, if Ln is the number of digits in the n-th element of the sequence, then

\lim_{n \rightarrow \infty} \frac{L_{n+1}}{L_n} = \lambda

where λ is known as Conway’s constant, calculated by the British mathematician John Horton Conway as the unique positive real root of the following polynomial:

x^{71} - x^{69} - 2 x^{68} - x^{67} + 2 x^{66} + 2 x^{65} + x^{64} - x^{63} - x^{62} - x^{61} - x^{59} + 2 x^{58} + 5 x^{57} + 3 x^{56} - 2 x^{55} - 10 x^{54} - 3 x^{53} - 2 x^{52} + 6 x^{51} + 6 x^{50} + x^{49} + 9 x^{48} - 3 x^{47} - 7 x^{46} - 8 x^{45} - 8 x^{44} + 10 x^{43} + 6 x^{42} + 8 x^{41} - 5 x^{40} - 12 x^{39} + 7 x^{38} - 7 x^{37} + 7 x^{36} + x^{35} - 3 x^{34} + 10 x^{33} + x^{32} - 6 x^{31} - 2 x^{30} - 10 x^{29} - 3 x^{28} + 2 x^{27} + 9 x^{26} - 3 x^{25} + 14 x^{24} - 8 x^{23} - 7 x^{21} + 9 x^{20} + 3 x^{19} - 4 x^{18} - 10 x^{17} - 7 x^{16} + 12 x^{15} + 7 x^{14} + 2 x^{13} - 12 x^{12} - 4 x^{11} - 2 x^{10} + 5 x^9 + x^7 - 7 x^6 + 7 x^5 - 4x^4 + 12 x^3 - 6 x^2 + 3 x - 6

Conway analyzed the look and say sequence in his paper “The Weird and Wonderful Chemistry of Audioactive Decay” published in Eureka, Volume 46, Pages 5−18 in 1986. In his blog, Nathaniel Johnston gives a derivation of the polynomial.

Your task is to compute the value of λ. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisement

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
9 Comments »