[Question]
  [
#### The Collatz Conjecture
The famous [Collatz Conjecture](https://en.wikipedia.org/wiki/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!](https://tio.run/##fVBda8JAEHzvrxgOhLs2qJdAH0Kvf6QUiWajW8JeOE@Ktf72mA8/0AfnYWFnZwZ2mn3ceMnatqQKK1/XRfxbkKx8SVpM/oIOw8qyhsOXsup7IH83XBMEn7CjqgdXHTNBCucwv9E9BDOH9I665E6LpiEptZorcxVQvaXHBIfsVfAG@zzGnmOGsWQpwn6xjWH8QKnpj2fRF9coDRR3QcAS9Z0hQWraygdwd0MoZE3aJrDv52qa0FsqdeA8O@Ifh4cK2eQfR2XaEw)) 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]
# [Python 2](https://docs.python.org/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!](https://tio.run/##JY3NbsJADITveQpfKnZRgHjzt0Hss1RBbUokcFZhEalU9dXTcTnN2J89E7/TZRK3rkO49rfzR0@SL4GPfJDtQtNMg5GD28mb2/6CvMxyOrFdB1ChUWju5evTcE7c2GOGTcxpeqRIgW59NKOkHDfPd4BHMnZ/j9cxmQ390MbajOKMC/QAWwrh/3UlYnDOiBzUQUvVwsNVcBW0VtVFA1OWDVyrT4X3rIPHoLhTdV3LiOFChwJG813jO1yydtSdYm1pPdJZW7itylrXWuXYs/N/ "Python 2 ‚Äì 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](https://docs.python.org/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!](https://tio.run/##HY3NTsQwDITvfQpf0CYlsLX7l642z4KKoEul3TQqWVEkxKuXMadv7LFn0nf@WKLs@xSu4@31baTotsAnPsZyo2WlycSjPMUHKX/j@Qy6rZRH0O4T7EhzpHWMl3fDjrizpwKb5Gi550SBbmMyc8wON18vMO7Z2OfPdJ2zOdAPHawtKK24QBFsSyH8v@5EDJ8LIgEFrJWVh2qgGrBV6qKDqOsOqtenynvWwWNQe1DK0DNiuNKhgtB86fyAS9aOdlBbW3qPdNYW7pu61bVWCXsW/wc "Python 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]
# 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!](https://tio.run/##DYyxDoJAEAV7vmIrc8uBZDE24MG3EOCMhrwlQGyUbz@3mskU8x4@wz5ur/UoodOcUgwOhQbh0KGTPjpcpEd@89Kgqos6158VbjRF3RwokLQEehjvJt4zfTOiUbHrMl8XfdqPbMOcnekP "JavaScript (Node.js) ‚Äì 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]
# 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]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), 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!](https://tio.run/##DcrRCsIgFADQ977iMgjudcbS1QiZ/YuZlrDuRPYSa99uO88nf5f3zP0tl1qjndzn8XTAMlhlgkAeNc0FIrLouw6H01WgN5aPmqj1UovQeqpxLwkSQ3H8CqikGsgcYJdL4gVjsyZz7zf4wRoxkRkv5w0aqn8 "Python 3.8 (pre-release) ‚Äì 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]
# [K (ngn/k)](https://codeberg.org/ngn/k), 31 bytes
```
2/1 :':2!(1<){(-2!x;1+3*x)2!x}\
```
[Try it online!](https://ngn.bitbucket.io/k#eJwtzDsOwjAURNE+qxhXSYhQPM+/sWEpdCipKSgsobB2UtDd5ty92Uq0sZmbeJ8/09Vcv3EJlz6fdTyGYeuv7fluhMG8EBGFEDLoJWYIslpokIdl1YxUDUURLDGkE1E0/TfffeTimH5Y7Br3)
[Answer]
# 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!](https://tio.run/##XVFNT8MwDD3Hv8IUTUr2pbEhDhvjgsSNCyckhqY0TdugLJ2aFDJN/HWKuzIh8MFx3vPHk632@0mhVNteGqdsk2m89SEz1bS8gz@QNel/rDau6DDQMejaYXKf4HG7lYGYtAl6u@U8lz4oaa0QaFzAnHdeihW@VyZDz8XqE6TfIcenhMO0sFUqLebgl4wmoVYRmC/rLhjjFbA3AiUws2tsj90Ak1nWx9fApukhaJzF2QPkS@abFLUkhhz1CQrkktXK9iC1s1W1Rw@s1gFEgmIF0AncSeN6pXWhxqhKWeNwSJ93AUdAso6MuMbZGA/dszqhH6WxGvloFPF2jYu5OKGd7WlZIefJwODkDgdm45IxkoacRyH64nPKxj1KVRqnUVWZXiY/dPwdk1V4PGfjYDZ/pl6HNeeN86ZwOjsJHgovXuJo9EorPgs74AU1ifeLfyORk65uc170wn54WktDh6Wxn9C2Xyq3svDtZLeYk6Ozralc228 "C++ (gcc) ‚Äì 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]
# [Haskell](https://www.haskell.org), ~~55~~ ~~53~~ 49 bytes
*-2 bytes thanks to [Unrelated String](https://codegolf.stackexchange.com/users/85334)*
```
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!](https://ato.pxeger.com/run?1=m708I7E4OzUnZ8GCpaUlaboWN80T7fNq8myMbBNr8lNSFPJsNYy0ErUNNe01jLXygHRNio0uUMQ2xT4ls0whT8GIK9VWw9BeE6J9T25iZp6CrUJBUWZeiYJGbmKBQqpCtKGenqFBLFQJzCYA)
### 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]
# [Pip](https://github.com/dloscutoff/pip), ~~27~~ 26 bytes
```
Wa>1Io.:Y%aa:6Ey*a/2+y;FBo
```
[Attempt This Online!](https://ato.pxeger.com/run?1=m724ILNgwYKlpSVpuha7whPtDD3z9awiVRMTrcxcK7US9Y20K63dnPIhCqDqFkebx0KZAA)
### 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]
# [C (gcc)](https://gcc.gnu.org/), 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!](https://tio.run/##XZDRToMwFIbv9xQnJEvKKNlaBhQremF8CreLpTtMonYLJZG44KOLB4Zkk6SF/uc/Xzm/CQ/GdB3qgln/XBwrhrnQ36HVNrdz@RgEyKOFDcSdXUofgxypgLrtSlvDx660zIfzDOjphRpd7V62kMNZcJAcIg5rDjGHhEPKQXHIOIgVLaoLMghyCLKIuNUTBpsTmhr31yS5UgNrTa8oSnqKUiIZmEpmaQ9TBJaJykiNMzqnqien6yjuAUIJqcZbzNG6GszrrlrQjuYNq8tl3qZ5lpsme6IVexyuz5E3dlNMwPofLe0eG2pb6fHzHlz5hceC/Y3gL0dhMSkagmBw@wPskt6UINEuKQ6Wrb6pOqoWrPZvVSR1iux/26kiS8G8@R7CB6B97jaWBqs5OD7N7vIctyO2nbXdjynedwfXhZ@/ "C (gcc) ‚Äì Try It Online")
Inputs an integer.  
Returns its Collatz encoding.
[Answer]
# [Husk](https://github.com/barbuz/Husk), 17 bytes
```
·∏ã:1m%2‚Üë‚Üê¬°?o‚Üí*3¬Ω%2
```
[Try it online!](https://tio.run/##ASwA0/9odXNr/23igoHhuKMxNf/huIs6MW0lMuKGkeKGkMKhP2/ihpIqM8K9JTL//w "Husk ‚Äì 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](https://github.com/barbuz/Husk), 19 bytes
```
·∏ã:1‚Üît·∏ã‚Ç¨Œ£¬°·πÅ¬ßeDo/3‚Üê;1
```
[Try it online!](https://tio.run/##yygtzv6f@6ip8eGOxYam/x/u6LYyfNQ2pQTIeNS05tziQwsf7mw8tDzVJV/f@FHbBGvD//8B "Husk ‚Äì 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]
# [K (ngn/k)](https://codeberg.org/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!](https://ngn.bitbucket.io/k#eJxLs9KqqVaJNrTNs9KqsLaqsNYqsDbUNtbKs9Y1UsyL1THSrymwMlIwUFSvqNWvMdTh4srTUU9z0LfKszLUVjQ14AIASPYQlQ==)
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]
# [Python 3.8 (pre-release)](https://docs.python.org/3.8/), 50 bytes
```
f=lambda n,x=0:4//n*x/2or f(1-6*n//(l:=n^-n),~x*l)
```
[Try it online!](https://tio.run/##HU3RboMwEHvnK@6tCaJLLoEQkPIrk5g2NiR6RDSVmFT119ndnuyzfXb@LT8b@Zj385zTOt0@Pieg5kh2bI2h@jBu22FWeA01GaPWMdH7lXTzOupVnzObBAvBPtH3l8IGMOixYiU3sD1KhgS3KauFSiPioyj9ds/rUtQFnnDRuoK8swtq5lDWkNL/nz4BkBNYAThGx@gFbWTWMmsZO0ERAhPvA7NenmyMKEfkQ@xB0A09cg1aOSwT6XchDpxE2egGsWWlj9yOsoJ96zuRZcphRBf/AA "Python 3.8 (pre-release) ‚Äì 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]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), ~~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!](https://tio.run/##K0otycxL/K@nzaWixWXIZaiScGgbl3uCHpeqhm@CIUTc0NqQq1o7IU7DUFszxtAaRHGpGFqrGKkYccXB@HqGXCAGhGeoAobWhiA1//8bmgIA "Retina 0.8.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](https://github.com/m-ender/retina/wiki/The-Language) 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!](https://tio.run/##FcQ7CoAwEAXA/p1jlXwguJsoQgrLXCKwsbCwsRDvH5WBuY/nvHbugymtBw/NNDr4ZtTb/FfF6GZB/ImZhEJ0ZJLT2ZGgFu2dIYhImLFgBU9gAccX "Retina ‚Äì 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]
# [Haskell](https://www.haskell.org), 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!](https://ato.pxeger.com/run?1=NY5BCoMwFET3OcVfuEgUIdFNkf5epLQQMFbRjtVYV96kGzelt-g9epsGxFkMw2Ng5vWprW9d163r-zlV6eHXeipJsxZe2mJQYBtnVyTS0xAhNUpUhAXHjM-Xxc0OBNZFJctmJlCmFnPSbAJAnCehPZJhExzsZcAEFXUOt6mOQt4mv3fbgMueBO16jA0mkiPlSmyl_d8f)
I am new to Haskell golf, so I apologize for any bits of this that are outrageously ungolfed.
[Answer]
# [Factor](https://factorcode.org/) + `math.extras project-euler.014`, 59 bytes
```
[ collatz [ < ] monotonic-count rest 1 prefix 48 v+n bin> ]
```
[Try it online!](https://tio.run/##JYwxD4IwFIR3fsXtCrEJJkaNq3FxMU6EoTQPxUBbXx8E/fMVZLlc7vJ9tTbiON5vl@t5D8/uRUZS6lvibKNydFqe/8hoFNYBgd49WUNhWb3mQLz0gWZXmCwk8vHcWFkO1vYxAYckUVsUal2VsYBxbavliwJHlOicdeJsY1Lj@oljCgI1q@pmRL7DsLKoGntCGTvtkcUf "Factor ‚Äì 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]
# [Re:direction](https://esolangs.org/wiki/Re:direction), ~~42~~ 38 bytes
```
++v
v>
<
+>+
>v
+> >
v
+> >>
> >v
+ >>
```
[Try it online!](https://tio.run/##K0rVTcksSk0uyczP@/9fW7uMq8yOy4ZL206by64MSCnYcUEoOy4gAWQCWf//mwMA "Re:direction ‚Äì 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:
[![Execution path for 1](https://i.stack.imgur.com/NVUwG.png)](https://i.stack.imgur.com/NVUwG.png)
[![Execution path for 2N](https://i.stack.imgur.com/jYwu5.png)](https://i.stack.imgur.com/jYwu5.png)
[![Execution path for 2N+1](https://i.stack.imgur.com/399Jy.png)](https://i.stack.imgur.com/399Jy.png)
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 30 bytes
```
ÔºÆŒ∏‚äûœÖ¬πÔº∑‚äñŒ∏‚âî‚éá‚Ü®‚Å∞‚äûÔºØœÖÔπ™Œ∏¬≤‚äï√ó¬≥Œ∏√∑Œ∏¬≤Œ∏Ôº©‚Ü®¬≤œÖ
```
[Try it online!](https://tio.run/##RY67DsIwDEV3vsKjIwUJyoQ6AV068Bj6A6G1aKQ0aZ2kiK8PqYrEZtnnHt@2V9w6ZVKq7RjDLQ5PYpxEuXlE32OUsM/zu9eGACtqmQaygbqMCDh5r18WG2Kr@INn5Ql3EpbkfSRWwfFiuLouGoeThEIIIaG2f02jB/J4kDCtl1DpWXf0g5d1bsLaBrwoH9YXhYSYRWVKx7SdzRc "Charcoal ‚Äì 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]
# [Jelly](https://github.com/DennisMitchell/jelly), 14 bytes
```
√ó3‚Äò$H·∏Ç?‚Äô√ê¬ø·∏Ç·πô-·∏Ñ
```
[Try it online!](https://tio.run/##y0rNyan8///wdONHDTNUPB7uaLJ/1DDz8IRD@4HMhztn6j7c0fLf@nC7pvv//4amAA "Jelly ‚Äì 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]
# [BQN](https://mlochbaum.github.io/BQN/), ~~36~~ 31 bytes
*-5 bytes inspired by [ovs](https://codegolf.stackexchange.com/users/64121/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](https://mlochbaum.github.io/BQN/try.html#code=RiDihpAgMeKKuHth8J2VijE6YTsocCsyw5fwnZWoKfCdlYpwK/CdlanDtzLDtzbii4Zw4oaQMnzwnZWpfQoKRsKoIDEr4oaVMTU=)
### 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]
# [Rust](https://www.rust-lang.org/), ~~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!](https://tio.run/##TY1LCsIwGAb3PcVvQUgfVBIXLkq8SOmigRYD7afkgWCas8cWRZzVMJsx3ro0gZZBgxUUMtqY7oZAGsSbRorLt@48jIabcWB5iHlNLK2Ld4Q1zKOjXZXk7fOm55Fw5UFJUaoKR9FCdjiJ@lyi4n23lT6qmOiPgoEGS97q11j8hh@LWUxv "Rust ‚Äì 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!](https://tio.run/##TY1BCsIwFAX3PcVvQUhaiSYuXJTvXQy0GEifUlNcpDl7TFHEWQ3zFm9eniGPoOnqICTFigrjfSaQA2ml2Jy/deMxOwSPWjQxNXsSeZ2WQFijHwJtalmr/nVzfiDUrKMbCTtzOUbLRrW2Kyv41KLTfbJtaT0ObIqnTH9IAfk7/ViqUn4D "Rust ‚Äì 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]
# [tinylisp 2](https://github.com/dloscutoff/tinylisp2), 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](https://replit.com/@dloscutoff/tinylisp2): 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]
# [PARI/GP](https://pari.math.u-bordeaux.fr), 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!](https://ato.pxeger.com/run?1=m728ILEoMz69YMGCpaUlaboWN_XTNPJ0Mm0NNW0zgSwbI51MnTQNEFPVSMdYK0_bUCdP30hTx0grUxsopKkJ1aaSll-kkadgq2Coo2BoqqNQUJSZVwIUUFLQtQMSQP2aMLUwqwA)
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 17 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
[D#√ê√âi3*>√´;])√â√Å2Œ≤
```
[Try it online](https://tio.run/##yy9OTMpM/f8/2kX58ITDnZnGWnaHV1vHah7uPNxodG7T///GAA) or [verify all test cases](https://tio.run/##ATQAy/9vc2FiaWX/MTVFTj8iIOKGkiAiP04i/1tEI8OQw4lpMyo@w6s7XSnDicOBMs6y/yIuViz/).
**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]
# [R](https://www.r-project.org/), 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!](https://tio.run/##LczLCcAgDADQaYREAyWCl4KdxSIVBE2kn0Ont5e@Ad45s7Z2SI6zxPJIvqsKCGlk6lGM8ZhqSSAbUwEItjtGK4t3nbxV15EU57WP0V7glQP9H84P "R ‚Äì Try It Online")
Recursive function.
---
# [R](https://www.r-project.org/), 58 bytes
```
function(n){while(n>1){T=T*2+(m=n%%2)
n=(5*m+1)*n/2+m}
+T}
```
[Try it online!](https://tio.run/##K/qfnJ@Tk5qXbPs/rTQvuSQzP08jT7O6PCMzJ1Ujz85QszrENkTLSFsj1zZPVdVIkyvPVsNUK1fbUFMrT99IO7eWSzuk9n9xYkFBTqWGoZWhqQ7UPM3/AA "R ‚Äì Try It Online")
Non-recursive approach, same length.
[Answer]
# [Desmos](https://www.desmos.com), ~~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!](https://www.desmos.com/calculator/iknrh8ko9z)
*-3 bytes thanks to Aiden Chow*
[Answer]
# 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]
# [Wolfram Language(Mathematica)](https://www.wolfram.com/wolframscript/), 61 bytes
[Try it online!](https://tio.run/##y00syUjNTSzJTE78/z8tOi9eJzPeyjDWytYTyLEx0snUSYsGMn3zU6LzdIxibW0NdYzztA118vSNYnWMMrVhErGx/13yowOKMvNKgHwFJQVdOwUlHQWgIbGxOgrVQCFDIDKtjf0PAA)
```
f[n_,i_:1]:=If[n<2,i,f[If[Mod[n,2]==1,3n+1,n/2],2i+Mod[n,2]]]
```
[Answer]
# [MathGolf](https://github.com/maxbergmark/mathgolf/blob/master/math_golf.txt), 16 [bytes](https://github.com/maxbergmark/mathgolf/blob/master/code_page.py)
```
‚î¥√≤_‚ñ†_@<\_‚î¥‚Üê¬¨]y‚ñë√•
```
[Try it online.](https://tio.run/##y00syUjPz0n7///RlC2HN8U/mrYg3sEmJh7Ie9Q24dCa2MpH0yYeXvr/vyGXEZcxlwmXKZcZlzmXBZcll6EBl6Ehl6ERl6Exl6EJl6EpAA)
Unfortunately there seem to be some bugs in MathGolf with the `‚Äº` and `√§` builtins, since this should have been possible in 12 [bytes](https://github.com/maxbergmark/mathgolf/blob/master/code_page.py) 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]
# [Burlesque](https://github.com/FMNSSun/Burlesque), 41 bytes
```
1{J2dv{2./}{3.*+.}IE}C~J1Fi.+1+]m{2.%}2ug
```
[Try it online!](https://tio.run/##FY0xC8IwFIR3f0UWESzGvJe2SegoChZ3py6iSEFBK3FJ41@P76bv7l1yd4nT4/Z5x1tJq7nrNsM0Fko9X7@J9TYnq9eVzsd93v16Ooy6omp4SrTMHO8lvvL5VJQiNStaKMVCFlrQeFG1qFrYgDi0IqxtRTl8Mt4TjBeDOIAcHEkNGRgjAv3c@iAvCRtNQIwV56WdsEKutg3OmGLyxP4P "Burlesque ‚Äì 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]
# 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%
```
]