# On a proof that "there are at least $F_n$ Collatz permutations of length $n$".

Let $n, k \in \Bbb{N}$ and $F_n$ be the $n$th term of the Fibonacci sequence.

Let $u$ be the map $x \to 3x+1$ and $d$ be the map $x \to \frac{x}{2}$.

Let a type be a sequence of $u$'s and $d$'s. Recall that a type must end with a mapping $d$ and that there cannot be two mappings $u$ consecutively.

Let $A = 2^a$ for some $a \in \Bbb{N}$ ($a$ is necessarily even).

Let a witness be of the form $U(A)$, where $U$ is the inverse of $u$.

Consider the following proposition:

If a type $σ$ contains $k$ $u$’s then there is a single congruence of the form $A = c \mod 3^k+1$ which must be satisﬁed in order that a trace of type $σ$ ends with witness $A$. Consequently, there is a least witness $A = 2^a$ with $a ≤ 2·3^k$, and a general witness is of the form $2^{a+jd}$ where $j$ is a nonnegative integer and $d = 2·3^k$.

This is a proposition from a paper on Collatz permutations. I am actually quite confused on how this proves that the proposition shows [...] that there are at least $F_n$ Collatz permutations of length $n$.

More straightforwardly, the following question on MSE seems to answer the question (for strings of length $\leq 14$) using induction of Fibonacci sequences.

• Link to the paper at arXiv is broken. Commented Dec 23, 2014 at 22:42
• @FredKline fixed Commented Dec 23, 2014 at 22:43
• Would you mind to explain how in the article the permutation $(5,3,1,4,2)$ is actually determined from the trajectory beginning at $12$ and is completely $12,6,3,10,5,16,8,4,2,1,4,2,1,...$ - I've no idea how this is made.... Commented Dec 25, 2014 at 9:34
• @GottfriedHelms The paper trims off the final descending part so it first becomes 12,6,3,10,5. Then the numbers in this list are ranked, so that 3 is rank 1, then 5 is rank 2, 6 is rank 3, 10 is rank 4, and finally 12 is rank 5. So in terms of ranks, the trimmed part of the trajectory is (5,3,1,4,2). Commented Dec 25, 2014 at 11:35
• @coffemath : ahh- Thank you very much! Commented Dec 25, 2014 at 12:07

The Collatz permutations of length $n$ are as in the linked paper the permutations of the numbers in the initial part, before the final descent upon reaching a power of $2,$ where the numbers occurring in this initial part have been ranked from $1$ to $n$ according to magnitude. The patterns of $u,d$ (up,down) are what give rise to Fibonacci numbers, and such patterns of length $n$ have to end with a $d$ and have no two adjacent $u$'s. That there are $F_n$ of these patterns can be shown by defining $G_n$ as the number of them, and looking at the last two terms, which must be $dd$ or $ud.$ In the first case, the last $d$ may be dropped and the contribution is $G_{n-1},$ while those ending $ud$ must have the term right before that as a $d$ (to avoid adjacent $u$) and so contribute $G_{n-2}.$ Thus $G_n=G_{n-1}+G_{n-2},$ and some base cases then show $G_n=F_n.$
Now the arguments in the paper are to show that each allowable pattern sequence of length $n$ actually occurs in the Collatz sequence, and it seems the paper shows any such sequence appears infinitely often.
The point about there then being "at least $F_n$ Collatz permutations of length $n$" is then a consequence of the fact that several Collatz permutations may correspond to a single pattern, but obviously different patterns have distinct Collatz permutations lying above them.
For example the two Collatz sequences $(5,3,4,2,1,7,6)$ and $(5,3,6,4,2,7,1)$ each correspond to the up down pattern $d,u,d,d,u,d.$