What formula could generate this sequence related to the Collatz conjecture

Question

The collatz conjecture states that every number eventually reaches $1$ under the repeated iteration of $$ f_0(n) = \begin{cases} n/2, & \text{if $n$ even} \\ 3n+1, & \text{else} \end{cases}$$ As a number is guaranteed to be even after the $3n+1$ step, one can replace $f_0(n)$ with $$ f_1(n) = \begin{cases} n/2, & \text{if $n$ even} \\ \frac{3n+1}{2}, & \text{else} \end{cases}$$ and obtain an equivalent conjecture. One can tabulate the possible expressions that can arise from applying $f_1$ to $n$ $x$ times, as is shown in the following table.

\begin{array}{|c|c|c|c|} \hline \frac{n}{2^1}& \frac{n}{2^2} & \frac{n}{2^3} & \frac{n}{2^4} \\ \hline \frac{3^1n+1}{2^1}& \frac{3^1n+1\cdot2^1}{2^2} & \frac{3^1n+1\cdot2^2}{2^3} & \frac{3^1n+1\cdot2^3}{2^4}\\ \hline & \frac{3^1n+1\cdot2^0}{2^2} & \frac{3^1n+1\cdot2^1}{2^3} &\frac{3^1n+1\cdot2^2}{2^4}\\ \hline & \frac{3^2n+5\cdot2^0}{2^2} & \frac{3^2n+5\cdot2^1}{2^3}& \frac{3^2n+5\cdot2^2}{2^4}\\ \hline & &\frac{3^1n+1\cdot2^0}{2^3} & \frac{3^1n+1\cdot2^1}{2^4} \end{array}

Let $x$ be the column index and the number of iterations, starting at $1$.
Let $y$ be the row index, starting at $0$.

The content of cell $x,y$ is $f_1$ applied to the content of cell $x-1,\lfloor\frac{y}{2}\rfloor$. The parity of $y$ decides which 'path' of $f_1$ (even or odd) is taken. Or formulated another way: the table is built up recursively. Column 1 row 0 was the input for column 2 rows 0 and 1. Column 1 row 1 was the input for column 2 rows 2 and 3 and so on. The resulting large fractions are then factored into this form.

I've pasted the html of a table for the first 8 iterations to this page.

When written this way, the expressions exhibit some nice pattern, namely: Every expression (apart from row 0) is of the form $$ \frac{3^bn+q\cdot2^d}{2^x} $$

where $b$ is the hamming weight of $y$, i.e. the number of 1-bits in it's binary representation and $d = x - \log_2 (c) + 1$ with $c$ being the greatest power of 2 $\leq y$.

$q$ is the only thing which seems not be as easily parameterisable. However, it seems to be somehow similar to A035109, which is defined as $$ \frac{1}{n}\sum_{d \mid n}{\mu\left(\frac{n}{d}\right)\sum_{e\mid d} e\sum_{\substack{e\mid d \\ e \text{ odd}}}e} $$

The first values of q are: $0,1,1,5,1,7,5,19,1,11,7,29,5,23,19,65,1,19,\dots$ More can be read out from the linked table. My question is: what formula could generate this sequence?

Answer 1

Update - solution
It seems, a valid pattern is been indicated by the following picture, where your values $q$ are ordered in a binary (or ternary?) tree:

(remark, your sequence $q$ occurs when reading the yellow marked numbers from the first row from left to right and row by row beginning at index $1$)

I've sometimes seen sequences which have such a "binary tree" pattern. If it is really appropriate for your problem, this knowledge might be helpful to detect a generating formula. If this pattern is indeed correct, then I have a simple function to determine the value of $q$ at any index:

\\ program in Pari/GP  
{getQ(idx)=local(b,a);   
      b=binary(idx); \\ b becomes vector with bits of value idx
      a=1;for(k=2,length(b), if(b[k]==1, a=3*a+2^(k-1))); 
      return(a); }      

checking:

 getQ(3)  \\ gives value 5
 getQ(5)  \\ gives value 7
 getQ(25) \\ gives value 31
 getQ(211) \\ 527
 getQ(255) \\ 6305

first 12 values:

 vector(12,r,getQ(r))
  \\ output:  [1, 1, 5, 1, 7, 5, 19, 1, 11, 7, 29, 5]

---

old text of answer
Unfortunately I didn't see how to implement computation of the squence of q's so I couldn't make it more likely that this binary pattern actually exists.

The numbers $1,5,19,65,211,...$ are likely best interpreted as differences of the type $3^n-2^n$ And many other numbers can be described as other difference of powers of 3 and 2, like

                                       9    11      49    7     37     29 
                                     27-8  27-16  81-32  9-2  64-27  32-3

