Question similar to Collatz conjecture

Question

Let $a_0$ be an positive integer, define

$$ a_{n+1} = \begin{cases} a_n/2, & \text{if $a_n$ is even} \\ a_n+2a_0-1, & \text{if $a_n$ is odd} \end{cases}$$

Now form a sequence $S(a_0)_{n\ge 0}$ by performing this operation repeatedly.

Example: let $a_0=9$ then sequence $S(9)=\{9,26,13,30,15,32,16,8,4,2,1\}$

1 Question: For every $a_0$, sequence $S(a_0)$ will eventually reach the number $1$?

More example

S(1): 1

S(2): 2 1

S(3): 3 8 4 2 1

S(4): 4 2 1

S(5): 5 14 7 16 8 4 2 1

S(6): 6 3 14 7 18 9 20 10 5 16 8 4 2 1

S(7): 7 20 10 5 18 9 22 11 24 12 6 3 16 8 4 2 1

S(8): 8 4 2 1

S(9): 9 26 13 30 15 32 16 8 4 2 1

S(10): 10 5 24 12 6 3 22 11 30 15 34 17 36 18 9 28 14 7 26 13 32 16 8 4 2 1

Extending above claim

Define Sequence $S_t(a_0)$ where $$ a_{n+1} = \begin{cases} a_n/2, & \text{if $a_n$ is even} \\ a_n+2^ta_0-1, & \text{if $a_n$ is odd} \end{cases}$$

With $a_0$ and $t$ are given positive integers.

Note $S_1(a_0)=S(a_0)$

Example $S_2(9)=\{9, 44, 22, 11, 46, 23, 58, 29, 64, 32, 16, 8, 4, 2, 1\}$

2 Question : for every $a_0,t\in\mathbb{N}$, sequence $S_t(a_0)$ will eventually reach the number $1$?

Source python

n=1
while n<11:
    
    def collatz(n):
        k=n
        while (n > 1):
            print(n, end=' ')
            if (n % 2):
                # n is odd
                n = n + 2*k-1
            else:
                # n is even
                n = n//2
        print(1, end='')
     
     
    #n = int(input('Enter n: '))
    print('\n',n,'Sequence: ', end=' ')
    collatz(n)
    n=n+1
'''

Answer 1

Indeed, the sequence will reach $1$ eventually. Here is how you can see it. Let's look into a slightly modified sequence:

$$b_{n+1}=\begin{cases}b_n/2&b_n\text{ even}\\\frac{b_n-1}{2}+a_0&b_n\text{ odd}\end{cases}$$

$$b_0=1$$

This is the same sequence as the previous one, except that it is "shifted" by one place ($b_1=a_0$) and from the original sequence we drop the first (necessarily even) number following any odd number.

Example: $a_0=6$, $(a_n)_{n\in\mathbb N}=(6, 3, 14, 7, 18, 9, 20, 10, 5, 16, 8, 4, 2, 1,\ldots), (b_n)_{n\in\mathbb N}=(1, 6, 3, 7, 9, 10, 5, 8, 4, 2, 1,\ldots)$.

The sequence $(b_n)$ is easier to look at, for example it immediately follows that its members are all smaller than $2a_0$, in fact they are bound by $2a_0-2$ (induction on $n$):

• If $b_n$ is even, then $b_{n+1}=b_n/2\lt b_n\le 2a_0-2$
• If $b_n$ is odd, then $b_{n+1}=\frac{b_n-1}{2}+a_0\le \frac{2a_0-3}{2}+a_0=2a_0-3/2$, but as the LHS is an integer, it must further be $\le 2a_0-2$.

(By the way, this also means that $(a_n)$ will be bound by $4a_0-4$.)

Now, this means that the sequence $b_n$ will eventually start to repeat.

On the other hand, the sequence $b_n$ can be also "replayed backwards":

$$b_{n-1}=\begin{cases}2b_n,&b_n\lt a_0\\2(b_n-a_0)+1,&b_n\ge a_0\end{cases}$$

This is because, if the following item $b_n$ is $b_n\ge a_0$, it could've only been produced by the second rule (or otherwise, if produced by halving, we would have $b_{n-1}\ge 2a_0$). Also, if the following item $b_n$ is $b_n\lt a_0$, then it could've only been produced by halving, because the second rule produces only values $\ge a_0$.

From the two facts shown in italics above, we can conclude that one of $b_n$'s will eventually be $1$. Namely, the sequence will repeat eventually, and let $b_m=b_n$ be the first repetition (lexicographically), with $m<n$. If $m=0$, then $b_n=b_0=1$ - problem solved! If $m\ne 0$, then, because of the "replay backwards" rule we have $b_{m-1}=b_{n-1}$ - a contradiction with $b_m=b_n$ being the first repetition.