CLR cover
Previous problem

Problem 6: Fibonacci Words and Fibonacci Numeration System

Next problem
\( \def\sa#1{\tt{#1}} \)

Let $r(m)$ denote the Fibonacci representation of a non-negative integer $m$. It is a word $x$ of length $\ell$ on the alphabet $\{\sa{0},\sa{1}\}$ ending with $\sa{1}$ except for $m=0$, containing no two consecutive occurrences of $\sa{1}$ and that satisfies $m = \sum_{i=0}^{\ell-1} x[i]\cdot F_{i+2}$, where $F_{i+2}$ is the $(i+2)$th Fibonacci number (recall that $F_{0}=0$, $F_{1}=1$, $F_{2}=1$, $F_{3}=2$, etc.).

For example: $r(0)=\sa{0}$, $r(1)=\sa{1}$, $r(2)=\sa{01}$, $r(3)=\sa{001}$, $r(4)=\sa{101}$, $r(5)=\sa{0001}$, $r(6)=\sa{1001}$, $r(7)=\sa{0101}$.

Note that the usual positional Fibonacci representation of an integer $m$ is $r(m)^\mathrm{R}$, the reverse of $r(m)$. Also note that Fibonacci coding used to encode an integer $m$ in a data stream is $r(m)\sa{1}$, terminating with $\sa{11}$ to allow its decoding.

Show that the sequence of first digits of Fibonacci representations of natural numbers in increasing order is the infinite Fibonacci word when letters are identified to digits: $\sa{a}$ to $\sa{0}$, $\sa{b}$ to $\sa{1}$.

Let $pos(k,c)$, $k\gt 0$, denote the position of the $k$th occurrence of letter $c$ in the infinite Fibonacci word $\mathbf{f}$.

Show how to compute the position of the $k$th occurrence of letter $\sa{a}$ in the Fibonacci word $\mathbf{f}$ in time $O(\log k)$. The same applies for letter $\sa{b}$.
Show the following formulas: $r(pos(k,\sa{a})) = \sa{0}\cdot r(k-1)$ and $r(pos(k,\sa{b})) = \sa{10}\cdot r(k-1)$}

References

  • W. Rytter. Computing the k-th letter of Fibonacci word. Personal communication, 2017.