# Collatz Conjecture (OEIS A006577)

This is the Collatz Conjecture (OEIS A006577):

• Repeat the following steps:
• If n is even, divide it by 2.
• If n is odd, multiply it by 3 and add 1.

It is proven that for all positive integers up to 5 * 260, or about 5764000000000000000, n will eventually become 1.

Your task is to find out how many iterations it takes (of halving or tripling-plus-one) to reach 1.

Rules:

• Shortest code wins.
• If a number < 2 is input, or a non-integer, or a non-number, output does not matter.

Test cases

2  -> 1
16 -> 4
5  -> 5
7  -> 16


## GolfScript, 24232120 18 chars

~{(}{3*).2%6\?/}/,


Assumes input on stdin. Online test

• 1+ is special-cased as ). – Peter Taylor Aug 1 '13 at 11:59
• @PeterTaylor of course, forgot about that ;) – Volatility Aug 1 '13 at 12:01
• Nice work! <!-- padding --> – Peter Taylor Aug 2 '13 at 8:20
• @Peter: The <!-- --> don't work in comments. Use this instead. – Ilmari Karonen Aug 2 '13 at 10:36
• Or this. – Timwi Aug 3 '13 at 8:45

# C - 50 47 characters

Poor little C unfortunately requires an awful amount of code for basic I/O, so shorting all that down has made the UI slightly unintuitive.

b;main(a){return~-a?b++,main(a&1?3*a+1:a/2):b;}


Compile it with for example gcc -o 1 collatz.c. The input is in unary with space-separated digits, and you will find the answer in the exit code. An example with the number 17:

$> ./1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1$> echo $? 12$>

• return~-a? saves 1. Also moving b++ to the ? case should save b--. – ugoren Aug 30 '13 at 15:41
• Hehe you're bending the rules so much :P +1 for creativity and using a language not usually used to golf – Doorknob Aug 30 '13 at 16:56
• Thank you ugoren! I must have been drunk when writing it. :) – Fors Aug 30 '13 at 17:24

## Perl 34 (+1) chars

$\++,$_*=$_&1?3+1/$_:.5while$_>1}{  Abusing $\ for final output, as per usual. Run with the -p command line option, input is taken from stdin.

Saved one byte due to Elias Van Ootegem. Specifically, the observeration that the following two are equivalent:

$_=$_*3+1
$_*=3+1/$_


Although one byte longer, it saves two bytes by shortening $_/2 to just .5. Sample usage: $ echo 176 | perl -p collatz.pl
18


## PHP 54 bytes

<?for(;1<$n=&$argv;$c++)$n=$n&1?$n*3+1:$n/2;echo$c;


Javascript's archnemesis for the Wooden Spoon Award seems to have fallen a bit short in this challenge. There's not a whole lot of room for creativity with this problem, though. Input is taken as a command line argument.

Sample usage:

$php collatz.php 176 18  • Took me a while to figure out what the unmatched brackets are doing :) – marinus Aug 1 '13 at 22:21 • Repeating $_ in the ternary seems wasteful, you can shave off another character by using *= like this: $\++,$_*=$_&1?3+1/$_:.5while$_>1}{. Multiplying by 1/$_ has the same effect as +1, so $_*=3+1/$_ works just fine – Elias Van Ootegem Dec 21 '15 at 17:31
• @EliasVanOotegem $_*=3+1/$_ is brilliant, thanks! – primo Dec 22 '15 at 8:54

# Mathematica (35)

