Collatz Conjecture (OEIS A006577)

Question

This is the Collatz Conjecture (OEIS A006577):

Start with an integer n > 1.
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 * 2⁶⁰, 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.

Relevant xkcd :)

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

MD XF · Accepted Answer · 2017-09-21 04:10:27Z

PARI/GP, 38 bytes

a(n)=if(n==1,0,a(if(n%2,3*n+1,n/2))+1)

Try it online!

Equivalent to this readable C code:

int b(n)
{
    if (n % 2)
        return 3 * n + 1;
    else
        return n / 2;
}

int a(n)
{
    if (n == 1)
        return 0;
    else
        return a(b(n)) + 1;
}

numbermaniac · Accepted Answer · 2017-10-06 06:50:38Z

1

Casio-Basic, 83 72 bytes

71 bytes for code, +1 for n as parameter.

0⇒z
While n≠1
piecewise(mod(n,2),3n+1,n/2)⇒n
z+1⇒z
WhileEnd
Print z

edited Oct 6 '17 at 6:50

answered May 12 '17 at 9:00

numbermaniac

6395 silver badges12 bronze badges

add a comment |

DLosc · Accepted Answer · 2017-10-26 21:43:57Z

tinylisp repl, 68 bytes

(load library)(d f(q((n)(i(e n 1)0(inc(f(i(even? n)(/ n 2)(inc(* 3 n

Try it online! (Note that the repl auto-closes parentheses; on TIO, they have to be explicitly closed, which I've done in the footer.)

This is the same recursive solution as, e.g., Carcigenicate's Clojure answer. Because tinylisp has only addition and subtraction built in, I load the standard library to get even?, /, and * (and inc, which is the same length as a 1 but looks nicer). Other library functions would make the code longer; for instance, I'm defining the function manually with (q((n)(...))) rather than using (lambda(n)(...)). Here's how it would look ungolfed and indented:

(load library)
(def collatz
  (lambda (n)
    (if (equal? n 1)
      0
      (inc
        (collatz
          (if (even? n)
            (/ n 2)
            (inc (* 3 n))))))))

Going the other direction, here's a 101-byte solution that doesn't use the library. The E function returns n/2 if n is even and the empty list (falsey) if n is odd, so it can be used both to test evenness and to divide by 2.*

(d E(q((n _)(i(l n 2)(i n()_)(E(s n 2)(a _ 1
(d f(q((n)(i(e n 1)0(a 1(f(i(E n 0)(E n 0)(a(a(a n n)n)1

_{* Only works for strictly positive integers, but that's exactly what we're dealing with in this challenge.}

steenbergh · Accepted Answer · 2017-12-27 12:16:09Z

QBIC, 34 33 bytes

:{~-a|_Xb\b=b+1~a%2|a=a*3+1\a=a/2

Pretty straightforward:

:           Name the Command Line Parameter 'a'
{           Start an infinite loop
~-a|_Xb     If 'a' = 1 (or -a = -1, QB's TRUE value), quit printing 'b'
\           ELSE (a > 1)
b=b+1       Increment step counter
~a%2        In QBasic, 8 mod 2 yields 0, and 0 is considered false
|a=a*3+1    Collatz Odd branch
\a=a/2      Collatz Even branch

Conor O'Brien · Accepted Answer · 2018-01-09 05:18:58Z

1

Attache, 11 bytes

CollatzSize

Try it online!

Not much to say...

answered Jan 9 '18 at 5:18

Conor O'Brien

36.2k2 gold badges71 silver badges165 bronze badges

add a comment |

DLosc · Accepted Answer · 2018-01-09 08:33:32Z

Acc!!, 127 75 bytes

Count u while N/49 {
_+1
}
Count i while _-1 {
_/2+_%2*(5*_/2+2)
Write 49
}

The program takes input and produces output in unary. Try it online!

(Here's a decimal I/O version in 209 bytes.)

With comments

# Read input in unary
Count u while N/49 {   # Increment u from 0 while input character is >= "1"
  _+1                  # Add one to accumulator
}

# Main loop
Count i while _-1 {    # Increment i from 0 while accumulator is not equal to 1
  _/2+_%2*(5*_/2+2)    # Apply one step of Collatz function to accumulator
  Write 49             # Write "1" to output
}

The expression _/2+_%2*(5*_/2+2) boils down to

_/2,               if _%2 is 0
_/2 + (5*_)/2 + 2, if _%2 is 1

This is integer division, so the latter case comes out to

_/2 + 2*_ + _/2 + 2
 = 2*_ + (_/2)*2 + 2
 = 2*_ + _ + 1
 = 3*_ + 1

Martin Ender · Accepted Answer · 2018-02-21 14:11:04Z

Wumpus, 22 bytes

I]=2:~3*)=&~~!0~.
l(O@

Try it online!

Explanation

The first line is the main loop which iterates the Collatz function until we get 1. We keep track of the number of steps by growing the stack by one element on each iteration.

I   Read a decimal integer N from STDIN. At EOF (i.e. on subsequent 
    iterations) this pushes 0 instead.
]   Rotate the stack right. On the first iteration, this does nothing, but
    afterwards this moves the 0 to the bottom of the stack.
=   Duplicate N.
2:  Compute N/2.
~   Swap with the other copy of N.
3*) Compute 3N+1.
=   Duplicate.
&~  3N+1 times: swap N/2 and 3N+1. If N is odd, 3N+1 is even and vice versa.
    We end up with the value that we want on top and the incorrect one
    underneath.
~   Swap them once more.
!   Logical NOT. 3N+1 is always positive and N/2 gives 0 iff N = 1 (in which 
    case N/2 will also be on top of the stack). So this essentially gives us
    1 iff N = 1 (and 0 otherwise). Call this value y.
0~. Jump to (0, y), i.e. to the beginning of the second line once we reach N = 1
    and to the beginning of the first line otherwise.

Once we reach 1:

l   Push the stack depth. The stack holds one zero for each iteration as well
    as the final result. But note that we won't terminate until the iteration
    that process 1 itself (because we check the condition at the end of
    the loop, but based on its initial N). So the stack depth is one
    greater than the number of steps to reach 1.
(   Decrement.
O   Print as decimal integer.
@   Terminate the program.

I've got an alternative 22 byte solution, but unfortunately I haven't found anything shorter yet:

I]3*)=2%5*):=(!0~.
lO@

X1M4L · Accepted Answer · 2018-05-09 15:42:38Z

1

Java (OpenJDK 8), 54 bytes

a->{int c=0;for(;a!=1;c++)a=a%2>0?a*3+1:a/2;return c;}

Try it online!

This answer is a little to simple to justify an explanation, it’s just a while loop and a ternary expression.

edited May 9 '18 at 15:42

answered Mar 26 '18 at 12:43

X1M4L

1,5867 silver badges17 bronze badges

add a comment |

Stewie Griffin · Accepted Answer · 2018-05-12 20:29:06Z

Octave, 65 bytes

@(x)eval 'k=0;do++k;if mod(x,2)x=3*x+1;else x/=2;end,until x<2,k'

Try it online!

It's time we have an Octave answer here. It's a straight forward implementation of the algorithm, but there are several small golfs.

Using do ... until instead of while ... end saves some bytes. Instead of having while x>1,k++;...end, we could have do++k;...until x<2, saving two bytes. Using eval in an anonymous function saves a few bytes, compared to having input(''). Also, skipping the parentheses in the eval call saves some bytes.

Joey · Accepted Answer · 2018-06-14 17:35:03Z

1

Ruby, 48 bytes

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

Same as other Ruby, but using n%2?a:b syntax instead of [a,b][n%2]. Saves one char.

answered Jun 14 '18 at 17:35

Joey

111 bronze badge

\$\begingroup\$ You mention that you save one byte off of the other Ruby answer yet your answer is 13 bytes longer because of (...)[gets.to_i]. Even if I remove that (which doesn't break your answer) you still have the same length as the other answer. This is ok, I just thought maybe you might have made a mistake. \$\endgroup\$ – Ad Hoc Garf Hunter Jun 19 '18 at 14:11

add a comment |

Francisco Hahn · Accepted Answer · 2018-06-14 19:21:53Z

1

PHP, 80 73 Bytes

Tried a recursive function Try it here! (80 Bytes)

Try it online (73 Bytes)

Code (recursive function)

function f($n,$c=0){echo($n!=1)?(($n%2)?f($n*3+1,$c+1):f($n/2,$c+1)):$c;}

Output

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

Explanation

function f($n,$c=0){ //$c counts the iterations, $n the input
echo($n!=1)?    
(($n%2)?
    f($n*3+1,$c+1): //$n is odd
    f($n/2,$c+1))   //$n is even
:$c;                 //echo $c (counter) when n ==1
}

edited Jun 14 '18 at 19:21

answered Mar 26 '18 at 13:23

Francisco Hahn

5912 silver badges10 bronze badges

\$\begingroup\$ No, the test cases aren't part of the byte count. Your submission looks fine as it is. \$\endgroup\$ – Martin Ender Mar 26 '18 at 13:42

add a comment |

maxb · Accepted Answer · 2018-11-15 09:22:57Z

MathGolf, 7 bytes

kÅ■┐▲î

Don't get fooled, there's a non-breaking space at the end of the program.

Try it online!

Explanation

k        Read input as integer
 Å       Start a block of length 2
  ■      Map TOS to the next item in the collatz sequence
   ┐     Push TOS-1 without popping
    ▲    Do block while TOS is true
     î   Push the length of the last loop
         Discard everything but top of stack

MathGolf, 14 bytes (no built-ins, provided by JoKing)

{_¥¿É3*)½┐}▲;î

Explanation

{               Start block of arbitrary length
 _              Duplicate TOS
  ¥             Modulo 2
   ¿            If-else (works with TOS which is 0 or 1 based on evenness)
    É3*)        If true, multiply TOS by 3 and increment
        ½       Otherwise halve TOS
         ┐      Push TOS-1 (making the loop end when TOS == 1)
          }▲    End block, making it a do-while-true with pop
            ;   Discard TOS
             î  Print the loop counter of the previous loop (1-based)

Ideally, this solution could become 13 bytes, since it's not neccessary to have the ending of the block be explicit when the loop type instruction comes right after. I'll see when I get around to coding implicit block ending when loop type is present.

Try it online!

Nice solution! I'll have to analyze a bit before I understand it completely. I wrote this solution when the language was still really new, there are a bunch of new features now — maxb, Oct 6 '18 at 9:25
@JoKing I've looked your solution over, and I might have to clarify the documentation, ∙ (documented as "triplicate TOS") does not push TOS*3, but instead pushes TOS 3 times. Your solution gives the correct input for powers of 2, but fails for e.g. input 7. — maxb, Nov 15 '18 at 8:15

Bijan · Accepted Answer · 2018-12-24 15:55:19Z

1

C (gcc), 43 33 bytes

f(x){x=~-x?f(x&1?3*x+1:x/2)+1:0;}

Try it online!

edited Dec 24 '18 at 15:55

answered Apr 4 '17 at 23:24

Bijan

7817 silver badges11 bronze badges

add a comment |

Shaggy · Accepted Answer · 2019-01-23 23:45:49Z

1

Japt, 18 15 bytes

É©Òß[U*3ÄUz]gUv

Try it

edited Jan 23 '19 at 23:45

answered Feb 21 '18 at 15:14

Shaggy

25.1k3 gold badges22 silver badges74 bronze badges

add a comment |

score 1 · Accepted Answer · 2019-12-14 00:56:49Z

1

Keg `-rR`, 23 bytes (SBCS)

^{I really need to remember those new instructions.}

0&{:1>|:2%[3*⑨|½]⑹

Try it online!

edited Dec 14 '19 at 0:56

answered Dec 12 '19 at 12:41

user85052

\$\begingroup\$ -5 bytes with -rR and new register commands \$\endgroup\$ – Lyxal Dec 13 '19 at 20:24

add a comment |

RosLuP · Accepted Answer · 2016-12-05 09:45:06Z

Axiom, 74 bytes

g(a)==(c:=0;repeat(a<=1=>break;c:=c+1;a rem 2=0=>(a:=a quo 2);a:=3*a+1);c)

ungolfed

gg(a)==
   c:=0
   repeat
      a<=1     =>break
      c:=c+1 
      a rem 2=0=>(a:=a quo 2)
      a:=3*a+1
   c

results

(3) -> [i,g(i)] for i in [2,16,5,7,1232456,123245677777777777777777777777777]
   Compiling function g with type PositiveInteger -> NonNegativeInteger
   (3)
   [[2,1], [16,4], [5,5], [7,16], [1232456,191],
    [123245677777777777777777777777777,572]]
                                      Type: Tuple List NonNegativeInteger

Community · Accepted Answer · 2017-04-13 12:39:01Z

0

R, 57 55 bytes

x=scan();n=0;while(x-1){x='if'(x%%2,3*x+1,x/2);n=n+1};n

Not much to say, uses a nice statement within the while loop, which should become 0 -> False only when x=1, similar to the check whether x is odd or even. This also uses the implicit conversion of 0->False and nonzero -> True.

Saved 2 bytes thanks to a trick by @Billywob used in this answer.

edited Apr 13 '17 at 12:39

Community♦

1

answered Dec 5 '16 at 10:14

JAD

2,8981 gold badge6 silver badges31 bronze badges

\$\begingroup\$ Abusing a built-in (F) saves 4 bytes - the other change is just a different way of doing the if, not golfier. \$\endgroup\$ – JayCe Jun 14 '18 at 19:35

add a comment |

nimi · Accepted Answer · 2016-12-06 23:15:00Z

0

Haskell, 43 Bytes

c 1=0
c x|odd x=1+c(3*x+1)|1<2=1+c(x`div`2)

Usage: c 7-> 16

edited Dec 6 '16 at 23:15

answered Jan 23 '15 at 0:16

nimi

34.7k3 gold badges29 silver badges92 bronze badges

\$\begingroup\$ What's "Haskell 2"? \$\endgroup\$ – nyuszika7h Dec 6 '16 at 23:14
2

\$\begingroup\$ @nyuszika7h: a typo \$\endgroup\$ – nimi Dec 6 '16 at 23:14

add a comment |

Alfie Goodacre · Accepted Answer · 2016-12-14 12:05:22Z

0

C#, 71 bytes

Assuming output is required as opposed to just a return

n=>{int i=0;while(n>1){n=n%2<1?n/2:n*3+1;i++;}System.Console.Write(i);}

answered Dec 14 '16 at 12:05

Alfie Goodacre

3212 silver badges9 bronze badges

add a comment |

Pavel · Accepted Answer · 2017-01-07 03:51:10Z

0

Java (OpenJDK), 53 bytes

n->{int i=0;for(;n>1;i++)n=n%2<1?n/2:n*3+1;return i;}

Try it online!

answered Jan 7 '17 at 3:51

Pavel

8,6051 gold badge37 silver badges92 bronze badges

add a comment |

Roman Gräf · Accepted Answer · 2017-01-27 11:24:41Z

0

Java 8, 53 bytes

i->{for(;i>1;)System.out.print(i=i&1>0?i=3*i+1:i/2);}

Another solution(Java 9)

i->IntStream.iterate(i,j->j&1>0?j*3+1:j/2).takeWhile(n->true);

answered Jan 27 '17 at 11:24

Roman Gräf

2,9358 silver badges33 bronze badges

add a comment |

pizzapants184 · Accepted Answer · 2017-04-05 12:37:35Z

0

TI-Basic, 47 bytes

Prompt A
0→B
While A-1
Aremainder(A+1,2_/2+(3A+1)remainder(A,2→A
B+1→B
End
B

answered Apr 5 '17 at 12:37

pizzapants184

3,1749 silver badges16 bronze badges

add a comment |

Rohan Jhunjhunwala · Accepted Answer · 2017-05-13 12:54:36Z

S.I.L.O.S, 76 bytes

readIO
lbla
I=1-(i%2)
if I x
i=i*6+2
lblx
i/2
x+1
I=1-i
I|
if I a
printInt x

Try it online!

Somewhat naively implements the spec. It avoids a couple extra lines at the cost of performance by multiplying i by 6 and adding 2, then dividing by two when the number is odd.

betseg · Accepted Answer · 2017-07-30 12:09:48Z

0

Emojicode, 139 bytes

🐖🔢➡️🚂🍇🍮a🐕🍮i 0🔁❎😛1a🍇🍊😛1🚮a 2🍇🍮a➕1✖3a🍉🍓🍇🍮a➗a 2🍉🍮i➕1i🍉🍎i🍉

Try it online!

answered Jul 30 '17 at 12:09

betseg

8,4933 gold badges19 silver badges55 bronze badges

add a comment |

Οurous · Accepted Answer · 2018-01-09 20:07:29Z

0

Clean, 82 bytes

import StdEnv
?n=snd(until(\(e,_)=e<2)(\(e,i)=(if(isOdd e)(3*e+1)(e/2),i+1))(n,0))

Try it online!

answered Jan 9 '18 at 20:07

Οurous

7,9161 gold badge12 silver badges36 bronze badges

add a comment |

Weijun Zhou · Accepted Answer · 2018-02-21 15:44:37Z

0

Stax, 12 bytes^CP437

ÄFl,rBoU¡£&╦

14 bytes when unpacked,

1{h_3*^\_@gt%v

Run and debug online!

Adaptation of https://github.com/tomtheisen/stax/blob/master/testspecs/golf/CollatzTest.staxtest .

answered Feb 21 '18 at 15:44

Weijun Zhou

3,4167 silver badges38 bronze badges

add a comment |

Giuseppe · Accepted Answer · 2018-02-21 16:09:43Z

0

SNOBOL4 (CSNOBOL4), 96 bytes

	N =INPUT
T	X =X + 1
	N =GT(REMDR(N,2)) 3 * N + 1	:S(O)
	N =N / 2
O	OUTPUT =EQ(N,1) X	:F(T)
END

Try it online!

answered Feb 21 '18 at 16:09

Giuseppe

21.4k3 gold badges18 silver badges76 bronze badges

add a comment |

caird coinheringaahing · Accepted Answer · 2018-04-11 21:45:03Z

Add++, 50 bytes

D,f,@,dd2/i@3*1+$2%D
+?
-1
W,+1,$f>x,},+1,},-1
}
O

Try it online!

-5 bytes thanks to rubber duck golfing!

How it works

D,f,@,		; Define a function 'f' that takes one argument
		; Example argument:	[10]
	dd	; Triplicate;	STACK = [10 10 10]
	2/i	; Halve;	STACK = [10 10 5]
	@	; Reverse;	STACK = [5 10 10]
	3*1+	; (n*3)+1;	STACK = [5 10 31]
	$	; Swap;		STACK = [5 31 10]
	2%	; Parity;	STACK = [5 31 0]
	D	; Select;	STACK = [5]

+?		; Take input; 	x = 10;	y = 0;
-1		; Decrement;	x = 9;	y = 0;

W,		; While x != 0:
	+1,	;  Increment;	x = 10;	y = 0;
	$f>x,	;  Call 'f';	x = 5;	y = 0;
	},+1,	;  Increment y;	x = 5;	y = 1;
	},-1	;  Decrement x;	x = 4;	y = 1;

}		; Swap to y;	x = 0;	y = 6;
O		; Output y;

Toby Speight · Accepted Answer · 2018-05-09 15:17:45Z

dc, 30 28 bytes

?[d5*2+d2%*+2/d1<f1+]dsfx1-p

This uses the formula from Jo King's answer, slightly adapted so we dup after adding 2.

Explanation

?                             # read input
 [            d1<f  ]dsfx     # repeat until we reach 1 
  d5*2+d2%*+2/                # n → (n + (5n+2)%2 * (5n+2)) / 2
                  1+          # count iterations
                         1-p  # decrement and print result

Previous answer: 30 bytes

?[6*4+]sm[d2~1=md1!=f]dsfxz1-p

We keep all the intermediate results on the stack, then count the size of the stack. We save bytes by always doing the division by two, but if the remainder is 1, then we multiply by 6 and add 4 (3 for the remainders and 1 for the Collatz constant). The final stack count contains all the numbers we've seen; the number of operations is one less than that.

Explanation

?                               # input

[6*4+]sm                        # helper function

[d2~1=md1!=f]dsfx               # recursion

z1-p                            # print result

sundar - Reinstate Monica · Accepted Answer · 2018-06-16 15:49:33Z

0

Julia 0.6, 43 bytes

c(n,l=0)=n<2?l:n%2>0?c(3n+1,l+1):c(n/2,l+1)

Try it online!

answered Jun 16 '18 at 15:49

sundar - Reinstate Monica

5,29612 silver badges29 bronze badges

add a comment |

Collatz Conjecture (OEIS A006577)

100 Answers 100

PARI/GP, 38 bytes

Casio-Basic, 83 72 bytes

tinylisp repl, 68 bytes

QBIC, 34 33 bytes

Attache, 11 bytes

Acc!!, 127 75 bytes

With comments

Wumpus, 22 bytes

Explanation

Java (OpenJDK 8), 54 bytes

Octave, 65 bytes

Ruby, 48 bytes

PHP, 80 73 Bytes

MathGolf, 7 bytes

Explanation

MathGolf, 14 bytes (no built-ins, provided by JoKing)

Explanation

C (gcc), 43 33 bytes

Japt, 18 15 bytes

Keg -rR, 23 bytes (SBCS)

Axiom, 74 bytes

R, 57 55 bytes

Haskell, 43 Bytes

C#, 71 bytes

Java (OpenJDK), 53 bytes

Java 8, 53 bytes

Another solution(Java 9)

TI-Basic, 47 bytes

S.I.L.O.S, 76 bytes

Emojicode, 139 bytes

Clean, 82 bytes

Stax, 12 bytesCP437

SNOBOL4 (CSNOBOL4), 96 bytes

Add++, 50 bytes

How it works

dc, 30 28 bytes

Explanation

Previous answer: 30 bytes

Explanation

Julia 0.6, 43 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math or ask your own question.

Linked

Related

Hot Network Questions

Keg `-rR`, 23 bytes (SBCS)

Stax, 12 bytes^CP437