Density of odd numbers in a sequence relating base 2 and base 3 expansion

Define the function $$f(4n)=6n+1\\ f(4n+1)=6n+2\\ f(4n+2)=6n+3\\ f(4n+3)=6n+5$$ and the sequence $u_0=2$, $u_{k+1}=f(u_k)$.

Let $d_1\le d_2$ be the lower and upper asymptotic density of odd numbers in $u_k$.

Since $f(n)$ is odd for even $n$, no two consecutive terms can be even so obviously $d_1\ge 1/2$. Experimentally, it seems reasonable to conjecture $d=d_1=d_2=2/3$.

Heuristically, when $n$ is odd, $f(n)$ has "probability 1/2" to be even, so we get this Markov chain:

which is consistent with $d=2/3$. But can we prove rigorously that the heuristic works, that is that $u_k$ is "random enough" for this to be true? Failing that, a sharper lower bound on $d_1$ could still be an interesting result.

(One approach could be to let $a_k=1$ if $u_k$ is even and $0$ otherwise, and examine the probabilities of the $p$-bit subwords $(a_k,\dots,a_{k+p-1})$. Unfortunately every Fibonacci word, that is one not containing the pattern 11, seems to appear infinitely frequently in $a_k$. This is consistent with the Markov chain model.)

PS: If you're wondering, the problem arose from this question.

Response to comments:

• Someone suggested to work modulo some larger number, such as 12. The problem with this approach is that if the input is considered mod $2^a 3^b$, the output will only be known mod $2^{a-1} 3^{b+1}$ so you're not going to be able to say much about the behavior of $f$ when iterating more than $a$ times. And it seems that $010101\dots$ can always appear as a subword of $a_k$, so you won't be able to prove anything non-trivial about the density by proving something about the density after $k$ iterations starting from an arbitrary state (that is, by examining $f^k$ for bounded $k$).
• The first few terms are 2, 3, 5, 8, 13, 20, 31, 47, 71, 107, 161, 242. The sequence grows as $\Theta((3/2)^n)$. Interestingly, notice how closely the first few terms match the Fibonacci sequence (which can be explained by how close $3/2$ is to the golden ratio and by the fact that modulo 2, neither sequence contains the pattern 00).

Solution 1:

This is an extended comment:

Looking at the first ten thousand terms (so up to about $1.5285 \times 10^{1761}$), it looks as if the conjecture may be true. $6610$ of the terms are odd, which is slightly lower than predicted by the conjecture but not substantially so. Graphs of the cumulative proportion odd look like

or with a more helpful scale

There is an obvious fall after $1250$ terms

so while $834$ of the first $1251$ terms are odd (exactly two-thirds), only $453$ of the next $711$ terms are odd rather than the expected $474$, and this keeps the cumulative proportion below $\frac23$ for the remainder of the observations.

Even this does not seem an extreme excursion to me (for a binomial distribution it is smaller than two standard deviations away from the expected value), so I would guess the conjecture is true, even though the truth of the conjecture depends on behaviour in the tail rather than in the initial terms.