If[#>1,#0@If[OddQ@#,3#+1,#/2]+1,0]&


Usage:

If[#>1,#0[If[OddQ@#,3#+1,#/2]]+1,0]&@16
>> 4

• It's not a valid function, 10.3 complains about a rogue @ at the end – CalculatorFeline Apr 18 '16 at 5:29
• @ is calling the argument, I don't know why it was there, just a quick edit – miles Apr 18 '16 at 5:32
• Gotta be careful :) – CalculatorFeline Apr 18 '16 at 16:51

# FRACTRAN, 8 fractions (45 bytes)

$$\frac{5120}{33}, \frac{15}{11}, \frac{22}{105}, \frac{33}{560}, \frac{13}{5}, \frac{3}{2}, \frac{7}{9}, \frac{11}{7}$$

Takes input as $$\3^n\$$; halts at $$\3 \cdot 13^m\$$ for a sequence with $$\m\$$ iterations.

Try it online!

### How it works

If the current state is $$\3^n \cdot 13^m\$$, if $$\n = 1\$$, the program halts immediately; if $$\n = 2k\$$ is even, we have

$$\begin{multline*}3^{2k} \cdot 13^m \xrightarrow{\left(\frac{7}{9}\right)^k} 7^k \cdot 13^m \xrightarrow{\frac{11}{7}} 7^{k - 1}\cdot 11 \cdot 13^m \xrightarrow{\frac{15}{11}} 3 \cdot 5 \cdot 7^{k - 1} \cdot 13^m \\ \xrightarrow{\left(\frac{22}{105} \cdot \frac{15}{11}\right)^{k - 1}} 2^{k - 1} \cdot 3 \cdot 5 \cdot 13^m \xrightarrow{\frac{13}{5}} 2^{k - 1} \cdot 3 \cdot 13^{m + 1} \xrightarrow{\left(\frac{3}{2}\right)^{k - 1}} 3^k \cdot 13^{m + 1};\end{multline*}$$

and if $$\n = 2k + 1\$$ is odd, we have

$$\begin{multline*} 3^{2k + 1} \cdot 13^m \xrightarrow{\left(\frac{7}{9}\right)^k} 3 \cdot 7^k \cdot 13^m \xrightarrow{\frac{11}{7}} 3 \cdot 7^{k - 1} \cdot 11 \cdot 13^m \xrightarrow{\frac{5120}{33}} 2^{10} \cdot 5 \cdot 7^{k - 1} \cdot 13^m \\ \xrightarrow{\left(\frac{33}{560} \cdot \frac{5120}{33}\right)^{k - 1}} 2^{6k + 4} \cdot 5 \cdot 13^m \xrightarrow{\frac{13}{5}} 2^{6k + 4} \cdot 13^{m + 1} \xrightarrow{\left(\frac{3}{2}\right)^{6k + 4}} 3^{6k + 4} \cdot 13^{m + 1},\end{multline*}$$

where $$\6k + 4 = 3n + 1\$$.

• What a competitive solution (byte-count-wise) for such an unwieldy, syntax-limited language. – Bubbler Apr 20 '20 at 5:06
• If you use your Collatz program from another challenge, you can get another 8-fraction solution that fits in 41 bytes. gist.github.com/kmill/9462894fe99d9e93733e788585f45444 – Kyle Miller Apr 21 '20 at 22:58

As I usually do, I will start the answers off with my own.

## JavaScript, 46 44 chars (run on console)

for(n=prompt(),c=1;n>1;n=n%2?n*3+1:n/2,++c)c

• What is the point of ~~prompt() if you said the output doesn't matter if it is a non-integer? You can save two characters by getting rid of ~~. – Resorath Aug 1 '13 at 16:57
• @Resorath Ah, forgot about JS's auto casting :P thanks – Doorknob Aug 1 '13 at 23:28

### Rebmu: 28

u[++jE1 AeEV?a[d2A][a1M3a]]j


On a problem this brief and mathy, GolfScript will likely win by some percent against Rebmu (if it's not required to say, read files from the internet or generate JPG files). Yet I think most would agree the logic of the Golfscript is nowhere near as easy to follow, and the total executable stack running it is bigger.

Although Rebol's own creator Carl Sassenrath told me he found Rebmu "unreadable", he is busy, and hasn't time to really practice the pig-latin-like transformation via unmushing. This really is merely transformed to:

u [
++ j
e1 a: e ev? a [
d2 a
] [
a1 m3 a
]
]
j


Note that the space was required to get an a: instead of an a. This is a "set-word!" and the evaluator notices that symbol type to trigger assignment.

If it were written in unabbreviated (yet awkwardly-written Rebol), you'd get:

until [
++ j
1 == a: either even? a [
divide a 2
] [
]
]
j


Rebol, like Ruby, evaluates blocks to their last value. The UNTIL loop is a curious form of loop that takes no loop condition, it just stops looping when its block evaluates to something not FALSE or NONE. So at the point that 1 == the result of assigning A (the argument to rebmu) to the result of the Collatz conditional (either is an IF-ELSE which evaluates to the branch it chooses)... the loop breaks.

J and K are initialized to integer value zero in Rebmu. And as aforementioned, the whole thing evaluates to the last value. So a J reference at the end of the program means you get the number of iterations.

Usage:

>> rebmu/args [u[++jE1 AeEV?a[d2A][a1M3a]]j] 16
== 4


Java, 165, 156, 154,134,131,129,128,126 (verbose languages need some love too)

class a{public static void main(String[]a){for(int x=Short.valueOf(a),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y));}}


All is done inside the for

for(int x=Short.valueOf(a),y=0;x>1;x=x%2<1?x/2:x*3+1,System.out.println(++y))


That's freaking beautiful man. Thanks to Pater Taylor!!!, and the idea of using a for loop was stolen from ugoren

I replaced Integer for Short.

• You can quite easily save the length of i(,++y). You can save two more by using < instead of ==. – Peter Taylor Aug 1 '13 at 16:24
• @PeterTaylor you're right, my comparisons will be shorter with < , but I don't understand the part of the pre-increment – jsedano Aug 1 '13 at 16:29
• The two sides of your second ternary are structurally identical, so you can push the ternary into the first argument of the recursive call. – Peter Taylor Aug 1 '13 at 16:37
• OH MY GOD THAT'S BRILLIANT – jsedano Aug 1 '13 at 16:39
• I know it has been about 3.5 years, but you can still golf it by 5 bytes: class a{public static void main(String[]a){for(int x=new Short(a),y=0;x>1;System.out.println(++y))x=x%2<1?x/2:x*3+1;}} Changes made: 1) Replaced Short.valueOf(...) with new Short(...) for -4 bytes and 2) I've put the x=x%2<1?x/2:x*3+1; in the body of the for-loop to get rid of the comma for -1 byte. – Kevin Cruijssen Apr 5 '17 at 8:42

