What formula could generate this sequence related to the Collatz conjecture

collatz conjecturesequences-and-series

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?

Best Answer

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:

picture
(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.

Related Question