Let $(a_n)$ be a sequence of integers, with $a_1 = 1$ and for every integer $n \ge 1$, $a_{2n} = a_n + 1$ and $a_{2n+1} = 10a_n$. How many times does $111$ appear in this sequence?

Let's think step by step and output the final answer within \boxed{}.
user