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

100 Answers 100

1 2 3
4
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\$

Python 2, 48 bytes

f=lambda n,s=0:s*(n<2)or f((n/2,3*n+1)[n%2],s+1)

Try it online!

Aaah, recursion.

# s*0 or s*1.
s*(n<2)

# while n>1, this will evaluate to 0 or f(n,s+1).
# Since positive integers are Truthy, this will return f().
# when n<2, this will return s without evaluating f().
s*(n<2)or f(...)
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

Pushy, 24 bytes

Zvt$h2C3*h}2/}2%zFhFt;F#

Try it online!

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

JavaScript, 35 bytes

f=(n,c)=>n<2?c:f(n%2?n*3+1:n/2,-~c)

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\$
  • 1
    \$\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\$ – Ad Hoc Garf Hunter Dec 12 '19 at 14:08
0
\$\begingroup\$

Wren, 68 bytes

Fn.new{|n|
var c=0
while(n>1){
n=n%2==0?n/2:n*3+1
c=c+1
}
return c
}

Try it online!

Explanation

Fn.new{|n| // New anonymous function with param n
var c=0    // Declare a variable c as 0
while(n>1){ // While n is larger than 1:
n=n%2==0?          // If n is divisible by 2:
         n/2:      // Halve n
             n*3+1 // Otherwise, triple n & increment.
c=c+1              // Increment the counter
}                  // This is here due to Wrens bad brace-handling system
return c           // Return the value of the counter
}
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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.

Original CollatzGameCleaned-up CollatzGame

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

Kotlin, 63 bytes

{var n=it
var c=0
while(n>1){n=if(n%2==0)n/2 else n*3+1
c++}
c}

Try it online!

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