25
\$\begingroup\$

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

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.

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

12 Answers 12

14
\$\begingroup\$

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...
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
\$\endgroup\$
5
  • 1
    \$\begingroup\$ What are the advantages of using ngn/k vs oK vs shakti? \$\endgroup\$
    – Jonah
    Aug 18 at 3:29
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Bubbler
    Aug 18 at 3:46
  • \$\begingroup\$ Also how does your code deal with the "and not already part of the tree" constraint? \$\endgroup\$
    – Jonah
    Aug 18 at 4:22
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Aug 18 at 4:27
  • \$\begingroup\$ direct BQN translation(42): {(∾´{⌊6÷˜⍟(↕1+4=6|𝕩×4<𝕩)2×𝕩}¨)⍟(↕𝕩)⥊1} \$\endgroup\$
    – Razetime
    Aug 18 at 7:11
6
\$\begingroup\$

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.

\$\endgroup\$
2
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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!

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

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.

\$\endgroup\$
3
\$\begingroup\$

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
}
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
2
\$\begingroup\$

Charcoal, 38 bytes

⊞υ¹FN«Iυ↓≔υη≔⟦⟧υFη«⊞υ⊗κ¿∧›κ⁴⁼⁴﹪κ⁶⊞υ÷κ³

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

⊞υ¹

Start with the first row of just 1.

FN«

Loop over the desired number of rows.

Iυ

Output each element on its own line.

Leave a blank line between rows.

≔υη

Save the current row.

≔⟦⟧υ

Start a new row.

Fη«

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.

\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

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

Try it online!

Returns a list of row-lists.

\$\endgroup\$
1
  • \$\begingroup\$ --+#/3 is neat. \$\endgroup\$
    – Roman
    Aug 20 at 8:29
2
\$\begingroup\$

Perl 5, 63 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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]...
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.