# Collatz, Sort, Repeat

## Background

The Collatz (or 3x+1) map (A006370) is defined as the following:

$$a(n) = \begin{cases} n/2, & \text{if n is even} \\ 3n+1, & \text{if n is odd} \end{cases}$$

Now, let's define the sequence $$\s_0\$$ as the infinite sequence of positive integers $$\1, 2, 3, 4, \cdots\$$, and define $$\s_k\$$ as the result of applying the process $$\k\$$ times to $$\s_0\$$:

1. Apply Collatz map to each term of the input sequence.
2. Sort all the terms to get a non-decreasing sequence.

Here are first few terms of $$\s_0, \cdots, s_3\$$:

s0: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...
s1: 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 10, 11, 12, 13, 14, 15, 16, 16, 17, ...
s2: 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 8, 8, 9, 10, 10, 11, 11, 12, 13, 14, 14, ...
s3: 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 6, 7, 7, 8, 8, 9, 10, 10, 10, 11, 11, 12, ...


## Challenge

Given $$\k\$$ as input, output the sequence $$\s_k\$$.

Default I/O methods are allowed. For this challenge, this means you can use one of the following:

• Take $$\k\$$ as input, and output the terms of $$\s_k\$$ forever.
• Take $$\k, n\$$ as input, and output the value of $$\s_k(n)\$$ (0- or 1-indexed).
• Take $$\k, n\$$ as input, and output the first $$\n\$$ values of $$\s_k\$$.

You can also use 0- or 1-indexing for $$\k\$$.

Standard rules apply. The shortest code in bytes wins.

• Missed a trick here, should've been "Collatz-collate-repeat"... – Darrel Hoffman May 3 at 17:31
• It feels like $s_\infty$ should be an infinite sequence of $1$s. I doubt this will be too hard to prove /s – hakr14 May 3 at 19:48
• ...actually, since repeated Collatz mappings are guaranteed to converge to 1 for powers of 2, and there are infinitely many powers of 2... you can't exactly have a non-1 after an infinite amount of 1s. – hakr14 May 3 at 19:51
• @hakr14 No, (assuming Collatz conjecture is true) every number will eventually be cycling through 1, 4, 2. I guess they will have roughly equal counts. Though it doesn't change the conclusion that the count of ones diverges to infinity, so it'll at least look like infinitely many ones at the end. – Bubbler May 4 at 0:36
• @Bubbler oh, that's right. I remember the Collatz conjecture as all numbers eventually reach 1, and for some reason I just completely forgot that 1 isn't a fixed point of period 1. As a side note, our observations are a decent way of convincing yourself that order absolutely matters when dealing with infinite quantities (hardly rigorous, but hey) – hakr14 May 4 at 0:40

# Haskell, 73 bytes