## Python repl, 48

I'm not convinced that there isn't a shorter expression than n=3*n+1;n/=1+n%2*5;. I probably found a dozen different expressions of all the same length...

i=0
n=input()
while~-n:n=3*n+1;n/=1+n%2*5;i+=1
i


edit: I've found another solution that will never contend, but is too fun not to share.

s='s'
i=s
n=i*input()
while 1:
while n==n[::2]+n[::2]:i+=s;n=n[::2]
if n==s:i.rindex(s);break
n=3*n+s
i+=s

• My brain hurts now. – daniero Aug 12 '13 at 17:55
• @daniero the second solution is just for you. – boothby Aug 13 '13 at 8:10
• Oh wow. I'm honored! – daniero Aug 15 '13 at 10:23
• (n//2,n*3+1)[n%2] is shorter. – Evpok Apr 5 '14 at 20:34
• @Evpok wouldn't n/2 work as well as we know it is even? – george Dec 16 '16 at 16:04

## APL (31)

A←0⋄A⊣{2⊤⍵:1+3×⍵⋄⍵÷2}⍣{⍺=A+←1}⎕

• old answer, yet, 27: {1=⍵:0⋄2|⍵:1+∇1+3×⍵⋄1+∇⍵÷2} – Uriel Dec 27 '17 at 17:33
• {1=⍵:0⋄1+∇⊃⍵⌽0 1+.5 3×⍵} – ngn Jan 16 '18 at 5:39

### J, 30 characters

<:#-:(1+3&*)]@.(2&|+1&=)^:a:


Turned out quite a bit longer than desired

usage:

   <:#-:(1+3&*)]@.(2&|+1&=)^:a:2
1
<:#-:(1+3&*)]@.(2&|+1&=)^:a:16
4
<:#-:(1+3&*)]@.(2&|+1&=)^:a:5
5
<:#-:(1+3&*)]@.(2&|+1&=)^:a:7
16
<:#-:(1+3&*)]@.(2&|+1&=)^:a:27
111

• -:(1+3&*)] is a gerund composed of three verbs, used on three occasions. -: means "halve", (1+3&*) or (1+3*]) encodes the multiplication step and ] (identity) aids termination.

