# 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"... Commented May 3, 2021 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 Commented May 3, 2021 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. Commented May 3, 2021 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. Commented May 4, 2021 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) Commented May 4, 2021 at 0:40

# 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
Commented May 3, 2021 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. Commented May 3, 2021 at 1:07
• @Bubbler Fair enough. Fixed, and also golfed a bit more by combining with Leo. Thanks. Commented May 3, 2021 at 1:08
• Nice answer! Switching to Python 2 is shorter here; I can get you down to 91 bytes. Commented May 3, 2021 at 3:18
• 81 bytes Commented May 3, 2021 at 13:08

([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. • Very nice! 71 bytes Commented May 3, 2021 at 7:41 # 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 -> Ṙ .... Commented May 3, 2021 at 2:46 • @Razetime Thanks! I kept thinking that that part should be shorter but somehow forgot Ṙ existed – Leo Commented May 3, 2021 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? Commented May 3, 2021 at 12:09 • @cairdcoinheringaahing the problem with that approach is: how can you sort an infinite list? – Leo Commented May 3, 2021 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//…) Commented May 9, 2021 at 20:59
• 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 Ŀ. Commented May 9, 2021 at 21:09

# 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. Commented May 3, 2021 at 5:31

# 05AB1E, 19 bytes

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


Try it online!

A port of the jelly answer

# 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.. Commented May 3, 2021 at 11:06 # MathGolf, 9 bytes ²╒kÉm■sk<  Port of hyper-neutrino♦'s Python 2 answer, so will also output the first $$\n\$$ values (and will use the trick of only checking the range $$\[1,n^2]\$$). Explanation: ² # Square the (implicit) first input n ╒ # Pop and push a list in the range [1,n²] k # Push the second input k É # Pop and loop k amount of times using 3 characters as inner code-block: m # Map each value in the list to: ■ # Pop and calculate its Collatz value s # Then sort the list from lowest to highest k # After the loop, push the first input n again < # And only leave that many leading items from the list # (after which the entire stack is output implicitly as result)  # C (gcc), 183 $$\\cdots\$$ 148 126 bytes g;t;l;i;f(k,n){int a[g=l=n<<k];for(;g||k--;g=qsort(a,l,4,L"\x62b078bǃ"))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! Saved a whopping 22 bytes thanks to ceilingcat!!! 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 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, // end of each loop sort L"\x62b078bǃ") // using a -zexecstack // comparator 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 }  • @ceilingcat Awesome golf - thanks! :D Commented Dec 7, 2023 at 15:45 # 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! # Haskell, 96 bytes (x:w)#h|x<=h!!0=x:w#h x#y=y#x g x=[div i 2|i<-x,even i]#[3*i+1|i<-x,odd i] f 0=[1..] f n=g$f\$n-1
`

Try it online!