Let $(a_n)$ be a sequence of integers, with $a_1 = 1$ and for evert integer $n \ge 1$, $a_{2n} = a_n + 1$ and $a_{2n+1} = 10a_n$. How many times $111$ appears on this sequence?
Problem
Source: Rio de Janeiro Mathematical Olympiad 2018, Level 4, #2
Tags: number theory, combinatorics
rchokler
18.11.2019 02:09
If no $\times10$ steps, we get $1$ routes. If $1$ step of $\times 10$ then there are $11$ routes since this step happens before you exceed $11$. If $2$ step of $\times 10$ then there are $2$ routes since the first such step must happen immediately. There are no routes involving more than $2$ steps of $\times 10$. That is a total of $14$ routes. This is also how many times $111$ happens since every positive integer is uniquely reachable from $1$ by a sequence of $n\mapsto 2n$ and $n\mapsto 2n+1$ moves. The indices where $111$ happens are: $14$ $4098$ $14336$ $2099200$ $1075838976$ $551903297536$ $283673999966208$ $146366987889541120$ $76092819304051900416$ $40140115104391984316416$ $21760664753063325144711168$ $12379400392853802748991242240$ $7605903601369376408980219232256$ $1298074214633706907132624082305024$
Letteer
18.11.2019 18:07
I get $14$ times. The number of times $n$ appears is the number of ways to reach $n$ by starting with $1$ and either adding $1$ or multiplying by $10$. If $f(n)$ is the number of ways $n$ appears we have the recurrence
$$f(n)=\begin {cases} 1&n=1\\
f(n-1)&n \not \equiv 0 \pmod {10}\\
f(n-1)+f(\frac n{10})& n \equiv 0 \pmod {10} \end {cases}$$We have $f(100)=12$ because you can add $1\ 100$ times, you can multiply by $10$ twice, or you can add $1$ a number of times from $0$ to $9$, multiply by $10$ and add $1$ enough other times to get to $100$