• 2&|+1&= forms an index to the gerund. literally, "the remainder after division by two plus whether it equals one".

• #verb^:a: iterates the function until the result is stable (here, forced explicitly), while collecting the steps, then counts them. Stolen from @JB. <: decrements the step count by one to align with the question requirements.

• Whenever I see a J submission, I count the smilies. This one does pretty well: <:, #-:, :(, &*), =), )^:. – primo Aug 1 '13 at 14:58
• @primo nice; want their explanation? :-) <: means "decrement" or "less or equal", # means "count of" or "n times", -: means "halve" or "epsilon-equality", :( mean in turn the end of said "halve", the tie between two verbs in a gerund and a left parenthesis (used for grouping). &*) means "sth. bonded to the multiplication" (3 bonded with multiplication creates the "times three" operator) and the end of grouping. = performs equality checking or, in the unary sense, self-classification. ^: is the power conjunction (verb iteration). Since a lot of J verbs end with a colon, ... :-) – John Dvorak Aug 1 '13 at 15:10
• Years later... Improved loop block: '-&2#(>&1*-:+2&|*+:+>:@-:)^:a:' -> -1 char. :P – randomra Jan 26 '15 at 13:44
• More years later... <:#a:2&(<*|+|6&*%~) 19 bytes (-11) – miles Jan 10 '18 at 14:29

## Brachylog, 16 bytes

1b|{/₂ℕ|×₃+₁}↰+₁


Try it online!

### Explanation

         Either:
1        The input is 1.
b        In which case we unify the output with 0 by beheading the 1
(which removes the leading digit of the 1, and an "empty integer"
is the same as zero).
|        Or:
{        This inline predicate evaluates a single Collatz step on the input.
Either:
/₂       Divide the input by 2.
ℕ        And ensure that the result is a natural number (which is
equivalent to asserting that the input was even).
|        Or:
×₃+₁     Multiply the input by 3 and add 1.
}
↰        Recursively call the predicate on this result.
+₁       And add one to the output of the recursive call.


An alternative solution at the same byte count:

;.{/₂ℕ|×₃+₁}ⁱ⁾1∧


Try it online!

;.          The output of this is a pair [X,I] where X is the input and
I will be unified with the output.
{/₂ℕ|×₃+₁}  This is the Collatz step predicate we've also used above.
ⁱ⁾          We iterate this predicate I times on X. Since we haven't actually
specified I, it is still a free variable that Brachylog can backtrack
over and it will keep adding on iterations until the next
constraint can be satisfied.
1           Require the result of the iteration to be 1. Once this is
satisfied, the output variable will have been unified with
the minimum number of iterations to get here.
∧           This AND is just used to prevent the 1 from being implicitly
unified with the output variable as well.


Gambit scheme, 106 98 characters, 40 parentheses

