Can You Unravel These Number Strings?

Riddler Express

Six numbers are given in sequence: $1,\ 11,\ 21,\ 1211,\ 111221,\ 312211$. What is the next number?

The Riddler, FiveThirtyEight, August 18, 2017(original post)

Solution

This is the look-and-say sequence: each term describes its predecessor digit by digit, by reading aloud the consecutive runs as “$k$ copies of $d$”.

Apply the rule to the sixth term: $$312211 \;\longrightarrow\; \underbrace{\text{one $3$}}_{13}\, \underbrace{\text{one $1$}}_{11}\, \underbrace{\text{two $2$s}}_{22}\, \underbrace{\text{two $1$s}}_{21} \;=\; 13112221.$$

$$\boxed{\,13112221.\,}$$

A standing fact about this sequence (due to John Conway): consecutive terms grow by a constant factor in the limit, namely Conway’s constant $\lambda \approx 1.3036$, the only positive real root of a degree-$71$ polynomial. The sequence never contains a digit other than $1$, $2$, or $3$ once those are the only digits that appear (Conway’s “cosmological theorem”), so the look-and-say can never trigger itself into using a $4$ or larger.

The computation

Encode the look-and-say rule directly: walk the string, count each run, emit “count digit” pairs. Apply seven times from the seed $1$ and check the seventh iterate.

1. Start with the string “$1$”.

2. To advance: scan the current string left to right, finding maximal runs of equal digits.

3. For each run of $k$ copies of digit $d$, emit the two-digit pair $kd$.

4. Iterate.

def look_and_say(s):
    out = []
    i = 0
    while i < len(s):
        j = i
        while j < len(s) and s[j] == s[i]:
            j += 1
        out.append(str(j - i))
        out.append(s[i])
        i = j
    return "".join(out)

s = "1"
for _ in range(6):
    s = look_and_say(s)
print(s)                                         # 13112221
# match against the six given terms plus our answer
seq = ["1"]
for _ in range(6):
    seq.append(look_and_say(seq[-1]))
print(seq)
# ['1', '11', '21', '1211', '111221', '312211', '13112221']

The seventh iterate is $13112221$, agreeing with the boxed answer.

Riddler Classic

Take the self-referential string $$333\ 2\ 333\ 2\ 333\ 2\ 33\ 2\ 333\ 2\ 333\ 2\ 333\ 2\ 33\ 2\ \ldots,$$ where each digit (ignoring spaces) gives the count of consecutive $3$s before the next $2$. The first digit, $3$, says there are three $3$s before the first $2$; the second digit, $3$, says there are three $3$s between the first and second $2$s; and so on. What is the limiting ratio of $3$s to $2$s in the infinite string?

The Riddler, FiveThirtyEight, August 18, 2017(original post)

Solution

Define a recursive construction. Generation $1$ is the single digit “$3$”. Generation $n + 1$ is obtained from generation $n$ by replacing each digit using the rule it imposes on the string: a $3$ in generation $n$ says “three $3$s follow before a $2$”, so it expands to the block $\textbf{3332}$; a $2$ in generation $n$ says “two $3$s before a $2$”, so it expands to $\textbf{332}$. Each expansion contributes one $2$ (the terminating one), and either three or two $3$s.

Let $T_n$ and $W_n$ denote the count of $3$s and $2$s in generation $n$. The expansion rule gives the linear recursion $$\begin{aligned} T_{n+1} &= 3\,T_n + 2\,W_n, \\ W_{n+1} &= T_n + W_n. \end{aligned}$$ Each generation $n$ digit produces exactly one $2$ in the next generation (the explicit terminator of its block), giving the $W$ recursion; and a $3$ contributes three $3$s while a $2$ contributes two, giving the $T$ recursion.

Let $r_n = T_n / W_n$. Dividing the two recursions, $$r_{n+1} = \frac{3 T_n + 2 W_n}{T_n + W_n} = \frac{3 r_n + 2}{r_n + 1}.$$ This is a Möbius (linear-fractional) iteration. Its fixed points satisfy $r = (3r + 2)/(r + 1)$, that is $r^2 + r = 3r + 2$, i.e., $r^2 - 2r - 2 = 0$. The positive root is $$r = 1 + \sqrt{3} \approx 2.7321.$$ The other root $1 - \sqrt{3} < 0$ is irrelevant since counts are positive. The map $f(r) = (3r + 2)/(r + 1)$ has derivative $f'(r) = 1/(r + 1)^2$; at the positive fixed point $r = 1 + \sqrt{3}$ this is $1/(2 + \sqrt{3})^2 \approx 0.072$, which is less than $1$ in absolute value, so the fixed point is an attractor and $r_n \to 1 + \sqrt{3}$ from any positive start.

The infinite string is the limit of these generations (each generation is a strict prefix of the next), so the overall ratio of $3$s to $2$s is $$\boxed{\,r = 1 + \sqrt{3} \approx 2.7321.\,}$$

The computation

Iterate the actual substitution rule on strings: start with “$3$”, and at each step replace every $3$ by $3332$ and every $2$ by $332$. Confirm that the empirical ratio $T_n / W_n$ converges to $1 + \sqrt{3}$.

1. Seed with the single character “$3$”.

2. At each step, build the next-generation string by concatenating $3332$ for each $3$ and $332$ for each $2$.

3. Track counts of $3$s and $2$s and form the ratio.

import math
s = "3"
for n in range(1, 12):
    s = "".join("3332" if c == "3" else "332" for c in s)
    t, w = s.count("3"), s.count("2")
    print(n + 1, t, w, round(t / w, 6))
# generation 12 ratio prints ~2.732050
print("target:", 1 + math.sqrt(3))               # 2.732050807568877

By generation $12$ the empirical $T_n / W_n$ matches $1 + \sqrt{3}$ to six decimals.