Convergence and limit for Collatz type of recurrence

Question

Let $x_0=1$ and

$$x_{n+1}= 2+3\cdot\frac{x_n}{2} \mbox{ if } x_n \mbox{ is even}, $$ $$x_{n+1}= 1+3\cdot x_n \mbox{ otherwise}.$$ Let $$z_n = \frac{\log x_n}{n}.$$

I have numerous questions regarding this sequence. It looks almost like the sequence in the Collatz conjecture, but its behavior is totally different. My main question is whether $z_n$ converges or not.

The other questions (and I don't expect an answer for these) are

• What is the value of $\lim_{n\rightarrow\infty} z_n$?
• Are the binary digits of $x_n$ evenly distributed as $n\rightarrow\infty$?
• On average, is $x_n$ even 50% of the time?

Below is a plot of $z_n$ for the first 5,000 values of $n$:

For convenience, below is the piece of code (Perl) that I used for my computations. If you find some issues with it, let me know. It's very basic, based on a brute-force algorithm, except for the fact that it uses exact arithmetic with numbers that have hundreds (or more) digits.

use strict;
use bignum;

my $x;
my $k;
my $logx;

$x=1;

open(OUT,">collatz.txt");
for ($k=1; $k<5000; $k++) {
 if ($x % 2  == 0) {
   $x = $x >> 1;  # divide by 2
   $x=2+3*$x;
 } else {
   $x =1 + 3*$x;
 }
 if ($k%5 == 0) { print "$k\n"; select()->flush(); }
 if ($k%25 == 0) { 
   $logx=log($x)/$k; 
   print OUT "$k\t$logx\n";
 }
}
close(OUT);

Answer 1

This answer lacks mathematical rigor, but I went further than simply answering my main question.

Let $y_k = x_k/x_{k-1}$ for $k>0$. Clearly, as $k\rightarrow\infty$, the ratio $y_k$ gets closer and closer to either $3$ or $\frac{3}{2}$, alternating (at the limit) between these two values in a non-periodic way. The distribution of these two values is reminiscent of the distribution of the binary digits of an non-normal irrational number. On average, $\frac{3}{2}$ appears twice as frequently as $3$, as $k\rightarrow\infty$.

In other words, we have the following fact:

$$x_n = C_n \cdot \Big(\frac{3}{2}\Big)^{2n/3} \cdot 3^{n/3} =C_n \cdot 3^n \cdot 2^{-2n/3},$$

with $$0 <\lim_{n\rightarrow\infty}\inf C_n <\lim_{n\rightarrow\infty}\sup C_n<\infty.$$

As a result, we have: $$\lim_{n\rightarrow \infty} z_n =\log 3 - \frac{2}{3}\log 2.$$

This result is confirmed by empirical evidence. In the few cases that I tried, using a different recurrence, whenever the behavior was truly periodic, I was able to get a closed form for $x_n$. An example of such recurrence is given by $x_0 = a$ and

$$x_{n+1}= b+3\cdot\frac{x_n}{2} \mbox{ if } x_n \mbox{ is even}, $$ $$x_{n+1}= c+\frac{4}{3}\cdot( x_n-\mbox{mod}(x_n,3)) \mbox{ otherwise}.$$ Periodicity occurs in the following cases:

Case 1: $a=3, b=0, c=0$: We have

$$x_{3n} = 3^{n+1}, x_{3n+1} = 4\cdot 3^{n}, x_{3n+2} = 2\cdot 3^{n+1}$$

Case 2: $a=3, b=2, c=2$: If $n>0$, we have

$$x_{2n} = 3\cdot 2^{n+1} - 1, x_{2n+1} = 2^{n+3} - 2$$