## 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 *L _{n}* is the number of digits in the

*n*-th element of the sequence, then

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:

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.

My Haskell solution (see http://bonsaicode.wordpress.com/2011/03/28/programming-praxis-look-and-say-revisited/ for a version with comments):

[…] today’s Programming Praxis exercise, our goal is to calculate Conway’s constant. Let’s get […]

Cheating with Sage:

I’ll come up with a real solution soon.

Your polynomial appears to have some typos, and doesn’t match what is shown at Mathworld. For example, see the x^61 term.

Fixed. Thanks.

As it turns out, I should have used

`find_root(f, 1, 2)`

in Sageinstead. As for my own code, I went for Newton’s Method. It requires knowing

the derivative of your function (simple enough to calculate for polynomials),

so I wrote a second Horner’s Rule to build it. The nice thing about Newton’s

Method is that if the function is reasonably well-behaved in the neighborhood

of interest, it converges quadratically to the root.

Come to think of it, I didn’t actually use Horner’s Rule to construct my

polynomials, just the naive definition. Apologies on misnaming my functions!

A version that actually uses Horner’s Rule:

My c++ solution :)

Factor solution. Interesting that if epsilon is set to 1e-8, Newton’s method doesn’t converge to that precision. Instead it alternately cycles between 1.303577269034296 and 1.303577269034297 until the iteration count breaks the cycle. If the precision is set to 1e-7, it converges rapidly (5 iterations) to 1.303577269034296.

( scratchpad ) conway-constant .

1.303577269034296

( scratchpad )