([1..]>>=).(#)
k#n|k<1=[n]|s<-k-1=n<$s#(2*n)++[n|_<-s#div n 3,mod n 6==4]  Try it online! k#n returns a list of the appropriate number of copies of n. The anonymous function ([1..]>>=).(#) concatenates all of those together. # Python 2, 81 bytes f=lambda k,n:k and sorted([x/2,x*3+1][x%2]for x in f(k-1,n*2))[:n]or range(1,n+1)  Try it online! -19 bytes thanks to Leo and Bubbler -11 bytes thanks to dingledooper (-6 + -5 from Python 2) -8 bytes by swapping over to the brute force solution -2 bytes thanks to Noodle9 To get $$\s_k\$$ up to $$\n\$$ elements, we only need to get $$\s_{k-1}\$$ up to $$\2n\$$ elements. • Do you really need to check that n is a positive integer? It looks like things work the same if you just set c(n,0) to 1 for any n – Leo May 3 at 1:03 • Personally I don't feel like it's very adequate to print a sequence as a nested structure (list of lists in this case). Something like [*map(print,[i]*c(i,k))] should fix that. Meanwhile, c can be golfed a lot like this. – Bubbler May 3 at 1:07 • @Bubbler Fair enough. Fixed, and also golfed a bit more by combining with Leo. Thanks. – hyper-neutrino May 3 at 1:08 • Nice answer! Switching to Python 2 is shorter here; I can get you down to 91 bytes. – dingledooper May 3 at 3:18 • 81 bytes – Noodle9 May 3 at 13:08 # Husk, 272523 20 bytes !¡ȯΞzme½o→*3Mfe¦2%2N  Try it online! The idea for this comes from a message by rak1507 in the Husk chat. Returns the full sequence corresponding to the given 1-based k. ### Explanation We start from the list of natural numbers and then at each step produce one list with each even number halved and another list with each odd number multiplied by 3 and incremented, then we merge the two lists keeping them sorted. !¡(Ξzme½(→*3)Mfe¦2%2)N N Start from the infinite list of natural numbers ¡ Then iterate the following function Mfe Build two lists by applying the following two filters ¦2 Numbers divisible by 2 %2 Numbers not divisible by 2 zme Apply the following two functions respectively to the first and second list ½ Halve →*3 Multiply by 3, then increase Ξ Merge the two resulting lists ! Finally, return the result of the kth iteration  # Previous answer, 25 bytes ṘN!¡§z+oĊ2tȯ↓2ṁ:R5 0Ċ2∞1  Try it online! A bit clunky, but here's what I have for now. Returns the full sequence corresponding to the given 1-based k. -2 bytes thanks to Razetime. ### Explanation Rather than building the sequence directly, we build a list containing at each position n the number of occurrences of n in the sequence, then we convert it to the final sequence. ṘN!¡§z+oĊ2tȯ↓2ṁ:R5 0Ċ2∞1 ∞1 Start from an infinite list of ones (in s0 each number appears once) ¡ Iterate the following function §z+ Sum together oĊ2t The even-positioned values ȯ Ċ2 with the odd-positioned values ṁ:R5 0 with 5 zeros added before each one ↓2 and the initial 2 zeros dropped ! Get the kth iteration ṘN Repeat each natural number as many times as indicated  The trick here is that at each step we build two infinite lists and sum them together: the first one is the even-position values, which will each move to position n/2 simply because we remove the odd positions from the list; the second one starts from the odd positions (n->(n+1)/2), inserts 5 zeros before each value ((n+1)/2->3n+3), and removes the first two zeros (3n+3->3n+1). • ΣzR -> Ṙ .... – Razetime May 3 at 2:46 • @Razetime Thanks! I kept thinking that that part should be shorter but somehow forgot Ṙ existed – Leo May 3 at 3:41 • Given Husk's infinite lists, I'm surprised this isn't just "map collatz over the natural, sort" $k$ times. Would that approach be any simpler? – caird coinheringaahing May 3 at 12:09 • @cairdcoinheringaahing the problem with that approach is: how can you sort an infinite list? – Leo May 3 at 12:12 # Jelly, 16 or 17 bytes ×3‘ H æ«ḂĿ€⁴¡Ṣḣ³  Try it online! Takes n and k as arguments in that order, and outputs the first n elements of sk. The 16-byte version above does not work for k = 0; if this invalidates the solution, you can add an R after æ« for a 17-byte solution. ## Algorithm As is so often the case, producing terse code here was a matter of translating the problem directly using a brute-force algorithm rather than looking for a nice mathematical way to solve the problem. We simply start with a sufficiently long list, then Collatz and sort it the required number of times, and output the first m elements. (As an optimization, which saves runtime but more importantly a byte, we can in fact Collatz it the required number of times but sort it only once, because sorting+mapping+sorting a list is equivalent to just mapping+sorting it.) The number of terms we start with is n×2k; this guarantees that all terms which are numerically at least n will be correct in the output (any term that started higher than this couldn't be reduced to n in only k iterations), and therefore the first n elements will necessarily be correct in the output (because no sk can grow faster than the integers do, thus sk(n) ≤ n). ## Explanation Function 1Ŀ: ×3‘ ×3 Multiply by 3 ‘ Increment Function 2Ŀ: H H Halve Main program: æ«ḂĿ€⁴¡Ṣḣ³ æ« Calculate {n} times 2 to the power of {k} ¡ Loop times: ⁴ k € On each {of the previous iteration's results, if any or the numbers from 1 to the input, if not} Ŀ Call the function whose index is Ḃ determined by whether {that number} is odd or even Ṣ Sort {the resulting list} ḣ Take the first elements ³ n  I'm actually not sure why ḂĿ (which should call 1Ŀ on odd numbers but a nonexistent "0Ŀ" on even numbers) decides to call 2Ŀ on even numbers, but it's convenient here. (I assume it's some special case in Jelly that recognises that it doesn't make sense to do a recursive call here, but I'm not sure what triggers it; the special case isn't mentioned in the documentation for Ŀ, but the quicks aren't fully documented anyway.) One interesting thing about this code is that it's a self-polyglot; the € does something different on the first loop iteration than it does on the other loop iterations (and the code wouldn't typecheck in a typical statically typed language as a consequence). I frequently do this sort of thing in horrifyingly low-level esolangs that are a nightmare to program in, but this is the first time I remember doing it in Jelly. As a consequence, the code doesn't work for k = 0 (it tries to sort the digits of n, due to a special case in Jelly that's more harmful than useful here). If this is a problem, it can be fixed at the cost of 1 additional byte by adding an R after the æ«. • You can save a byte by collapsing it down to a single link: [æ«×3‘$HḂ?€⁹¡Ṣḣ⁸]tio.run/##AS8A0P9qZWxsef//…) – Nick Kennedy 2 days ago
• Regarding the use of Ŀ, the index has one subtracted and then is taken mod (the number of links minus 1), so 0 will point to the penultimate link. This also means it’s impossible to recursively call the main link using Ŀ. – Nick Kennedy 2 days ago

# J, 39 bytes

]{.[:/:~[_&(]2&|(-:,:1+3&*)})1+[:i.2&*


Try it online!

Called like k f n, returns the first n elements.

I am using the same algorithm as ais523, though I stumbled upon it independently.

• 1+[:i.2&* Generate n*2^k elements starting at 1.
• _&(]2&|(-:,:1+3&*)}) Apply collatz k times using Item Amend.
• [:/:~ Sort.
• ]{. Return first n.

# JavaScript (Node.js), 78 bytes

i=0;f=k=>f(k,c=(n,k)=>k--?c(2*n,k)|n%6==4&&c(~-n/3,k):console.log(i),c(++i,k))


Try it online!

Quite port but still some changes

# JavaScript (Node.js), 98 bytes

i=>g=(n,a=[...Array(i<<n+1)])=>n?g(n-1,a.map((c,j)=>(c=c||j,c%2?c*3+1:c/2))):a.sort((a,b)=>a-b)[i]


Try it online!

Pure definition

i<<n+1 for n=1 case

• You can use print from v8 or alert from browser instead of console.log. – A username May 3 at 5:31

# Brachylog, 34 bytes

Generates each sequence. Still a bit too verbose …

∧ℕ₁≜gT;?⟨×₂ᵐc{-₁/₃.%₂1∧}ˢ⟩ⁱ⁾l;Tj₍∋


Try it online!

∧ℕ₁≜gT;?⟨×₂ᵐc{-₁/₃.%₂1∧}ˢ⟩ⁱ⁾l;Tj₍∋
∧ℕ₁≜gT                              trying T = [1], then T = [2], then T = [3], …
;?⟨                ⟩ⁱ⁾        apply the predicade input times:
×₂ᵐ                         multiply each element by 2
{-₁/₃.%₂1∧}ˢ            select outputs where
(element - 1)/3 must be odd
c                        join both lists together
l;Tj₍∋  get the length of the final result,
and output T so many times


# Ruby, 67 65 bytes

f=->k,n{k<1?[*1..n]:f[k-1,n*2].map{|x|x%2<1?x/2:x*3+1}.sort[0,n]}


Try it online!

### Quickly explained:

If we know that the output is in the range (1..n), then we can start reducing the array (1..n*2^k). The rest is standard Collatz for k steps.

(Thanks Kirill L. for -1 byte)

# Retina, 84 bytes

~(.+),(.+)
.+¶$1*$(2$*)$2$*$¶¶¶$$.*¶%1+(_+)\1$$|(_+)¶3$*$$2$$1$$#2*¶O¶,G2¶_  Try it online! Explanation: Uses the same n2ᵏ approach as other answers. Works by building up a Retina program with k and n hardcoded in and then evaluating it. For example, the link demonstrates k=3 and n=20, and this results in the following Retina program: .+ 2*2*2*20*¶  Replace the input with n2ᵏ newlines.  .*  Generate all of the integers from 0 to n2ᵏ in unary. %  Separately for each line... 3+  ... repeat k times... (_+)\1|(_+) 3*21#2*  ... if the current value is even, then halve it, otherwise treble it and add 1. (The 3* needs to be at the beginning to avoid conflicting with the 1 while the #2* needs to be at the end to allow for an implicit _.) O  Sort all of the lines into order. (This is not a numeric sort because the lines are still in unary at this point.) ,G20  Select the nth line. _  Convert it to decimal. At a cost of 4 bytes, the first n terms can be output instead: ~(.+),(.+) .+¶1*(2*)2*¶¶¶$$.$*¶%$1+(_+)\1$$|(_+)¶3*$$2$$1$$#2$*¶O¶,G1,\$2¶%_


Try it online! Explanation: Only the last two lines change.

,G1,20


Select the first to the nth line. (There is actually a zeroth line that we need to skip.)

%_


Convert each line to decimal.

• If I had a dollar for every dollar in this program.. – Razetime May 3 at 11:06

# C (gcc), 183 $$\\cdots\$$ 149 148 bytes

g;t;l;i;e(a,b)int*a,*b;{i=*a>*b;i-=*a<*b;}f(k,n){int a[g=l=n<<k];for(;g||k--;g=qsort(a,l,4,e))for(i=l;i--;a[i]=g?i+1:t%2?3*t+1:t/2)t=a[i];i=a[n-1];}


Try it online!

Inputs $$\k\$$ and $$\1\$$-based $$\n\$$ and returns the $$\n^{\text{th}}\$$ element of $$\s_k\$$.

### Explanation

g;t;l;i;                                 // declare all int vars needed
e(a,b)int*a,*b;{i=*a>*b;i-=*a<*b;}       // comparator function for qsort
f(k,n){                                  // main function
int a[         ];                    // array a to hold sequences
g=                             // init g to non-zero
l=n<<k                      // length is n * 2**k
for(;                                // main loop
g||                             // g non-zero is an init loop for a
k--;                         // after that loop k times
g=qsort(a,l,4,e))        // end of each loop sort a
// and set g to zero (return value
// of qsort for success)
for(i=l;i--;                     // loop over all elements in a
a[i]=                // each loop set a[i] to...
g?              // if it's the init loop
i+1            // set a[i] to i + 1
:              // otherwise post-init loops
t%2?            // apply Collatz map to a[i]
3*t+1
:
t/2)
t=a[i];                      // temp for a[i] to save bytes
i=a[n-1];                            // return the 1-based nth value
}


# 05AB1E, 19 bytes

o*L¹FεDÉi3*>ë2÷]{I£


Try it online!

A port of the jelly answer

# Charcoal, 46 bytes

ＮθＮη≔…·¹×ηＸ²θζＦθＵＭζ⎇﹪κ²⊕×³κ⊘κＷ⁻ζυＦ№ζ⌊ι⊞υ⌊ιＩ…υη


Try it online! Link is to verbose version of code. Outputs the first n elements. Explanation:

ＮθＮη


Input k and n.

≔…·¹×ηＸ²θζ


Create a range from 1 to n2ᵏ.

ＦθＵＭζ⎇﹪κ²⊕×³κ⊘κ


Apply the Collatz formula k times to the range.

Ｗ⁻ζυＦ№ζ⌊ι⊞υ⌊ι


Sort the range.

Ｉ…υη


Output the first n elements.

A port of @hyper-neutrino's algorithm takes 48 bytes:

ＮθＮη≔⁰ζＷ‹Ｌυη«≦⊕ζ≔⟦ζ⟧εＦθ≔⁺⊗ε÷Φε⁼⁴﹪λ⁶¦³εＦε⊞υζ»Ｉ…υη


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

ＮθＮη


Input k and n.

≔⁰ζ


Start counting at 0.

Ｗ‹Ｌυη«


Repeat until we have at least n elements.

≦⊕ζ


Get the next value we want to calculate the count for.

≔⟦ζ⟧ε


Start with a list of just that value.

Ｆθ


Repeat k times...

≔⁺⊗ε÷Φε⁼⁴﹪λ⁶¦³ε


Double the list and integer divide an appropriately filtered copy of the list by 3. This results in a list of all the values that result in the target value after k steps.

Ｆε⊞υζ


Add that many copies of the target value to the list of results.

»Ｉ…υη


Output the first n elements.

# R, 76 bytes

f=function(k,n,a=1:(n*2^k),b=a%%2)if(k,f(k-1,n,sort(a*b*3+b+a/2*!b)),a[n])
`

Try it online!