Rows of the Collatz tree

Question

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 code-golf, so the shortest code in bytes wins.

Answer 1

K (ngn/k), ³⁷ 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...
2*x                    start with twice the input,
(-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

Answer 2

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.

Answer 3

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!

Answer 4

Python 2, 77 75 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!

Answer 5

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.

Answer 6

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
}

Answer 7

Wolfram Language (Mathematica), 58 bytes

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

Try it online!

Returns a list of row-lists.

Answer 8

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!

Answer 9

Haskell, 69 57 bytes

(`take`iterate(>>=g)[1])
g n=2*n:[n`div`3|n`mod`6==4,n>4]

Try it online!

• saved 12 bytes thanks to @DelfadOr !

• Based on @ovs answer

57 bytes alternative provided by @xnor

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

Try it online!

Answer 10

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.

⊞υ⊗κ

Add the current element, doubled.

¿∧›κ⁴⁼⁴﹪κ⁶

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

⊞υ÷κ³

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

Answer 11

Perl 5, 63 bytes

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

Try it online!

Answer 12

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!

based on ovs's answer

output is in the form

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