The 100(th) Problem

Calculus Level 3

Consider the binary look-and-say sequence : $1,{\color{#D61F06}1}1,{\color{#D61F06}10}1,{\color{#D61F06}1}1{\color{#D61F06}1}0{\color{#D61F06}1}1,{\color{#D61F06}11}1{\color{#D61F06}1}0{\color{#D61F06}10}1,$ and so on.

Let $f(n)$ denote the times the string "100" appears in the $n^\text{th}$ term. Then $f(8)=2,$ for example, because the $8^\text{th}$ term equals $111{\color{#D61F06}100}111010110{\color{#D61F06}100}110111011.$

What is $\displaystyle\lim_{n\to\infty}\frac{f(n)}{f(n-1)}?$

The answer is 1.4656.

3 solutions

Mark Hennings
Aug 13, 2018

The terms in this sequence can all be expressed as collections of 10 specific subsequences. The table below details the particular subsequences, and what each subsequence contributes to the next generation $\begin{array}{ccc} \hline \mathrm{Label} & \mathrm{Sequence} & \mathrm{Becomes} \\ \hline A & 1 & B \\ B & 11 & CA\\ C & 10 & E \\ D & 110 & CD \\ E & 1110 & F \\ F & 11110 & GD \\ G & 100 & I \\ H & 1100 & CH \\ I & 11100 & J \\ J & 111100 & GH \\ \hline \end{array}$ Thus if the subsequence A occurs $v(n)_1$ times, the subsequence B occurs $v(n)_2$ times, the subsequence C occurs $v(n)_3$ times, ..., and the subsequence J occurs $v(n)_{10}$ times in the $n$ th term of this sequence, then $v(n+1) \; = \; Mv(n)$ where $M \; = \; \left(\begin{array}{cccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \end{array} \right)$ and so $f(n) \; = \; \left( \begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 \end{array}\right)^T M^{n-1} \left(\begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\right)$ The characteristic polynomial of $M$ is $\chi_M(t) \; = \; t^4(t-1)^2(t+1)(t^3 - t^2 - 1)$ and some standard linear algebra tells us that $\lim_{n \to \infty} \frac{f(n)}{f(n-1)}$ is equal to the largest real eigenvalue of $M$ , which is the real root of $t^3 - t^2 - 1 = 0$ , namely $\boxed{1.46557}$ .

Did you diagonalize M? I tried to but I couldn't find enough eigenvectors. By the way there's a small typo in the table: label G becomes I, not J.

Nate Jellis - 2 years, 9 months ago

Thanks for pointing out the typo.

As to diagonalising $M$ , I did not have to. I am not even sure if $M$ can be diagonalised. It can, however, certainly be put in Jordan normal form, so the lack of diagonalisability may be due so some Jordan blocks with eigenvalue $0$ of size up to $4$ , and possibility a Jordan block with eigenvalue $1$ of size $2$ . The first of these will contribute nothing to $f(n)$ for large $n$ , since these Jordan blocks are nilpotent. The other Jordan block may contribute terms of order $n$ to $f(n)$ , since $\left(\begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array}\right)^n \; = \; \left(\begin{array}{cc} 1 & n \\ 0 & 1 \end{array}\right)$ but any such term will be overwhelmed by the terms in $f(n)$ of the order $1.46557^n$ .

Thus we only need consider the largest eigenvalue of $M$ .

Mark Hennings - 2 years, 9 months ago

Thank you. After doing some research, I think I have put it in Jordan normal form. It turns out there is no Jordan block of size 2. The numbers $r_1$ , $r_2$ , and $r_3$ are the roots of $t^3-t^2-1$ , two of which are non-real complex numbers. I have confirmed that $MP=PJ$ .

$P \; = \; \left(\begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 1 & 3 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & -3 & 0 & 0 & 0 \\ 0 & 0 & -1 & 1 & 0 & 0 & 4 & r_1^2 & r_2^2 & r_3^2 \\ 1 & 0 & 0 & 0 & 1 & 0 & -2 & r_1^2 & r_2^2 & r_3^2 \\ 0 & -1 & 1 & 0 & 0 & 0 & -4 & r_1 & r_2 & r_3 \\ -1 & 1 & 0 & 0 & 0 & 0 & 4 & 1 & 1 & 1 \\ 0 & 0 & 1 & -1 & 0 & 0 & -2 & 1 & 1 & 1 \\ -1 & 0 & 0 & -1 & -1 & -1 & 1 & 1 & 1 & 1 \\ 0 & 1 & -1 & 0 & 0 & 0 & 2 & 1/r_1 & 1/r_2 & 1/r_3 \\ 1 & -1 & 0 & 1 & 0 & 0 & -2 & 1/r_1^2 & 1/r_2^2 & 1/r_3^2 \end{array}\right), \; J \; = \; \left(\begin{array}{cccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & r_1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & r_2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & r_3 \end{array}\right)$

Nate Jellis - 2 years, 9 months ago

@Nate Jellis – That makes things easy...

Mark Hennings - 2 years, 9 months ago

@Nate Jellis – It is even simpler to note that $M$ has only one eigenvector of eigenvalue $0$ , namely $\left(\begin{array}{c} 0 \\ 0 \\ 0 \\ 1 \\ 0 \\ -1 \\ 0 \\ -1 \\ 0 \\ 1 \end{array}\right)$ while it has two eigenvectors of eigenvalue $1$ , namely $\left(\begin{array}{c} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ -1 \\ 0 \\ 0 \end{array}\right) \hspace{2cm} \left(\begin{array}{c} 1 \\ 1 \\ 0 \\ -1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\right)$ Thus the Jordan normal form for $M$ contains a single Jordan block with eigenvalue $0$ and size $4$ , and is otherwise diagonal. In other words, the JNF for $M$ is indeed the matrix $J$ .

Mark Hennings - 2 years, 9 months ago

How does a zero end up in a look-and-say sequence? Especially as an unmatched term ("101")? Yes, one 0, but one what? It seems to be somewhat arbitrarily inserted. Zero 0s is a sequence that has to be grabbed out of thin air.

Bert Seegmiller - 2 years, 9 months ago

If you look at the transition table, you will see that C always occurs succeeded by either A, D, or H. Thus means that there is always something after the final 1 in the C to make sense... Give it a try...

Mark Hennings - 2 years, 9 months ago

This is a binary look-and-say sequence… not a base-10 one. Since in binary, '2' -> '10', we can say that '11' -> '101', that is, two ones.

Look = say 1 = 'one' 1-1 = 'one-one' 10-1 = 'two-ones' 1-1, 1-0, 1-1 = 'one-one, one-zero, one-one' 11-1, 1-0, 10-1 -> 'thee-ones, one-zero, two-ones' …… and so on.

Looking at the ternary look-and-say sequence, we find it has zeros also:

Look = say 1 = 'one' 1-1 = 'one-one' 2-1 = 'two-ones' 1-2, 1-1 = 'one-two, two ones' 1-1, 1-2, 2-1 = 'one-one, one-two, two-ones' 10-1, 2-2, 1-1 = 'three-ones, two-twos, one-one' …… and so on.

Starting with a single 'one' doesn't produce zeros within the sequence for any base higher than four, however. But that's how you get zeros in a look-and-say sequence using base 2 or base 3.

Tristan Hauber - 2 years, 7 months ago

How can we generate the transition table? Is there more details about the transition table?

LosAnky Raw - 2 years, 9 months ago

The important thing is to choose subsequences that don't interact with each other. For example the fourth term is broken up like this: 1110 / 11. If you "look and say" the first part you get 11110. If you do the second part you get 101. Combined, that's 11110101, which is the correct value of the fifth term.

Notice that C through J each start with 1 and end with 0. Anything with this property will continue to have this property under the rules because the binary numbers don't have any leading zeros.

Nate Jellis - 2 years, 8 months ago

Calvin Osborne
Aug 29, 2018

Here's a python program that will calculate the correct limit using a binary look-and-say method that utilizes a decimal to binary converter.

def decToBinary(num):
    ret = "";
    while(num > 0):
        ret = str(num % 2) + ret;
        num = int(num / 2);
    return int(ret);

def binaryLookAndSay(pSeq):
    seq = "";
    counter = 0;
    while(counter < len(pSeq)):
        n = 0;
        m = pSeq[counter];
        while(counter < len(pSeq) and pSeq[counter] == m):
            n += 1;
            counter += 1;
        seq += str(decToBinary(n));
        seq += str(m);
    return seq;

def f(seq):
    counter = 0;
    for i in range(0, len(seq) - 2):
        if(seq[i] + seq[i+1] + seq[i+2] == "100"):
            counter += 1;
    return counter;

sequence = "1";
prev = 0;
for i in range(0, 100):
    prev = f(sequence);
    sequence = binaryLookAndSay(sequence);
    if(prev != 0):
        print(f(sequence) / prev);
    else:
        print("0");

Vinod Kumar
Aug 28, 2018

The number of 10 distinct binary subsequences in a binary look and say sequence which include binary subsequence 100, grow according to matrix of order 10 (T-matrix). For details of binary look and say sequence and matrix T, check the link below:

http://www.njohnston.ca/2010/11/the-binary-look-and-say-sequence/

Starting only with first non-zero sub sequence-1 (1,0,0,0,0,0,0,0,0,0), we keep multiplying with T matrix of order 10, repeatedly and find the ratio of growth of 7th sub sequence-100 ( 7th entry in the eigen vector). Just after 40 multiplications the 7th entry of eigenvector f(40)=234813 and f(39)= 160229 converges to the ratio in the question f(40)/f(39)=1.46557.

This indeed is the power iteration method of finding the largest eigenvalue of a matrix.

The characterstic polynomial of the T matrix also shows a factor (x^3-x^2-1) whose zero is also equal to 1.4655, which is the largest eigenvalue of matrix T.

Thus, Answer=1.4655

The 100(th) Problem

The answer is 1.4656.

3 solutions

0 pending reports