69
\$\begingroup\$

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

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
\$\endgroup\$

106 Answers 106

1 2 3
4
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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);
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Emojicode, 139 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Stax, 12 bytesCP437

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

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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;
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Ahead, 38 bytes

Il&+1t~j+1*3\~/2<~<
>:1)k~tO@~:k\:  nl

Try it online!

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Ruby, 77 72 bytes

b=0;a=gets.to_i;loop{if a==1;p b;exit;end;a.odd?? (a*=3;a+=1):a/=2;b+=1}

Definitely not the shortest, but not the most unreadable or hard to follow either. Try it online!

a.odd?? (a*=3;a+=1): uses the ternary operator, which is a short form of if/then/else. It looks like boolean ? instruction : instruction, with the first instruction being if the boolean is true, and the second being if it isn't. Therefore trailing question mark and colon.

*= and /= are the multiplication and division versions of += in Ruby.

Ungolfed version:

counter = 0
input = gets.to_i
loop do
  if input = 1
    print counter
    exit
  end
  if input.odd?
    input *= 3
    input += 1
  else
    input /= 2
  end
  counter += 1
end
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

SmileBASIC, 54 bytes

INPUT N
WHILE N-1D=1AND N
C=C+1N=N*3*D+D+N/2*!D
WEND?C
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

Here is the one line code in python (a long one though)

num = int(input()); while num > 0 : print(num); num = int(num / 2) if num % 2 == 0 else 3 * num + 1 if num > 1 else 0
| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Wecome to the site! Answers are scored in number of characters rather than number of lines. This leaves you a few ways of optimization. You can use a shorter variable name, you can remove unnecessary spaces. \$\endgroup\$ – Wheat Wizard Dec 12 '19 at 14:08
0
\$\begingroup\$

Haskell, 47 bytes

c n|n==1=0|even n=1+c(div n 2)|odd n=1+c(3*n-1)

Ungolfed:

c n
    | n == 1 = 0
    | even n = 1 + c (div n 2)
    | odd n  = 1 + c (3*n-1)

A recursive function that returns the number of times it's been run, excluding when n==1.

| improve this answer | |
\$\endgroup\$
1 2 3
4

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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