Collatz Encoding

Question

The Collatz Conjecture

The famous Collatz Conjecture (which we will assume to be true for the challenge) defines a sequence for each natural number, and hypothesizes that every such sequence will ultimately reach 1. For a given starting number N, the following rules are repeatedly applied until the result is 1:

While N > 1:

• If N is even, divide by 2
• If N is odd, multiply by 3 and add 1

Collatz Encoding

For this challenge, I have defined the Collatz encoding of a number, such that the algorithm specified in the conjecture may be used to map it to another unique number. To do this, you start with a 1 and at each step of the algorithm, if you divide by 2 then append a 0, otherwise append a 1. This string of digits is the binary representation of the encoding.

As an example we will compute the Collatz Encoding of the number 3, with the appended digits marked. The sequence for 3 goes

₍₁₎ 3 ->₁ 10 ->₀ 5 ->₁ 16 ->₀ 8 ->₀ 4 ->₀ 2 ->₀ 1.

Therefore, our encoding is 208 (11010000 in binary).

The Challenge

Your challenge is to write a function or program which takes an integer (n>0) as input, and returns its Collatz encoding. This is a code golf challenge, so your goal is to minimize the number of bytes in your answer.

• For the edge case n=1, your solution should return 1, because no iterations are computed and every encoding starts with a 1.

• Floating point inaccuracies in larger results are acceptable if your language cannot handle such numbers accurately (encodings on the order of 10^40 as low as 27)

Test Cases

I have written a reference implementation (Try It Online!) which generates the encodings of the first 15 natural numbers:

  1 | 1
  2 | 2
  3 | 208
  4 | 4
  5 | 48
  6 | 336
  7 | 108816
  8 | 8
  9 | 829712
 10 | 80
 11 | 26896
 12 | 592
 13 | 784
 14 | 174352
 15 | 218128

Answer 1

Python 2, 49 bytes

f=lambda n,x=1:1/n*x or f(n/2-n%2*~n,x-n%2*~x<<1)

Try it online!

Explanation

Notice the following: if n is odd, 3*n+1 must be even. This means that in the odd case, we can combine two steps into one, with (3*n+1)/2. Although it seems more complicated, the formula actually becomes much shorter:

[n/2,(3*n+1)/2][n%2]
[n/2,n+n/2+1][n%2]
n/2+[0,n+1][n%2]
n/2+n%2*(n+1)
n/2+n%2*-~n
n/2-n%2*~n

Then, to calculate the Collatz encoding, we'll append [0] if n is even, and [1, 0] if n is odd. Working on integers, we see that x becomes [x*2,x*4+2][n%2]. This can be further reduced to x-n%2*~x<<1 (proof is left as an exercise to the reader).

Python 2, 50 bytes

f=lambda n,x=1:1/n*x or f(n/2-n%2*~n<<n%2,x*2+n%2)

Try it online!

The "obvious" method to compute the next term would be [n/2,3*n+1][n%2], but we can do better with a little bit magic: n/2-n%2*~n<<n%2. It can be derived by working backwards:

[n/2,3*n+1][n%2]
[n/2,(3*n+1)/2][n%2]<<n%2
n/2+[0,n+1][n%2]<<n%2
n/2+n%2*(n+1)<<n%2
n/2+n%2*-~n<<n%2
n/2-n%2*~n<<n%2

Answer 2

JavaScript (ES6), 41 bytes

f=(n,o=1)=>n>1?f(n&1?n*3+1:n/2,2*o|n&1):o

Try it online!

Commented

f = (             // f is a recursive function taking:
  n,              //   n = input
  o = 1           //   o = output, initialized to 1
) =>              //
n > 1 ?           // if n is still greater than 1:
  f(              //   do a recursive call:
    n & 1 ?       //     if n is odd:
      n * 3 + 1   //       use 3n + 1
    :             //     else:
      n / 2,      //       use n / 2
    2 * o | n & 1 //     append the parity bit of n to the output
  )               //   end of recursive call
