# 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?

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]


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.

• Could you elaborate please what you mean? – SmallestUncomputableNumber May 4 '19 at 10:38
• @SmallestUncomputableNumber - I've sometimes seen sequences which have such a "binary tree" pattern. If it is really existent, this knowledge might be helpful to detext a generating formula. 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. --- If this all is trivial to you, sorry, please feel free to say so and I can delete my idea without fuzz. – Gottfried Helms May 4 '19 at 11:48
• Not trivial at all, I just didn't understand how you meant your comment but now I think I do. I can't say anything on the existence of such a structure, however I wouldnt be too surprised if the sequence would exhibit such a property. The only thing I noticed is: Given some y and its corresponding q, then y*2^k corresponds to the same q for every k. For the calculation of q, the even prime divisors of y (2) seem to be irrelevant. – SmallestUncomputableNumber May 4 '19 at 12:37
• Yes, in your $256$ number-list, the spacing between each number $1,5,19,65,211,665,2059,..$ of $3^n-2^n$ is exactly $2^x$ or $1,2,4,8,16,32...$ in the OP's sequence. If I call OP's sequence $g(n)$ then you could lookup your numbers by $g(2^x)$. – Natural Number Guy May 4 '19 at 20:10
• @NaturalNumberGuy - hi, seems I got it completely... See the updated answer... :) – Gottfried Helms May 5 '19 at 6:30

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.

• I've taken the first 256 values from the OP's link. Perhaps you can use them to extend your coloured partial sequences for more explanative power. – Gottfried Helms May 4 '19 at 15:57