[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:
[![collatz tree](https://i.stack.imgur.com/KxdQc.png)](https://i.stack.imgur.com/KxdQc.png)
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](https://en.wikipedia.org/wiki/Collatz_conjecture) to \$1\$ for that integer. This is called a *Collatz graph*
[This](https://upload.wikimedia.org/wikipedia/commons/0/0e/Collatz-tree%2C_depth%3D20.svg) 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](https://oeis.org/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](https://tio.run/##VZBBboNADEXXcApvqoxT0pSgbCJxhV6AogoVoyKBZzQMjdrLU3ugUbJ9fvO/x@4nfFkulqWlDj7tMDTh98Pb62Q4g@CJoIQ3y4SXNOm7lfRTREKSzaiqvK6jwFCW8KojT2H2HF@kaSKR6onUWQ9sW4lZh9Uhr6Nvry@Nc8StOcE@KihYM9V@glOMhoZbMBEdIEfhxa3yPuNOOR6hwHRtpoFGbRbzsqb/k2keje6TyZZ4S/M02m8yKmnE9qnHQ2nLdqxnqITVojrfczD7B1NJz24OBhEzmMjJTXbvvMNlyc9/) is a sample program (ungolfed) that takes an integer and outputs each list on a line.
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so the shortest code in bytes wins.
  
[Answer]
# [K (ngn/k)](https://codeberg.org/ngn/k), ~~37~~ 35 bytes
```
{x#x(,/{(4=6!x*4<x)(-6!)\2*x}')\,1}
```
[Try it online!](https://ngn.bitbucket.io/k#eJxLs6quUK7Q0NGv1jCxNVOs0DKxqdDU0DVT1Iwx0qqoVdeM0TGs5eJKUzA0AAD90ArT)
### 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]
# [Jelly](https://github.com/DennisMitchell/jellylanguage), 23 bytes
```
·∏§·∏§,‚Äô√∑3∆ä∆ä·∏Ç?‚Ç¨F·∏û∆ë∆á>∆á1
1√á√ê¬°
```
[Try It Online!](https://jht.hyper-neutrino.xyz/tio#WyIiLCLhuKThuKQs4oCZw7czxorGiuG4gj/igqxG4biexpHGhz7GhzFcbjHDh8OQwqEiLCLDh8WS4bmY4oKsWSIsIiIsWyIxNSJdXQ==)
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]
# 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!](https://tio.run/##y0osSyxOLsosKNHNy09J/f8/zVYjTyfRNtowVtPWLk9X1z5RO4ErQTsNJKqXlpNY4ptYoFFha1ehaqZrUlNhY2pvpFVhFQ0kdOp0K/SNYzU1rdTV/yfn5xXn56Tq5eSna6RpGBppav4HAA "JavaScript (Node.js) ‚Äì Try It Online")
[Answer]
# [Python 2](https://docs.python.org/2/), ~~77~~ ~~75~~ 72 bytes
-5 bytes thanks to [Dude coinheringaahing](https://codegolf.stackexchange.com/users/66833/dude-coinheringaahing), [G B](https://codegolf.stackexchange.com/users/18535/g-b) and [xnor](https://codegolf.stackexchange.com/users/20260/xnor)!
```
r=1,
exec'print r;r=sum([[2*i]+[i/3][:i%6==4<i]for i in r],[]);'*input()
```
[Try it online!](https://tio.run/##BcE7CoAwDADQ3VNkkfopiB8c1JwkZBLFDLYltqCnr@@FL17eDTkr9rY43mM3QcVF0FXxSXdFNDTCLUk3Mi1SzojTJnx6BQFxoGyJ69U04kKKVZ1zP/0 "Python 2 ‚Äì 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!](https://tio.run/##HcpBEoIgGEDhvadg0wgoo1CrHE7CsDDEYjBkiMa/TVcnbfu9Fz/5sQZRipHL@LxNI4Ir4x1QBXpNyGAFnWjPFBjXCk5Ck2YvlZd9ZcGaOiYXsmKb8nre/w25gF5rynbCBkdyWDwsjeFuMROU@rYnbmZfL@Viw/8iRA@@kXyoqQvxnTEphV9@ "Python 2 ‚Äì Try It Online")
[Answer]
# [J](http://jsoftware.com/), 48 bytes
```
<6&(([:;<@(((],<.@%~)+:)#~1,(4<])*4=|)"0)&.>)<@1
```
[Try it online!](https://tio.run/##y/qvpKeepmBrpaCuoKNgoGAFxLp6Cs5BPm7/bczUNDSiraxtHDQ0NGJ1bPQcVOs0ta00lesMdTRMbGI1tUxsazSVDDTV9Ow0bRwM/2typSZn5CukKRga/AcA "J ‚Äì Try It Online")
Just a port of [Bubbler's nice K answer](https://codegolf.stackexchange.com/a/233511/15469) 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]
# [Perl 5](https://www.perl.org/), 60 bytes
```
$_=1;for$x(2.."@F"){s,\d+,2*$&.($&%6-4|$&<5?'':(1-$&)/3),ge}
```
[Try it online!](https://tio.run/##BcFLCsIwFAXQ@V1GeaaNJtGXn3905CoEEawiFBNaB4K6deM5ue27UAqdtry@pp5ejTWm2h8q@R7U8TJRdkzCNCRGUfsPiU3Y1fWqYU1CTp1Ut/ZbCsPCwSMgYo4FluAZmMEW7MAeHMDxl/Lznh5D0efc/QE "Perl 5 ‚Äì 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]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), 58 bytes
```
NestList[If[#~Mod~6==4<#,##&,#&][2#,--+#/3]&/@#&,{1},#-1]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b73y@1uMQns7gk2jMtWrnONz@lzszW1sRGWUdZWU1HWS022khZR1dXW1nfOFZN3wEoVm1Yq6Osaxir9j@gKDOvRN8hzcHI4D8A "Wolfram Language (Mathematica) ‚Äì Try It Online")
Returns a list of row-lists.
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~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!](https://tio.run/##KypNqvyfZvtf1y6vOjrRNtowNlZbw0hPL09TLzexoDrRNlEvLSexJB7Eqamoia7QMtKpUDWztTWxr9A3tjKM1QVqqa2t/V@gkBZtaBr7HwA "Ruby ‚Äì Try It Online")
[Answer]
# [Haskell](https://www.haskell.org/), ~~69~~ 57 bytes
```
(`take`iterate(>>=g)[1])
g n=2*n:[n`div`3|n`mod`6==4,n>4]
```
[Try it online!](https://tio.run/##BcExDoMwDADAnVd4YICqHaCoQyXnIxTJFiRpRDARREy8HXP35322MarDn1aUebYUst0428oY9HXfDHXhQbB9yLcXmsJB71NoWSf6IHZPMd2gCwcBhLQFyVCCg6bVa3SR/a6vMaUb "Haskell ‚Äì Try It Online")
* saved 12 bytes thanks to @DelfadOr !
* Based on [@ovs answer](https://codegolf.stackexchange.com/a/233542/98541)
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!](https://tio.run/##BcExDoMwDADAva/w0AEoIJEyVTUfCZGwUJJGTq0IMvbtNXcfOtnnrAFXbbZK7LdU/UHVN8uCsbWTa28RBE0nL8s/fg/W9PM4iuufHT9mRHH6pSSAUI4kFe4QYDL630OmeOqwl3IB "Haskell ‚Äì Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 38 bytes
```
‚äûœÖ¬πÔº¶ÔºÆ¬´Ôº©œÖ‚Üì‚âîœÖŒ∑‚âî‚ü¶‚üßœÖÔº¶Œ∑¬´‚äûœÖ‚äóŒ∫¬ø‚àß‚Ä∫Œ∫‚Å¥‚Åº‚Å¥Ôπ™Œ∫‚Å∂‚äûœÖ√∑Œ∫¬≥
```
[Try it online!](https://tio.run/##Tc2xCsIwEAbguX2KGy8QB7U46CRWxEHpLg5pG20wJprk6iA@e2wKgrf9d8f3N51wjRU6xop8h8Rhylb5xTrAvXlQONK9lg4Zg3eeVU6ZgBvhAxIb3rKD7SUuS/syKa29V1eTjO4vns4cKOUR7UYo@5WVlmotW7yNXKYugGvT4s5JEYbaG4eCcdg@SWiPBYeDbUnbtF@wYeDn7E0oVa9amU7zEfvknxinszjp9Rc "Charcoal ‚Äì 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]
## [Perl 5](https://www.perl.org/), 63 bytes
```
@n=1;map{say"@n";@n=map{$_*2,$_<5||$_%6-4?():($_-1)/3}@n}0..pop
```
[Try it online!](https://tio.run/##K0gtyjH9X1qcqlBmqmdoYP3fIc/W0Do3saC6OLFSySFPyRooAOKqxGsZ6ajE25jW1KjEq5rpmthraFppqMTrGmrqG9c65NUa6OkV5Bf8///f0BgA "Perl 5 ‚Äì Try It Online")
[Answer]
# [Julia 1.0](http://julialang.org/), 67 bytes
```
>(n,a=[1])=show(a),0<n-1>[(a.|>j->[2j;~-j√∑3][1:1+(j%6==4<j)])...;]
```
[Try it online!](https://tio.run/##yyrNyUw0rPj/304jTyfRNtowVtO2OCO/XCNRU8fAJk/X0C5aI1Gvxi5L1y7aKMu6Tjfr8Hbj2GhDK0NtjSxVM1tbE5sszVhNPT0961igGUYGmv8B "Julia 1.0 ‚Äì Try It Online")
based on [ovs's answer](https://codegolf.stackexchange.com/a/233542/98541)
output is in the form
```
[1][2][4][8][16][32, 5][64, 10][128, 21, 20, 3]...
```
]