(let((f(lambda(x)(cond((= x 1) 0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))))(f(read)))

91 89 chars with define directly

 (define(f x)(cond((= x 1)0)((odd? x)(+ 1(f(+ 1(* 3 x)))))(else(+ 1(f(/ x 2))))))(f(read)) 

• I haven't been around for a long time, but I have notice that usually people post 1 answer per programming language. – jsedano Aug 1 '13 at 18:03
• Sorry, I wasn't aware of that :) – Valentin CLEMENT Aug 1 '13 at 18:05
• Edited to remove the Python one. – Valentin CLEMENT Aug 1 '13 at 18:06
• Not true! People tend to post one answer per programming language, but that's because they're trying not to directly compete with someone else with a shorter answer. But nobody's going to complain if you post a different answer in the same language. – breadbox Aug 1 '13 at 19:05
• @breadbox not true. I post one answer per language if each solution is interesting by itself compared to the other. If both solutions are each as interesting as them both together (the same algorithm, no interesting language tricks), I post them as one. Normally I don't post multiple solutions because I choose a language first, then solve the problem in that language - then I'm usually too lazy to write the same in a different language - or I embark on a journey to learn yet another programming language. – John Dvorak Aug 2 '13 at 14:20

## PowerShell: 77747170 61

Golfed code:

for($i=(read-host);$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x


Notes:

I originally tried taking the user input without forcing it to an integer, but that broke in an interesting way. Any odd inputs would process inaccurately, but even inputs would work fine. It took me a minute to realize what was going on.

When performing multiplication or addition, PowerShell treats un-typed input as a string first. So, '5'*3+1 becomes '5551' instead of 16. The even inputs behaved fine because PowerShell doesn't have a default action for division against strings. Even the even inputs which would progress through odd numbers worked fine because, by the time PowerShell got to an odd number in the loop, the variable was already forced to an integer by the math operations anyway.

Thanks to Danko Durbic for pointing out I could just invert the multiplication operation, and not have to cast read-host to int since PowerShell bases its operations on the first object.

PowerShell Golfer's Tip: For some scenarios, like this one, switch beats if/else. Here, the difference was 2 characters.

Protip courtesy of Danko Durbic: For this particular scenario, an array can be used instead of switch, to save 8 more characters!

There's no error checking for non-integer values, or integers less than two.

If you'd like to audit the script, put ;$i just before the last close brace in the script. I'm not sure exactly how well PowerShell handles numbers that progress into very large values, but I expect accuracy is lost at some point. Unfortunately, I also expect there's not much that can be done about that without seriously bloating the script. Ungolfed code, with comments: # Start for loop to run Collatz algorithm. # Store user input in$i.
# Run until $i reaches 1. # Increment a counter,$x, with each run.
for($i=(read-host);$i-ne1;$x++) { # New$i is defined based on an array element derived from old $i.$i=(
# Array element 0 is the even numbers operation.
($i/2), # Array element 1 is the odd numbers operation. (3*$i+1)
# Array element that defines the new $i is selected by$i%2.
)[$i%2] } # Output$x when the loop is done.
$x # Variable cleanup. Don't include in golfed code. rv x,i  Test cases: Below are some samples with auditing enabled. I've also edited the output some for clarity, by adding labels to the input and final count and putting in spacing to set apart the Collatz values. --- Input: 2 1 Steps: 1 --- Input: 16 8 4 2 1 Steps: 4 --- Input: 5 16 8 4 2 1 Steps: 5 --- Input: 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Steps: 16 --- Input: 42 21 64 32 16 8 4 2 1 Steps: 8 --- Input: 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Steps: 17 --- Input: 197 592 296 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Steps: 26 --- Input: 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 Steps: 106 --- Input: 6174 3087 9262 4631 13894 6947 20842 10421 31264 15632 7816 3908 1954 977 2932 1466 733 2200 1100 550 275 826 413 1240 620 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 Steps: 111 --- Input: 8008135 24024406 12012203 36036610 18018305 54054916 27027458 13513729 40541188 20270594 10135297 30405892 15202946 7601473 22804420 11402210 5701105 17103316 8551658 4275829 12827488 6413744 3206872 1603436 801718 400859 1202578 601289 1803868 901934 450967 1352902 676451 2029354 1014677 3044032 1522016 761008 380504 190252 95126 47563 142690 71345 214036 107018 53509 160528 80264 40132 20066 10033 30100 15050 7525 22576 11288 5644 2822 1411 4234 2117 6352 3176 1588 794 397 1192 596 298 149 448 224 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Steps: 93 ---  Interesting bits about the input numbers which are not from the question's test cases: • Nice! You can still shorten it somewhat, by replacing switch with $i=(($i/2),($i*3+1))[$i%2] – Danko Durbić Nov 30 '13 at 9:32 • Also, you don't have to convert read-host to number - just change $i*3 to 3*$i. – Danko Durbić Nov 30 '13 at 9:52 • An array instead of switch? Brilliant! And swapping $i*3 around - why didn't I think of that already? – Iszi Nov 30 '13 at 18:37
• param($i)for(;$i-ne1;$x++){$i=(($i/2),(3*$i+1))[$i%2]}$x - swap the read-host for a parameter, to get 56 bytes. Try It Online link – TessellatingHeckler Jul 9 '17 at 20:59

## 80386 assembly, 16 bytes

This example uses AT&T syntax and the fastcall calling convention, the argument goes into ecx:

collatz:
or $-1,%eax # 3 bytes, eax = -1; .Loop: inc %eax # 1 byte, eax += 1; lea 1(%ecx,%ecx,2),%edx # 4 bytes, edx = 3*ecx + 1; shr %ecx # 2 bytes, CF = ecx & 1; # ecx /= 2; # ZF = ecx == 0; cmovc %edx,%ecx # 3 bytes, if (CF) ecx = edx; jnz .Loop # 2 bytes, if (!ZF) goto .Loop; ret # 1 byte, return (eax);  Here are the resulting 16 bytes of machine code: 83 c8 ff 40 8d 54 49 01 d1 e9 0f 42 ca 75 f4 c3  ## GolfScript (23 chars) ~{.1&{.3*)}*.2/.(}do;],  Online test ## F# - 65 chars let rec c n=function 1->n|i->c(n+1)(if i%2=0 then i/2 else i*3+1)  Python 68 58 54 52 chars f=lambda n:1+(n-2and f((n/2,3*n+1)[n%2]));f(input()) Thanks to Bakuriu and boothby for the tips :) • You can use n%2and 3*n+1or n/2 to save 5 characters. Also in python2 you can remove the call to int, reducing the size to 58 bytes. – Bakuriu Aug 3 '13 at 12:35 • Oh, you can even get shorter than that: [n/2,3*n+1][n%2]. – boothby Aug 6 '13 at 4:14 • That is nifty ! – Valentin CLEMENT Aug 6 '13 at 9:12 • Is this python 2.7? I get an error in Python 3.5.1? unsupported operand type(s) for -: 'str' and 'int' – george Dec 16 '16 at 16:01 # Retina, 43 bytes 11 2 (2+)1$1$1$0$0$0$0 2.*$0x
)2
1
1?x
1


