Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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:

Transition diagram

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).
share|improve this question
2  
It may be helpful to post some raw data about what the sequence looks like for 100 or so terms. –  Ragib Zaman Jun 14 '12 at 15:33
add comment

1 Answer

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

enter image description here

or with a more helpful scale

enter image description here

There is an obvious fall after $1250$ terms

enter image description here

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.