:                 // else:
  o               //   we're done: return the output

Answer 3

FRACTRAN, 11 fractions (72 bytes) and reversible

$$\frac{7}{13},\frac{11}{17},\frac{247}{35},\frac{338}{441},\frac{104}{21},\frac{425}{209},\frac{153}{44},\frac{85}{49},\frac{169}{22},\frac{17}{7},\frac{195}{11}$$

The input is \$11\cdot 2^{n-1}\$ and the output is \$11\cdot 5^{k-1}\$ where \$k\$ is the Collatz encoding of \$n\$. (Note: it doesn't halt there. It will go on to generate all the other redundant encodings of this technically multivalued function, for every number of \$4,2,1\$ cycles.)

If you replace all the instructions with their reciprocals and give it \$11\cdot 5^{k-1}\$ as input, it will compute \$11\cdot 2^{n-1}\$.

Answer 4

Python 3.8 (pre-release), 55 bytes

f=lambda n,e=1:e*(n<2)or f(n*3//(6-5*(c:=n%2))+c,2*e+c)

Try it online!

This one uses an extra byte to do integer division since otherwise the answers accrue floating point innacuracy. I decided to submit the one with the extra / because Python can handle arbitrarily large integers according to your memory.

Answer 5

K (ngn/k), 31 bytes

2/1 :':2!(1<){(-2!x;1+3*x)2!x}\

Try it online!

Answer 6

x86 32-bit machine code, 20 bytes

41 D1 E9 73 0A 6B C9 06 83 C1 04 0F 29 C0 F9 D1 D0 E2 ED C3

Try it online!

Uses the fastcall calling convention – argument in ECX, result in EAX.

In assembly:

s:  inc ecx     # Add 1 to restore the value of ECX.
    shr ecx, 1  # Shift ECX right by 1; the low bit goes into CF.
    jnc a       # Jump if CF=0 (the number was even).
    imul ecx, 6 # Multiply ECX by 6.
    add ecx, 4  # Add 4 to ECX, producing 3n+1 where n is the original value
    .byte 0x0F  # Effectively skip an instruction by making it part of a harmless "movaps xmm0, xmm0".
f:  sub eax, eax        # (Start here.) Set EAX to 0.
    stc         # Set CF to 1.
a:  rcl eax, 1  # Append CF to the bits of EAX.
    loop s      # Subtract 1 from ECX and jump if it's nonzero.
    ret         # Return.

Answer 7

Haskell, 55 53 49 bytes

-2 bytes thanks to Unrelated String

a?n|n<2=a|p<-mod n 2=(2*a+p)?(6^p*n`div`2+p)
(1?)

The solution is the anonymous function (1?). Attempt This Online!

Explanation

Port of my BQN solution, essentially. We define an infix function ? that takes an accumulator a and a number n:

a ? n

When n is 1, just return the accumulator:

    | n < 2 = a

Otherwise, calculate n mod 2 and assign to p (for "parity"):

    | p <- mod n 2

Compute the new accumulator and number, and recurse:

        = (2 * a + p) ? (6 ^ p * n `div` 2 + p)

The new accumulator is simply twice the current accumulator plus the parity (2 * a + p). The Collatz function calculation is a little more involved:

6^p*n`div`2+p
6^p            6 to the power of the parity (1 if even, 6 if odd)
   *n          Times n (n if even, 6*n if odd)
     `div`2    Int-divided by 2 (n `div` 2 if even, 3*n if odd)
           +p  Plus the parity (n `div` 2 if even, 3*n+1 if odd)

Then our solution is simply ? with a first argument (initial accumulator value) of 1.

Answer 8

Pip, 27 26 bytes

Wa>1Io.:Y%aa:6Ey*a/2+y;FBo

Attempt This Online!

Explanation

Wa>1Io.:Y%aa:6Ey*a/2+y;FBo
                            a is first cmdline input; o is 1 (implicit)
W                           While
 a>1                        a is greater than 1:
         %a                  Parity of a (0 if even, 1 if odd)
        Y                    Yank into y variable
     o.:                     Concatenate to o in-place
    I                        If new value of o is truthy (which is always the case):
             6Ey              6 to the power of y (1 if a is even, 6 if odd)
                *a            Times a
                  /2          Divided by 2 (a/2 if even, 3*a if odd)
                    +y        Plus y (a/2 if even, 3*a+1 if odd)
           a:                 Assign that result back to a
                      ;     (Needed for parsing)
                       FBo  Convert the final value of o from binary
                            Autoprint

Answer 9

C (gcc), 49 bytes

e;f(n){for(e=1;~-n;n=n%2?++e,3*n+1:n/2)e+=e;n=e;}

Try it online!

Inputs an integer.
Returns its Collatz encoding.

Answer 10

Husk, 17 bytes

ḋ:1m%2↑←¡?o→*3½%2

Try it online!

Should be golfable. Ties ḋ:1hm%2U¡?o→*3½%2 courtesy of @Razetime.

        ¡            Infinitely iterate on the argument:
         ?     %2    if even,
              ½      halve, else
          o→*3       3n+1.
      ↑←             Take while != 1,
   m%2               map mod 2,
 :1                  prepend 1,
ḋ                    convert from binary.

Only reason I thought to use Husk for this is this almost works:

Husk, 19 bytes

ḋ:1↔tḋ€Σ¡ṁ§eDo/3←;1

Try it online!

Unfortunately manages to give 3840 instead of 829712 for 9, by virtue of not actually caring about the paths deterministically chosen (takes 28 to 85 as well as 14).

        ¡              Infinitely iterate
                 ;1    starting from [1]
         ṁ             concat-map
          §e           \n -> [   ,      ]
            D                 2*n
             o/3←                  n-1/3 ,
       Σ               concatenate the iterations,
      €                find the first 1-index of the input in them,
     ḋ                 convert to binary,
    t                  remove the leading 1,
   ↔                   reverse,
 :1                    put the leading 1 back,
ḋ                      and convert from binary.

Answer 11

K (ngn/k), 53 52 48 46 bytes

*|{$[1=n:*x;:x;*p;1+3*n;-2!n],2/|p:2 0!'x}/|1,

Try it online!

Pretty straightforward stab at this. Recurse with accumulator carrying both the number and the encoding.

-1 found a byte by using encode
-4 trying to remember lessons coltim passed on. (use tacit)
-2 don’t need list syntax

Answer 12

Python 3.8 (pre-release), 50 bytes

f=lambda n,x=0:4//n*x/2or f(1-6*n//(l:=n^-n),~x*l)

Try it online!

Returns a float (+1 byte for int).

Test harness from @dingledooper or whoever they nicked it from ;-)

How?

Straight-forward recursion with one twist: Group n steps down, 1 step up into one iteration. This avoids branching at the expense of a slightly more complicated body. Detail: Recall that n^-n clears the lowest set bit in n and sets all above including the sign bit, so this is effectively the same as -2 * (n&-n)

Answer 13

Retina 0.8.2, 72 68 bytes

.+
$*1;1
{+`^(1+)\1;(1+)
$1;$2$2
^1;(1+)
$.1
(1+);(1+)
1$1$1$1;1$2$2

Try it online! Link is to test suite that computes the results from 1 to n. Explanation:

.+
$*1;1

Convert n to unary and pair it with an initial output value of 1.

{`

Repeat while the input is paired.

+`^(1+)\1;(1+)
$1;$2$2

While n is even, halve it and double the output value.

^1;(1+)
$.1

If n is 1, then delete it and convert the output to decimal.

(1+);(1+)
1$1$1$1;1$2$2

Otherwise, triple n, double the output, and increment both of them.

After porting to Retina 1, it's possible to golf the answer down to 53 bytes, but for some reason it becomes inordinately slow:

.+
_;$&*
+`(_+);(_+)\2(_?)
$1$1$3;$2$.3*$(4*_5*$2
\G_

Try it online! Link includes faster test cases. Explanation:

.+
_;$&*

Convert n to unary and pair an initial output value of 1 with it.

+`(_+);(_+)\2(_?)
$1$1$3;$2$.3*$(4*_5*$2

While n is greater than 1, perform a Collatz step on it, updating the output value appropriately. Here $1 is the previous output value, $2 is n//2 (integer division) and $3 is n%2, thus n is replaced by n//2+n%2*(n//2*5+4) which computes equal to n*3+1 when n is odd.

\G_

Convert the output value to decimal and delete n.

Answer 14

Haskell, 107 bytes

s d 0=0
s(a:q)n=a*2^n+(s q$n-1)
f n|n<2=[]|even n=0:f(div n 2)|1>0=1:f(n*3+1)
r 1=1
r n=s(1:f n)$length$f n

Attempt This Online!

I am new to Haskell golf, so I apologize for any bits of this that are outrageously ungolfed.

Answer 15

Factor + math.extras project-euler.014, 59 bytes

[ collatz [ < ] monotonic-count rest 1 prefix 48 v+n bin> ]

Try it online!

There is no way Factor would be competitive using the mathy recursive algorithm. Too many symbols means too much whitespace. So we take advantage of the fact that Factor has a built-in collatz sequence word and a simple way to detect increases in a sequence.

Explanation

                       ! 3
collatz                ! { 3 10 5 16 8 4 2 1 }
[ < ] monotonic-count  ! { 0 1 0 1 0 0 0 0 }          (did it increase? then 1)
rest 1 prefix          ! { 1 1 0 1 0 0 0 0 }          (change first element to 1)
48 v+n                 ! { 49 49 48 49 48 48 48 48 }  (add 48 [equivalent to "11010000"])
bin>                   ! 208                          (convert from binary)

Answer 16

Re:direction, 42 38 bytes

++v
v>
<
+>+
>v
+> >
v
+> >>
> >v
+ >>

Try it online!

The following notation will be used for the contents of the queue: a number means that many ►s, and | means one ▼. If the input number is N, the initial queue is N|, but for the purpose of this program, it's better to view it as N|0.

This program works through the Collatz iterations, while having the second number be 1 less than a number containing the result bits. It does two iterations at a time for odd numbers greater than 1. The possibilities are as shown:

Answer 17

Charcoal, 30 bytes

Ｎθ⊞υ¹Ｗ⊖θ≔⎇↨⁰⊞Ｏυ﹪θ²⊕׳θ÷θ²θＩ↨²υ

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

Ｎθ

Input n.

⊞υ¹

Start with a Collatz encoding of 1.

Ｗ⊖θ

Repeat until n=1.

≔⎇↨⁰⊞Ｏυ﹪θ²⊕׳θ÷θ²θ

Save n%2 to the encoded value, and switch on that to halve or increment and triple n as appropriate. (Note that in order to avoid floating-point inaccuracy, I've used an integer halve, which is a byte longer than a floating-point halve.)

Ｉ↨²υ

Output the encoded value converted from base 2.

Answer 18

Jelly, 14 bytes

×3‘$HḂ?’пḂṙ-Ḅ

Try it online!

How it works

×3‘$HḂ?’пḂṙ-Ḅ - Main link. Takes n on the left
        п     - While loop, collecting each iteration i:
       ’       -   Condition: i > 1
      ?        -   Body: If:
     Ḃ         -     Condition: Bit; i % 2
   $           -     True:
×3             -       3i
  ‘            -       3i+1
    H          -     False: Halve
          Ḃ    - Bit of each i
           ṙ-  - Rotate the final 1 to the front
             Ḅ - Convert from binary

Answer 19

BQN, 36 31 bytes

-5 bytes inspired by ovs

1⊸{a𝕊1:a;(p+2×𝕨)𝕊p+𝕩÷2÷6⋆p←2|𝕩}

Anonymous function that takes an integer and returns its Collatz encoding. Try it at BQN online

Explanation

1⊸{a𝕊1:a;(p+2×𝕨)𝕊p+𝕩÷2÷6⋆p←2|𝕩}
  {                            }  Function of two arguments (right argument is the
                                  number, left argument calculates the answer):
   a𝕊1:                            Given left argument a and right argument 1,
       a                           return a
        ;                          Otherwise,
                 𝕊                 call this function recursively
                                   with new right argument:
                            2|𝕩     Current number mod 2
                          p←        Store that value in p (for parity)
                        6⋆          6 to that power (1 for even numbers, 6 for odd)
                      2÷            2 divided by that amount (2 or 1/3)
                    𝕩÷              Current number divided by that (x/2 or x*3)
                  p+                Add p (x/2+0 or x*3+1)
         (      )                  and new left argument:
            2×𝕨                     Current accumulator times 2
          p+                         Plus p

1⊸                                Call that function with a left argument of 1

Somewhat surprisingly, there seem to be no floating point errors from dividing by 3 until the numbers get too large to store as integers anyway.

Answer 20

Rust, 77 67 61 bytes

-10 bytes, thanks @alephalpha.
-6 bytes, thanks @Juan Ignacio Díaz

|mut n|{let mut b=1;while n>1{b=2*b+n%2;n=[n/2,3*n+1][n%2]}b}

Try it online!

If overflows are not okay we can use 81 74 (-6 bytes, thanks @Juan Ignacio Díaz) bytes instead and write

|mut n|{let mut b=1.;while n!=1{if n%2>0{b=2.*b+1.;n=3*n+1;}b*=2.;n/=2;}b}

Try it online!

which returns the value as a float, so it doesn't overflow for an input of 27. Instead it returns 4272797808638851700000000000000000, which is 137289440854955024 too small.

Answer 21

tinylisp 2, 78 bytes

(d E(\(N(A 1))(?(= N 1)A(E(?(o N)(+(* 3 N)1)(/ N 2))(+(o N)A A

Try it at Replit: enter the above definition, and then on the next line call it like (E 7), or test multiple arguments with something like (map E (1to 10)).

Ungolfed/explanation

Another port of my BQN answer.

(def encode           ; Define encode
 (lambda              ; as a lambda function
  (num (accum 1))     ; that takes a number and an accumulator that defaults to 1:
  (if (= num 1)       ;  If num is 1,
   accum              ;   return accum
   (encode            ;  Else, do a recursive call with these arguments:
    (if (odd? num)    ;   First argument: if num is odd,
     (+ (* 3 num) 1)  ;    3 * num + 1
     (/ num 2))       ;    else num / 2
    (+ (odd? num)     ;   Second argument: add 1 if num is odd, 0 otherwise
     accum            ;    to accum
     accum)))))       ;    and accum again--thus, 2 * accum + (num mod 2)

Answer 22

PARI/GP, 47 bytes

f(n,i=1)=if(n<2,i,f(if(n%2,3*n+1,n/2),2*i+n%2))

Attempt This Online!

Answer 23

05AB1E, 17 bytes

[D#ÐÉi3*>ë;])ÉÁ2β

Try it online or verify all test cases.

Explanation:

[          # Loop indefinitely:
 D         #  Duplicate the current value
           #  (which will be the implicit input in the first iteration)
  #        #  If it's equal to 1: stop the infinite loop
   Ð       #  Triplicate the current value
    Éi     #  Pop one, and it it's odd:
      3*   #   Multiply the value by 3
        >  #   And add 1
     ë     #  Else (it's even instead):
      ;    #   Halve it
]          # Close the if-else statement and loop
 )         # Wrap all values on the stack into a list
  É        # Check for each value whether it's odd
   Á       # Rotate the list once towards the right
    2β     # Convert it from a binary-list to an integer
           # (after which the result is output implicitly)

Answer 24

R, 58 bytes

f=function(n,o=1,m=n%%2)`if`(n>1,f((5*m+1)*n/2+m,2*o+m),o)

Try it online!

Recursive function.

---

R, 58 bytes

function(n){while(n>1){T=T*2+(m=n%%2)
n=(5*m+1)*n/2+m}
+T}

Try it online!

Non-recursive approach, same length.

Answer 25

Desmos, 83 80 bytes

i->i+si+sk,n->(floor(n/2)+kn+k)(k+1)s
s=max(0,sign(n-1))
k=mod(n,2)
i=1
n=\ans_0

Try it on Desmos!

-3 bytes thanks to Aiden Chow

Answer 26

C, 75 54 bytes

Edit: 54 bytes, credit to ceilingcat.

c(n,x){for(x=1;n>1;n=n%2?x++,n*3+1:n/2)x+=x;return x;}

Works with gcc and clang. Test main: main(){for(int i=1;i<16;i++) printf("%d\n",c(i));}

Takes and returns int16_t. Beware of the dreaded integer overflow.

81 chars, not conforming to requirements, but no overflow:

#define P putchar(4
c(n){P 9);for(;n>1;){if(n%2){n=n*3+1;P 9);}else{n/=2;P 8);}}}

Prints as binary to stdout.

Answer 27

Wolfram Language(Mathematica), 61 bytes

Try it online!

f[n_,i_:1]:=If[n<2,i,f[If[Mod[n,2]==1,3n+1,n/2],2i+Mod[n,2]]]

Answer 28

MathGolf, 16 bytes

┴ò_■_@<\_┴←¬]y░å

Try it online.

Unfortunately there seem to be some bugs in MathGolf with the ‼ and ä builtins, since this should have been possible in 12 bytes instead: ┴ô_■‼<_┴←¬]ä..

Explanation:

┴                # Check if the (implicit) input is equal to 1
          ←      # While false with pop,
 ò               # execute the following 6 characters as inner code-block:
  _              #  Duplicate the current value
   ■             #  Pop the copy, and push its Collatz value
    _            #  Duplicate that Collatz value
     @           #  Triple-swap the top three values on the stack: a,b,b → b,a,b
      <          #  Pop the top two and push a<b
       \         #  Swap the top two values
        _        #  Duplicate the top value
         ┴       #  Pop the copy, and check if it's equal to 1
           ¬     #  Rotate the stack once, so this duplicated 1 is at the front
            ]    # Wrap the entire stack into a list
             y   # Join it together to a number
              ░  # Convert it to a string
               å # Convert it from a binary-string to an integer
                 # (after which the entire stack is output implicitly)

Answer 29

Burlesque, 41 bytes

1{J2dv{2./}{3.*+.}IE}C~J1Fi.+1+]m{2.%}2ug

Try it online!

1        # Continuation takes last (1) value from stack
{
 J       # Duplicate
 2dv     # Divisible by two
 {2./}   # Halve
 {3.*+.} # *3+1
 IE      # If else
}C~      # Continue infinitely
J        # Duplicate
1Fi      # Find index of 1
.+       # Take that many
1+]      # Prepend 1
m{2.%}   # Map mod 2
2ug      # Read as binary digits

Answer 30

Batch, 152 bytes

@if %1==1 echo 1&exit/b0
@set n=%1&set s=1
:l
@set/at=%n%%%2,s=%s%*2
@if %t%==1 (set/an=%n%*3+1,s=%s%+1)else set/an=%n%/2
@if %n% gtr 1 goto:l
@echo %s%