Takes input and prints output in unary.

Each line should go to its own file. 1 byte per extra file added to byte-count.

You can run the code as one file with the -s flag. E.g.:

> echo -n 1111111|retina -s collatz
1111111111111111


The algorithm is a loop of doing a Collatz step with the unary number and adding a new step-marker x at the end of the string if the number isn't 1.

When the loop ends with 1, we convert the markers to a unary number (removing the leading 1) which is the desired output.

# Jelly, non-competing

12 bytes This answer is non-competing, since the challenge predates the creation of Jelly.

×3‘$HḂ?ß0’?‘  Try it online! ### How it works ×3‘$HḂ?ß0’?‘  Main link. Argument: n (integer)

Ḃ?       Yield the last bit of n is 1:
$Evaluate the three links to the left as a monadic chain: ×3 Multiply n by 3. ‘ Increment the product by 1. H Else, halve n. ’? If n-1 is non-zero: ß Recursively call the main link. 0 Else, yield 0. ‘ Increment the result by 1.  # brainfuck, 59 56 bytes ,-[<->[[>]+<[-<]>>]>[-<<[++>+<]>->]<<[+>+++<]<<+>>>]<<<.  Try it online! (Slightly modified for ease of use) Input and output as character codes. This is more useful with arbitrarily sized cells, but can still work with small values in limited cell sizes. ### How It Works Tape Format: Counter 0 Copy Number Binary... ^End ^Start ,-[ Get input, decrement by 1 and start loop <-> Initialises the copy of the value at -1 [[>]+<[-<]>>] Converts the input to binary while preserving a negative copy <+>>[-<<[++>+<]>->] If the last digit of the binary is 1 (n-1 is odd), divide by 2 and decrement <<[+>+++<] If the last digit of the binary is 0 (n-1 is even), multiply by 3 <<+>>> Increment counter and end on n-1 ]<<<. End loop and print counter  # FRACTRAN, 24 fractions Uses 180 bytes, for the more conventional counters... 68/13, 133/102, 341/51, 115/17, 17/19, 87/161, 17/23, 23/29, 53/93, 26973/217, 410/259, 43/111, 976/37, 37/41, 329/215, 37/43, 43/47, 118/265, 1/53, 53/59, 67/305, 1/61, 61/67, 117/4  Try it online! ### Explanation Am a bit lazy to add an explanation now; happy to do so if it gets attention/upvotes! However, I do have some notes for when I first wrote up the Collatz Conjecture code which you can run here. It's almost the same, but the TIO command line arguments are set to print every number in the sequence along the way, which makes it less of a blackbox! ### State Diagrams for COLLATZGAME Here are the state diagrams, for which I used Conway's original notation which he presents in this article. ### Change Made The above is simply to calculate the Collatz sequence for n given an input of the form 2^n. The only change I made to also keep count of the steps taken was to make the 1/3 from states Q -> D into an 11/3, 11 being the smallest unused prime. This fraction is only executed once for every number in the sequence; it's the state that figures out whether the number is even or odd to figure out what's next. Therefore, the 11 prime register is incremented once per number in the sequence, except one, yielding the number of steps. ### Note I simply encoded the state diagram as below and wrote an interpreter which did the dirty work. However, the work done to convert a state diagram to FRACTRAN is also detailed in Conway's article above: • A: 9/4 -> T • T: 4/1 -> Q • Q: 7/6*, 11/3 -> D, 5/1 -> R • R: 3/7*|Q • D: 1/3 -> E, 729/7 -> M • M: 10/7*, 1/3 -> N, 16/1 -> O • N: 7/5*|M • E: 2/5*|A • O: 1/5*|A # dc, 27 characters Applying boothby's black magic: ?[d3*1+d2%5*1+/d1<x]dsxxkzp  I'm not really sure if I understand how - or that - it works. Usage: $ dc collatz.dc <<< 7
16


