Rows of the Collatz tree

Consider a binary tree built the following way:

• The root node is $$\1\$$
• For a given node $$\n\$$:
• If $$\n\$$ is odd, its only child is $$\2n\$$
• If $$\n\$$ is even, one of its children is $$\2n\$$. If $$\\frac {n-1} 3\$$ is an integer and not already part of the tree, its right child is $$\\frac {n-1} 3\$$
• Recursively and infinitely define the tree this way, beginning from the root node.

The resulting tree begins like this:

and continues forever, conjectured to contain all positive integers. If you choose any integer on this tree and work your way up through its parents, you'll find the Collatz path to $$\1\$$ for that integer. This is called a Collatz graph

This is that tree to a depth of 20.

We can read this tree as rows, from left to right, to create a list of lists:

[[1], [2], [4], [8], [16], [32, 5], [64, 10], [128, 21, 20, 3], [256, 42, 40, 6], [512, 85, 84, 80, 13, 12], [1024, 170, 168, 160, 26, 24], [2048, 341, 340, 336, 320, 53, 52, 48], ...


Flattened, this is A088976.

Your program should take a positive integer $$\n\$$ and output the first $$\n\$$ rows of this tree. You may output in any format that clearly and consistently shows a separation between each element in the row, and a distinct separation between the rows themselves. For example, spaces for the elements, and newlines for the rows.

This is a sample program (ungolfed) that takes an integer and outputs each list on a line.

This is , so the shortest code in bytes wins.

• does each row need to be in this particular order? Aug 18 at 0:34
• @hyper-neutrino Yes, the order should be the same as shown - descending down the tree, with each row being left to right Aug 18 at 0:35
• @Arnauld Right, forget to mention that the tree doesn't contain duplicate nodes, so $1$ cannot appear twice (and is already the root node) Aug 18 at 0:49
• May we output only the $n$th row?
– att
Aug 18 at 5:54
• @att No, the output should be the first $n$ Aug 18 at 6:57

K (ngn/k), 37 35 bytes

{x#x(,/{(4=6!x*4<x)(-6!)\2*x}')\,1}


Try it online!

How it works

"n is even and (n-1)/3 is an integer" is equivalent to "n is 4 mod 6".

Avoiding the cycles is achieved by simply not allowing 4 to generate 1:

Claim: A cycle cannot be formed midway into the tree. Any cycle in the tree must include the root, i.e. the number 1.

Proof: Let's assume a node $$\a_0\$$ has a child $$\a_1\$$, which has a child $$\a_2\$$, ..., which has a child $$\a_n\$$, which in turn has a child $$\a_0\$$. Also, let's call the Collatz $$\3n+1\$$ function $$\f(x)\$$. Then the following holds:

$$f(a_1) = a_0, f(a_2) = a_1, \cdots, f(a_n) = a_{n-1}, f(a_0) = a_n$$

If $$\a_0\$$ has a parent (let's call it $$\a_{-1}\$$), then $$\f(a_0) = a_{-1}\$$, which implies $$\a_{-1} = a_n\$$, and therefore $$\a_{-1}, a_0, \cdots, a_{n-1}\$$ is also a cycle (which is one level closer to the root of the tree than $$\a_0, \cdots, a_n\$$). The same logic can be applied to $$\a_{-1}\$$, $$\a_{-2}\$$, ..., until the highest node reaches the root. Therefore, every cycle that exists in this tree goes through the root, i.e. the number 1. $$\\blacksquare\$$

The only cycle that involves the number 1 is the [1, 2, 4] cycle. Therefore, it suffices to prevent this cycle (i.e. stop 4 from generating 1) to prevent all cycles in the tree.

{x#x( ... )\,1}    start with [1], iterate x times and collect values,
and take first x values...
,/{ ... }'           apply to each number and flatten...
(-6!)\                 and append its floor division by 6 if
(4=6!x*4<x)            the original input is 4 mod 6 and it is over 4

• What are the advantages of using ngn/k vs oK vs shakti? Aug 18 at 3:29
• @Jonah The obvious advantage is CGCC post support in the online interpreter. Other than that, ngn/k has (IMO) lower chance of encountering "weird" bugs compared to oK, and Shakti is not free and its built-ins are still changing. Aug 18 at 3:46
• Also how does your code deal with the "and not already part of the tree" constraint? Aug 18 at 4:22
• By not allowing 4 to go back to 1... but now I realize it assumes the Collatz conjecture is true. I guess I should find a different solution that doesn't depend on it. Edit: Wait no, I think it actually works without assuming it. I'll add an explanation on it. Aug 18 at 4:27
• direct BQN translation(42): {(∾´{⌊6÷˜⍟(↕1+4=6|𝕩×4<𝕩)2×𝕩}¨)⍟(↕𝕩)⥊1} Aug 18 at 7:11

Jelly, 23 bytes

ḤḤ,’÷3ƊƊḂ?€FḞƑƇ>Ƈ1
1ÇÐ¡


Try It Online!

I doubt this is optimal; I kind of ended up patching together like three fixes in a row on my original idea. Might retry later if I have time and remember.

• -1 byte Aug 20 at 9:53
• ...and three more Aug 20 at 12:14

JavaScript (ES10), 70 bytes

f=(n,a=[1])=>n--?a+
+f(n,a.flatMap(x=>x%6-4|x<5?2*x:[2*x,~-x/3])):''


Try it online!

Python 2, 7775 72 bytes

-5 bytes thanks to Dude coinheringaahing, G B and xnor!

r=1,
exec'print r;r=sum([[2*i]+[i/3][:i%6==4<i]for i in r],[]);'*input()


Try it online!

Assuming the Collatz conjecture holds, we can generate the tree by sorting Collatz paths. This is a lot longer, but maybe a bit more interesting:

c=lambda x:-1/x*[x]or c([x/2,3*x-1][x%2])+[x]
k=0
exec'print[-w[k]for w in sorted(c(p)for p in range(-2**k,0)if-~k==len(c(p)))];k+=1;'*input()


Try it online!

• 75 bytes Aug 18 at 13:43
• Cut 2 bytes: the integer division (x+1)/3 is the same as x/3
– G B
Aug 19 at 14:55
• 70 bytes
– xnor
Aug 20 at 11:40
• @xnor I included the 1, but the other suggestion changes the order of nodes in the tree, which is not allowed
– ovs
Aug 23 at 8:58

J, 48 bytes

<6&(([:;<@(((],<.@%~)+:)#~1,(4<])*4=|)"0)&.>)<@1


Try it online!

Just a port of Bubbler's nice K answer into J, to see how they'd compare.

The required boxing to handle ragged arrays, as well as some other details, made it harder to golf in J.

Perl 5, 60 bytes

$_=1;for$x(2.."@F"){s,\d+,2*$&.($&%6-4|$&<5?'':(1-$&)/3),ge}


Try it online!

For each input line:

$_=1; # init output string$_ with '1'
for$x(2.."@F"){ # do input-1 times, input number is in "@F" due to -a s,\d+, # search-replace all positive ints in$_ with:
2*$& # 2 * the current int now in$&
.              # and possibly also another number
(
$&%6-4|$&<5  # ...if $& % 6 == 4 and$& > 4
? ''
: (1-$&)/3 # negative x where x = ($&-1)/3 using '-' as separator
)
,ge              # g=global, e=replacement from code not string
}


Wolfram Language (Mathematica), 58 bytes

NestList[If[#~Mod~6==4<#,##&,#&][2#,--+#/3]&/@#&,{1},#-1]&


Try it online!

Returns a list of row-lists.

• --+#/3 is neat. Aug 20 at 8:29

Ruby, 66 64 bytes

->n{[a=[1]]+(2..n).map{a=a.flat_map{|x|[x*2,x%6==4?x/3:1]-[1]}}}


Try it online!

(takeiterate(>>=g)[1])
g n=2*n:[ndiv3|nmod6==4,n>4]


Try it online!

• saved 12 bytes thanks to @DelfadOr !

57 bytes alternative provided by @xnor

(takeiterate(>>=g)[1])
g n=2*n:[k|k<-[2,4..n],3*k+4==n]


Try it online!

Charcoal, 38 bytes

⊞υ¹ＦＮ«Ｉυ↓≔υη≔⟦⟧υＦη«⊞υ⊗κ¿∧›κ⁴⁼⁴﹪κ⁶⊞υ÷κ³


Try it online! Link is to verbose version of code. Explanation:

⊞υ¹


Start with the first row of just 1.

ＦＮ«


Loop over the desired number of rows.

Ｉυ


Output each element on its own line.

↓


Leave a blank line between rows.

≔υη


Save the current row.

≔⟦⟧υ


Start a new row.

Ｆη«


Loop over the saved row.

⊞υ⊗κ


¿∧›κ⁴⁼⁴﹪κ⁶


If the current element is greater than 4 but equal to 4 modulo 6, then...

⊞υ÷κ³


... add the current element, integer divided by 3.

Perl 5, 63 bytes

@n=1;map{say"@n";@n=map{$_*2,$_<5||$_%6-4?():($_-1)/3}@n}0..pop


Try it online!

Julia 1.0, 67 bytes

>(n,a=[1])=show(a),0<n-1>[(a.|>j->[2j;~-j÷3][1:1+(j%6==4<j)])...;]


Try it online!

[1][2][4][8][16][32, 5][64, 10][128, 21, 20, 3]...