# Collatz Encoding

#### 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

(1) 3 ->1 10 ->0 5 ->1 16 ->0 8 ->0 4 ->0 2 ->0 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


# 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

• Damn. I was sitting on it too long ... Apr 30, 2022 at 23:12
• Awesome solution! I came to this same realization, but couldn't figure out how to shorten the formula. May 1, 2022 at 4:57

# 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

• I love the :o at the end.... It's pretty much my face when trying to understand this... How does it work? May 1, 2022 at 8:32
• @AncientSwordRage Explanation added, BTW. (I forgot to ping you.) May 1, 2022 at 19:51

# 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}\$$.

• Incredible answer! Wow! May 1, 2022 at 5:27
• I don't know FRACTRAN so is it legitimate to provide input in any form other than pⁿ for some prime p?
– Neil
May 1, 2022 at 6:59
• @Neil I don't know if there are official rules. I subtracted one from the input and output for esthetic, not golfing reasons: they're 1-based but FRACTRAN is 0-based. Extra factors are pretty common in answers here. This FRACTRAN-specific challenge bans them, while this one by the same user allows them. I don't like the 11 factor in this answer, but I couldn't see how to make it reversible otherwise. State-transition instructions have to work both ways, so they have to be after other instructions of both states, so every state needs a way to test for itself. May 1, 2022 at 7:24

# 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.

• n*3//(6-5*c)+c can be (3*n+1)//(6-5*c), which leads to 53 bytes. (One more byte could be saved by switching to Python 2)
– ovs
May 1, 2022 at 10:38

# K (ngn/k), 31 bytes

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


Try it online!

• Almost all other solutions here carry two arguments through the iteration. Calculating the encoding on the Collatz sequence is a novel approach.
– doug
May 1, 2022 at 12:54

-2 bytes thanks to Unrelated String

a?n|n<2=a|p<-mod n 2=(2*a+p)?(6^p*ndiv2+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*ndiv2+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)
div2    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.

# 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.


# 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


# 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.

# 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,
↔                   reverse,
:1                    put the leading 1 back,
ḋ                      and convert from binary.

• another 17: ḋ:1hm%2U¡?o→*3½%2 May 1, 2022 at 1:36

*|{$[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 # 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) # 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.

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. • Thanks for the help @Steffan! Apr 30, 2022 at 21:40 • Fixed, if probably sub-optimally. Thanks for pointing that out! Apr 30, 2022 at 22:48 • n>1 works in place of n\=1; but even better, if you rearrange the order of the guards to put |n<2=[] first, you don't need to check n>1&& on the others. May 1, 2022 at 0:19 • Thanks for the help @DLosc! That saved a ton of bytes! May 1, 2022 at 0:40 # 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)  # 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: # 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. # 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


# 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.

• Separating the odd and even case seems to save a byte
– ovs
May 2, 2022 at 8:57
• Or 35 bytes with the cases combined
– ovs
May 2, 2022 at 9:01
• Ah sorry, It thought the URL was auto-updating like ATO. Here is an actual link for the first one. The other one is 1⊸{𝕨𝕊1:𝕨;(k⊑6‿1÷˜k+3×𝕩)𝕊˜𝕨+𝕨+k←2|𝕩}
– ovs
May 2, 2022 at 17:28
• Ah, nice! Didn't think of assigning 2|𝕩 to a name. I played around with the second one and found a better formula that saved 4 more bytes. :D May 2, 2022 at 18:54

# 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.

• -10 bytes. May 2, 2022 at 15:17
• @alephalpha I'm a bit new to stack exchange, should I edit my answer with your code and cite it, or leave it for people to find in the comments? May 3, 2022 at 13:13
• It's up to you. Usually I'll edit the answer and say something like "-n bytes thanks to @user". May 4, 2022 at 0:07

# 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)


# 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!

# 05AB1E, 17 bytes

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


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
ë     #  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)


# 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.

# 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

# 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.

# 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)


# 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


# 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%


# APL(Dyalog Unicode), 40 34 bytes SBCS

{⍺←⊂1⋄⍵=1:⍺⋄(p+2×⍺)∇p+⍵÷2÷6*p←2|⍵}
`

Try it on APLgolf!

Reworked to use the same idea as BQN.