# dc, 36 characters

My own creation; a somewhat more traditional approach, even tho I had to wrangle with the language a fair bit to overcome the lack of an else part to if statements:

?[2/2Q]se[dd2%[0=e3*1+]xd1<x]dsxxkzp


Internally it produces all numbers of the sequence and stores them on the stack, then pops the final 1 and displays the stack height.

• Parity is not black magic. – boothby Aug 12 '13 at 23:09
• No, but it's a very neat trick there! I have actually done similar stuff myself, I just didn't think about it in this case. What stumbled me for a second was the division, but I get it: You divide by six, reverting the first operation (*=3,+=1) with the second if the parity was wrong, and because of integer division the addition goes away too, and we've basically done /=2. Very clever :) – daniero Aug 13 '13 at 0:11
• +1. I thought I was going to crush this challenge with dc, but only got as far as 40. The I saw your 27 answer. Oh well. – Digital Trauma May 2 '14 at 0:46
• I hadn't seen this challenge, but blogged a while back about printing the Collatz sequence in dc. My approach is similar to yours but loses by a byte so I don't really see a reason to post it. However, when I was looking at mine to see how to easily go from printing each step to printing the number of steps, I spotted something that can golf a byte from yours... Since the Collatz sequence will always go from 2 to 1, you can change your conditional to 2<x and get rid of the k. Just in case you want a byte back after four years. :D – brhfl Aug 25 '17 at 20:13

