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

bc 41 chars

I guess this kind of problems is what bc was invented for:

for(n=read();n>1;){if(n%2)n=n*6+2;n/=2;n}

Test:

bc1 -q collatz.bc
21
64
32
16
8
4
2
1

Proper code:

for(n=read();n>1;){if(n%2)n=n*3+1else n/=2;print n,"\n"}

bc handles numbers with up to INT_MAX digits

Edit: The Wikipedia article mentions this conjecture has been checked for all values up to 20x2⁵⁸ (aprox. 5.76e18). This program:

c=0;for(n=2^20000+1;n>1;){if(n%2)n=n*6+2;n/=2;c+=1};n;c

tests 2^20,000+1 (aprox. 3.98e6,020) in 68 seconds, 144,404 cycles.

Answer 2

C#: 216 Characters

using C=System.Console;class P{static void Main(){var p="start:";System.Action<object> o=C.Write;o(p);ulong i;while(ulong.TryParse(C.ReadLine(),out i)){o(i);while(i > 1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}o("\n"+p);}}}

in long form:

using C = System.Console;
class P
{
    static void Main()
    {
        var p = "start:"; 
        System.Action<object> o = C.Write; 
        o(p); 
        ulong i; 
        while (ulong.TryParse(C.ReadLine(), out i))
        {
            o(i); 
            while (i > 1)
            {
                i = i % 2 == 0 ? i / 2 : i * 3 + 1; 
                o(" -> " + i);
            } 
            o("\n" + p);
        }
    }
}

New Version, accepts one number as input provided through the command line, no input validation. 173 154 characters.

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;var i=ulong.Parse(a[0]);o(i);while(i>1){i=i%2==0?i/2:i*3+1;o(" -> "+i);}}}

in long form:

using System;
class P
{
    static void Main(string[]a)
    {
        Action<object>o=Console.Write;
        var i=ulong.Parse(a[0]);
        o(i);
        while(i>1)
        {
            i=i%2==0?i/2:i*3+1;
            o(" -> "+i);
        }
    }
}

I am able to shave a few characters by ripping off the idea in this answer to use a for loop rather than a while. 150 characters.

using System;class P{static void Main(string[]a){Action<object>o=Console.Write;for(var i=ulong.Parse(a[0]);i>1;i=i%2==0?i/2:i*3+1)o(i+" -> ");o(1);}}

Answer 3

Python - 95 64 51 46 char

Obviously does not produce a stack overflow.

n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n

Answer 4

x86 assembly, 1337 characters

;
; To assemble and link this program, just run:
;
; >> $ nasm -f elf collatz.asm && gcc -o collatz collatz.o
;
; You can then enjoy its output by passing a number to it on the command line:
;
; >> $ ./collatz 123
; >> 123 --> 370 --> 185 --> 556 --> 278 --> 139 --> 418 --> 209 --> 628 --> 314
; >> --> 157 --> 472 --> 236 --> 118 --> 59 --> 178 --> 89 --> 268 --> 134 --> 67
; >> --> 202 --> 101 --> 304 --> 152 --> 76 --> 38 --> 19 --> 58 --> 29 --> 88
; >> --> 44 --> 22 --> 11 --> 34 --> 17 --> 52 --> 26 --> 13 --> 40 --> 20 --> 10
; >> --> 5 --> 16 --> 8 --> 4 --> 2 --> 1
; 
; There's even some error checking involved:
; >> $ ./collatz
; >> Usage: ./collatz NUMBER
;
section .text
global main
extern printf
extern atoi

main:

  cmp dword [esp+0x04], 2
  jne .usage

  mov ebx, [esp+0x08]
  push dword [ebx+0x04]
  call atoi
  add esp, 4

  cmp eax, 0
  je .usage

  mov ebx, eax
  push eax
  push msg

.loop:
  mov [esp+0x04], ebx
  call printf

  test ebx, 0x01
  jz .even

.odd:
  lea ebx, [1+ebx*2+ebx]
  jmp .loop

.even:

  shr ebx, 1
  cmp ebx, 1
  jne .loop

  push ebx
  push end
  call printf

  add esp, 16
  xor eax, eax
  ret

.usage:
  mov ebx, [esp+0x08]
  push dword [ebx+0x00]
  push usage
  call printf
  add esp, 8
  mov eax, 1
  ret

msg db "%d --> ", 0
end db "%d", 10, 0
usage db "Usage: %s NUMBER", 10, 0

Answer 5

LOLCODE: 406 CHARAKTERZ

HAI
BTW COLLATZ SOUNDZ JUS LULZ

CAN HAS STDIO?

I HAS A NUMBAR
BTW, I WANTS UR NUMBAR
GIMMEH NUMBAR

VISIBLE NUMBAR

IM IN YR SEQUENZ
  MOD OF NUMBAR AN 2
  BOTH SAEM IT AN 0, O RLY?
    YA RLY, NUMBAR R QUOSHUNT OF NUMBAR AN 2
    NO WAI, NUMBAR R SUM OF PRODUKT OF NUMBAR AN 3 AN 1
  OIC
  VISIBLE NUMBAR
  DIFFRINT 2 AN SMALLR OF 2 AN NUMBAR, O RLY?
    YA RLY, GTFO
  OIC
IM OUTTA YR SEQUENZ

KTHXBYE

TESTD UNDR JUSTIN J. MEZA'S INTERPRETR. KTHXBYE!

Answer 6

not the shortest, but an elegant clojure solution

(defn collatz [n]
 (print n "")
 (if (> n 1)
  (recur
   (if (odd? n)
    (inc (* 3 n))
    (/ n 2)))))