Code Golf: Collatz Conjecture

Question

Inspired by http://xkcd.com/710/ here is a code golf for it.

The Challenge

Given a positive integer greater than 0, print out the hailstone sequence for that number.

The Hailstone Sequence

See Wikipedia for more detail..

• If the number is even, divide it by two.
• If the number is odd, triple it and add one.

Repeat this with the number produced until it reaches 1. (if it continues after 1, it will go in an infinite loop of 1 -> 4 -> 2 -> 1...)

Sometimes code is the best way to explain, so here is some from Wikipedia

function collatz(n)
  show n
  if n > 1
    if n is odd
      call collatz(3n + 1)
    else
      call collatz(n / 2)

This code works, but I am adding on an extra challenge. The program must not be vulnerable to stack overflows. So it must either use iteration or tail recursion.

Also, bonus points for if it can calculate big numbers and the language does not already have it implemented. (or if you reimplement big number support using fixed-length integers)

Test case

Number: 21
Results: 21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

Also, the code golf must include full user input and output.

Answer 1

Common Lisp, 141 characters:

(defun c ()
  (format t"Number: ")
  (loop for n = (read) then (if(oddp n)(+ 1 n n n)(/ n 2))
     until (= n 1)
     do (format t"~d -> "n))
  (format t"1~%"))

Test run:

Number: 171
171 -> 514 -> 257 -> 772 -> 386 -> 193 -> 580 -> 290 -> 145 -> 436 ->
218 -> 109 -> 328 -> 164 -> 82 -> 41 -> 124 -> 62 -> 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 

Answer 2

The program frm Jerry Coffin has integer over flow, try this one:

#include <iostream>

int main(unsigned long long i)
{
    int j = 0;
    for(  std::cin>>i; i>1; i = i&1? i*3+1:i/2, ++j)
        std::cout<<i<<" -> ";

    std::cout<<"\n"<<j << " iterations\n";
}

tested with

The number less than 100 million with the longest total stopping time is 63,728,127, with 949 steps.

The number less than 1 billion with the longest total stopping time is 670,617,279, with 986 steps.

Answer 3

ruby, 43, possibly meeting the I/O requirement

---

Run with ruby -n hail

n=$_.to_i
(n=n%2>0?n*3+1: n/2
p n)while n>1

Answer 4

C : 64 chars

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

With big integer support: 431 (necessary) chars

#include <stdlib.h>
#define B (w>=m?d=realloc(d,m=m+m):0)
#define S(a,b)t=a,a=b,b=t
main(m,w,i,t){char*d=malloc(m=9);for(w=0;(i=getchar()+2)/10==5;)
B,d[w++]=i%10;for(i=0;i<w/2;i++)S(d[i],d[w-i-1]);for(;;w++){
while(w&&!d[w-1])w--;for(i=w+1;i--;)putchar(i?d[i-1]+48:10);if(
w==1&&*d==1)break;if(*d&1){for(i=w;i--;)d[i]*=3;*d+=1;}else{
for(i=w;i-->1;)d[i-1]+=d[i]%2*10,d[i]/=2;*d/=2;}B,d[w]=0;for(i=0
;i<w;i++)d[i+1]+=d[i]/10,d[i]%=10;}}

Note: Do not remove #include <stdlib.h> without at least prototyping malloc/realloc, as doing so will not be safe on 64-bit platforms (64-bit void* will be converted to 32-bit int).

This one hasn't been tested vigorously yet. It could use some shortening as well.

---

Previous versions:

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

(removed 12 chars because no one follows the output format... :| )

Answer 5

TI-BASIC

Not the shortest, but a novel approach. Certain to slow down considerably with large sequences, but it shouldn't overflow.

PROGRAM:COLLATZ
:ClrHome
:Input X
:Lbl 1
:While X≠1
:If X/2=int(X/2)
:Then
:Disp X/2→X
:Else
:Disp X*3+1→X
:End
:Goto 1
:End

Answer 6

Ruby, 43 characters

bignum supported, with stack overflow susceptibility:

def c(n)p n;n%2>0?c(3*n+1):c(n/2)if n>1 end

...and 50 characters, bignum supported, without stack overflow:

def d(n)while n>1 do p n;n=n%2>0?3*n+1:n/2 end end

Kudos to Jordan. I didn't know about 'p' as a replacement for puts.