# Hexagony, 48 44 bytes

?(]$_)"){{?{*')}/&!/={:<$["/>&_(.<@2'%<>./>=


Try it online!

Expanded:

     ? ( ] $_ ) " ) { { ? { * ' ) } / & ! / = . { <$ [
" / > & _ ( . < @
2 ' % < > : / >
= . . . . . .
. . . . . .
. . . . .


Note that this fails on 1 for uhh... reasons. Honestly, I'm not really sure how this works anymore. All I know is that the code for odd numbers is run backwards for even numbers? Somehow?

The new version is much cleaner than the previous, but has a few more directionals in comparison and also ends in a divide-by-zero error. The only case it doesn't error is when it actually handles 1 correctly.

• If a number < 2 is input ... output does not matter. :o) – Sok Mar 27 '18 at 12:47
• @Sok Yep, that's why I posted it instead of going insane trying to fix that – Jo King Mar 27 '18 at 12:49

# Jelly, 10 bytes

×3‘ƊHḂ?Ƭi2


Try it online!

### How it works

×3‘ƊHḂ?Ƭi2    Main link (monad). Input: integer >= 2
?       Create a "ternary-if" function:
Ḃ          If the input is odd,
×3‘Ɗ            compute 3*n+1;
H           otherwise, halve it.
Ƭ      Repeat until results are not unique; collect all results
i2    Find one-based index of 2


Example: The result of ...Ƭ for input 5 is [5, 16, 8, 4, 2, 1]. The one-based index of 1 is 6, which is 1 higher than expected. So we choose the index of 2 (which is guaranteed to come right before 1) instead.

## C, 70 69 chars

Quite simple, no tricks.

a;
main(b){
for(scanf("%d",&b);b-1;b=b%2?b*3+1:b/2)a++;
printf("%d",a);
}


# Q,46

{i::0;{x>1}{i+:1;\$[x mod 2;1+3*x;(_)x%2]}\x;i}

• 32 bytes with (#)1_(1<){(1+3*x;x%2)0=x mod 2}\  – mkst Oct 26 '17 at 22:17

# Ruby 1.9, 49 characters

Rubyfied Valentin CLEMENT's Python answer, using the stabby lambda syntax. Sqeezed it into one statement for added unreadability.

(f=->n{n>1&&1+f[[n/2,3*n+1][n%2]]||0})[gets.to_i]


Some overhead because Ruby, unlike Python, is not happy about mixing numbers with booleans.

# C++ (51 48)

This is a recursive function that does this; input reading comes separately.

int c(n){return n==1?0:1+(n%2?c(n*3+1):c(n/2));}


I'm sure I can do some sort of "and/or" trick with the == 0 stuff, but I have no idea how.

• You could remove the ==0 and swap the sides of the conditional – Doorknob Nov 30 '13 at 15:30
• Also, no need to handle n==1 because I specified in the question that the number is always greater than 1 – Doorknob Nov 30 '13 at 15:31
• The problem is that n==1 is the base recursion case. Putting n==2 there wouldn't improve the score any. – Joe Z. Nov 30 '13 at 17:57
• Ah, then you could just replace it with this: return~-n? and swap the conditional sides – Doorknob Nov 30 '13 at 23:20
• .n==1==n<2. – CalculatorFeline Apr 18 '16 at 16:53

# ~-~! (No Comment) - 71 53

This language is obviously not the best for golfing since it lacks a large amount of native functionality, but that's the beauty of it.

'=|*;~~[*,~~~-~]*/~~|:''=|'''==~[*]'''='&''':''&*+~|:


First, set ''' to your input. The function '' can then be called with % as it's input and will return the answer, like so:

'''=~~~~~:''&%:

This will return ~~~~~. It actually works for n==1 (it loops forever with n==0`).

As always with this language, untested.