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).