20
\$\begingroup\$

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.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ Missed a trick here, should've been "Collatz-collate-repeat"... \$\endgroup\$ – Darrel Hoffman May 3 at 17:31
  • 1
    \$\begingroup\$ It feels like \$s_\infty\$ should be an infinite sequence of \$1\$s. I doubt this will be too hard to prove /s \$\endgroup\$ – hakr14 May 3 at 19:48
  • \$\begingroup\$ ...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. \$\endgroup\$ – hakr14 May 3 at 19:51
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Bubbler May 4 at 0:36
  • \$\begingroup\$ @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) \$\endgroup\$ – hakr14 May 4 at 0:40

14 Answers 14

8
\$\begingroup\$

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.

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

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.

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

Husk, 27 25 23 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).

\$\endgroup\$
4
  • 2
    \$\begingroup\$ Σz`R -> `Ṙ .... \$\endgroup\$ – Razetime May 3 at 2:46
  • \$\begingroup\$ @Razetime Thanks! I kept thinking that that part should be shorter but somehow forgot existed \$\endgroup\$ – Leo May 3 at 3:41
  • \$\begingroup\$ 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? \$\endgroup\$ – caird coinheringaahing May 3 at 12:09
  • \$\begingroup\$ @cairdcoinheringaahing the problem with that approach is: how can you sort an infinite list? \$\endgroup\$ – Leo May 3 at 12:12
6
\$\begingroup\$

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 æ«.

\$\endgroup\$
2
  • \$\begingroup\$ You can save a byte by collapsing it down to a single link: [æ«×3‘$HḂ?€⁹¡Ṣḣ⁸]tio.run/##AS8A0P9qZWxsef//…) \$\endgroup\$ – Nick Kennedy May 9 at 20:59
  • \$\begingroup\$ 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 Ŀ. \$\endgroup\$ – Nick Kennedy May 9 at 21:09
4
\$\begingroup\$

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

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

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

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

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)

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

Retina, 84 bytes

~`(.+),(.+)
.+¶$1*$(2$*)$2$*$¶¶¶$$.`$*¶%$1+`(_+)\1$$|(_+)¶3$*$$2$$1$$#2$*¶O`¶,G$2`¶_

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*$2$1$#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.

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

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

05AB1E, 19 bytes

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

Try it online!

A port of the jelly answer

\$\endgroup\$
0
\$\begingroup\$

Charcoal, 46 bytes

NθNη≔…·¹×ηX²θζFθUMζ⎇﹪κ²⊕׳κ⊘κW⁻ζυF№ζ⌊ι⊞υ⌊ιI…υη

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

NθNη

Input k and n.

≔…·¹×ηX²θζ

Create a range from 1 to n2ᵏ.

FθUMζ⎇﹪κ²⊕׳κ⊘κ

Apply the Collatz formula k times to the range.

W⁻ζυF№ζ⌊ι⊞υ⌊ι

Sort the range.

I…υη

Output the first n elements.

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

NθNη≔⁰ζW‹Lυη«≦⊕ζ≔⟦ζ⟧εFθ≔⁺⊗ε÷Φε⁼⁴﹪λ⁶¦³εFε⊞υζ»I…υη

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

NθNη

Input k and n.

≔⁰ζ

Start counting at 0.

W‹Lυη«

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.

Fθ

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.

Fε⊞υζ

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

»I…υη

Output the first n elements.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

Try it online or verify some more test cases.

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)
\$\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.