General form for the k-th next odd number the Collatz conjecture

Question

Let's consider only the odd positive integers in the Collatz conjecture. If the conjecture is true, they'd form a directed graph pointing to 1, which points to itself.

The next odd number in the graph, the "parent", is written: $$P(n)=\frac{3n+1}{2^a}:a\in\mathbb{N^*}\tag3$$

EDIT: If you had a generalized formula for the $k$th parent of $n$, $P^k(n)$, would it be sufficient to prove there are no cycles in the Collatz conjecture if you could show that there are no positive integer solutions for $P^k(n_0)=n_0$ for all $k$?

I think a general form can be written for the real solutions of $P^k(n_0)=n_0$, the $k$-th parent of $n$: $$P^k(n_0) = \cfrac{1+3\cdot\cfrac{1+3\cdot\cfrac{1+3(\dotsb)\textbf{}}{2^{a_{k-2}}}}{2^{a_{k-1}}}}{2^{a_k}}\tag6$$ If there are cycles in the Collatz, then there must be some $n_0$ such that $P^k(n_0)=n_0$. The real solutions to the parent equation take the form: $$A_k \equiv \sum_{i=1}^{k}a_i\tag7$$ $$B_k \equiv \sum_{i=1}^{k} 3^{i-1}\cdot2^{A_{k-i}}\tag8$$ $$n_0 = P^k(n_0) = \frac{B_k}{2^{A_k}-3^k}\tag9$$ We can utilize the condition that $\{n_0, k, a_i\}$ must be positive integers to get some important information about this function. First, the numerator is positive by definition, so for $n_0$ to be positive, it must be the case that $2^{A_k}>3^k$. We know that $A_k \geq k$ since each parent is the result of at least one divide by two operation, so we can rewrite $A_k$ in terms of $k$ and some leftover term $m$: $$A_k=k+m\tag{10}$$ This yields the inequality relating $m$ to $k$: $$\frac{2^{k+m}}{3^k} > 1\tag{11}$$ $$m>k\cdot log_2\left(\frac{3}{2}\right)\tag{12}$$

If there are no positive integer solutions for $m$ given a $k$, $P^k(n_0)\neq n_0$.

Would this be a valid approach to proving there are no cycles in the Collatz conjecture?

Answer 1

You have reproduced a result from the paper of Bohm and Sontachi 1978: http://www.bdim.eu/item?id=RLINA_1978_8_64_3_260_0&fmt=pdf. If one explores the more general $mx+c$ where $m,c$ are odd integers (the original Collatz conjecture has $m=3$ and $c=1$) you get the loop condition: $n_0 = \dfrac{cB_k}{2^{A_k}-m^k}$ where the $3$ in the definition of $B_k$ is replaced with $m$. A loop occurs if and only if the numerator is divisible by the denominator. With $c\ne1$ there are more possibilities for this condition to be met. There are many loops in the $mx+c$ zoo, in fact for every $m$ there are an infinite number of loops of every length across all $c$. Choose any $k$ and then any $A_k$ with $2^{A_k} > m^k$ and set $c=2^{A_k}-m^k$ then every legal set of $a_i$ which results in a $B_k$ meets the loop condition. There are also many other loops which don't use this trick. The loop condition applies to every $n_i$ in the loop where the $B_k$ are given by the cyclic rotation of the $a_i$. You are just choosing a different $n_i$ to play the role of $n_0$.

Anyway, the answer to your question is yes, if the loop condition has no integer solution for some k there is no loop of length k. One needs to be careful to distinguish between loops and cycles where a loop is a repeating sequence and a cycle is a loop where all the members of the sequence are unique, which is equivalent to saying all the cyclic rotations of $a_i$ are unique. A loop is one or more instances of a cycle. The above condition is a loop condition, not necessarily a cycle condition. For example, for $3x+1$ there is a solution to the loop condition for every $k$ which is simply the sequence $1,1,1,1,...$ with $k$ $1$'s. Any repeated solution to the loop condition is also a solution. You have to add another condition to your results to limit them to cycles.

Answer 2

If you look at the binary representation of an odd number starting from the least significant bit you can find only three cases:

a) $ \quad \cdots$ 011, $ \quad \cdots$ 0111, $ \quad \cdots$ 01111, $ \quad \dots \quad $

b) $ \quad \cdots$ 1101, $ \quad \cdots$ 110101 , $ \quad \cdots$ 11010101, $ \quad \dots \quad $

c) $ \quad \cdots$ 001, $ \quad \cdots$ 00101, $ \quad \cdots$ 0010101 , $ \quad \dots$

with which it is possible to determine the value of $ \quad n \pmod {2^{c+1}}$

a) $ \quad 3 ,\quad 7 ,\quad 15 , \quad \dots , \quad 2^c-1 \quad \text{ with } \quad c>1$

b) $ \quad 13 , \quad 53 , \quad 213 , \quad \dots , \quad (5 \cdot 2^c-1)/3 \quad \text{ with } \quad c=2 \cdot b +1 \quad,\quad b>0$

c) $ \quad 1 ,\quad 5 , \quad 21 , \quad \dots , \quad ( 2^c-1)/3 \quad \text{ with } \quad c=2 \cdot b \quad,\quad b>0$

From this you can derive a cyclic graph based on the value of $ \quad n \pmod {2^{c+1}}\quad $ which can help you better visualize the sequence of odd numbers.

edit: I had forgotten, in answer to question Q1, as can be seen from the formulas, only numbers $\pm 1 \pmod 3$ are obtained.

Note: in case a) a further simplification has been made using a property of the Syracuse_function: $f^{p-1}(2^p \cdot h-1)=2 \cdot 3^{p-1}\cdot h -1.$