What formula could generate this sequence related to the Collatz conjecture 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?
 A: 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.