Also, $1,7,29,103,341,...$ can be described as $1$, $7=3\cdot 1+4$, $29= 3\cdot 7+8$, $103 = 3 \cdot 29+16$, $341 = 3\cdot 103 + 32$, $...$ but I think it is too much for me at the moment to proceed here.

If we follow the right-down arrows (black and grey) then there is a so simple pattern that I'm sure this is the best way to define the tree (and from this the sequence)

---

I've just copied the first 256 numbers $q$ from the linked list in the OP. See:

0, 1, 1, 5, 1, 7, 5, 19, 1, 11, 7, 29, 5, 23, 19, 65, 1, 19, 11, 49, 7, 37, 
29, 103, 5, 31, 23, 85, 19, 73, 65, 211, 1, 35, 19, 89, 11, 65, 49, 179, 7, 53, 
37, 143, 29, 119, 103, 341, 5, 47, 31, 125, 23, 101, 85, 287, 19, 89, 73, 251, 65, 
227, 211, 665, 1, 67, 35, 169, 19, 121, 89, 331, 11, 97, 65, 259, 49, 211, 179, 
601, 7, 85, 53, 223, 37, 175, 143, 493, 29, 151, 119, 421, 103, 373, 341, 1087, 5, 
79, 47, 205, 31, 157, 125, 439, 23, 133, 101, 367, 85, 319, 287, 925, 19, 121, 89, 
331, 73, 283, 251, 817, 65, 259, 227, 745, 211, 697, 665, 2059, 1, 131, 67, 329,
 35, 233, 169, 635, 19, 185, 121, 491, 89, 395, 331, 1121, 11, 161, 97, 419, 65, 
323, 259, 905, 49, 275, 211, 761, 179, 665, 601, 1931, 7, 149, 85, 383, 53, 287, 
223, 797, 37, 239, 175, 653, 143, 557, 493, 1607, 29, 215, 151, 581, 119, 485, 
421, 1391, 103, 437, 373, 1247, 341, 1151, 1087, 3389, 5, 143, 79, 365, 47, 269, 
205, 743, 31, 221, 157, 599, 125, 503, 439, 1445, 23, 197, 133, 527, 101, 431, 
367, 1229, 85, 383, 319, 1085, 287, 989, 925, 2903, 19, 185, 121, 491, 89, 395, 
331, 1121, 73, 347, 283, 977, 251, 881, 817, 2579, 65, 323, 259, 905, 227, 809, 
745, 2363, 211, 761, 697, 2219, 665, 2123, 2059, 6305, ...

It seems a representation as numbers $6k \pm 1$ or $6k+1$,$6k+5$ could be helpful.

Answer 2

This is not an exact answer to your question, but an simple observation.

Looks like a fractal or reccurence sequence, similar to fibonacci, or one think it might have recurrent relationships. Most likely this is a sequence which can not be shortcut, i.e. one might have to compute every step along the way to get the numbers in the sequence (this is a guess though).

$$0,0,1,1,5,1,7,5,19,1,11,7,29,5,23,19,65,1,19,…$$

I've highlighted it's fractal behavior by the numbers in red color:

$$0,\color{red}0,1,\color{red}1,5,\color{red}1,7,\color{red}5,19,\color{red}1,11,\color{red}7,29,\color{red}5,23,\color{red}{19},65,\color{red}1,19,…$$

$$\color{red}0,\color{red}0,\color{red}1,\color{red}1,\color{red}5,\color{red}1,\color{red}7,\color{red}5,\color{red}{19},\color{red}1,11,7,29,5,23,19,65,1,19,…$$

Now if we take the other sequence (it's quite different!), iv'e highlighted that in blue):

$$\color{blue}0,0,\color{blue}1,1,\color{blue}5,1,\color{blue}7,5,\color{blue}{19},1,\color{blue}{11},7,\color{blue}{29},5,\color{blue}{23},19,\color{blue}{65},1,\color{blue}{19},…$$

$$\color{blue}0,\color{blue}1,\color{blue}5,\color{blue}7,\color{blue}{19},\color{blue}{11},\color{blue}{29},\color{blue}{23},\color{blue}{65},\color{blue}{19},…$$

The sequence in blue which is part of your sequence is not in the OEIS. The question for the red sequence is wether one can take every fourth, eight, and so on to state that it is fractal. In your sequence one could try other simple techniques to find out if there are self recurring similarities.

As a sidenote: the ruler sequence has the same fractal behaviour, which is also related to the largest power of $p$ that divides $2^n$ in the Reduced Collatz Function that is applied only to the odd integers.