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

Another assembler version. This one is not limited to 32 bit numbers, it can handle numbers up to 10⁶⁵⁵³⁴ although the ".com" format MS-DOS uses is limited to 80 digit numbers. Written for A86 assembler and requires a Win-XP DOS box to run. Assembles to 180 bytes:

    mov ax,cs
    mov si,82h
    add ah,10h
    mov es,ax
    mov bh,0
    mov bl,byte ptr [80h]
    cmp bl,1
    jbe ret
    dec bl
    mov cx,bx
    dec bl
    xor di,di
 p1:lodsb
    sub al,'0'
    cmp al,10
    jae ret
    stosb
    loop p1
    xor bp,bp
    push es
    pop ds
 p2:cmp byte ptr ds:[bp],0
    jne p3
    inc bp
    jmp p2
    ret
 p3:lea si,[bp-1]
    cld
 p4:inc si
    mov dl,[si]
    add dl,'0'
    mov ah,2
    int 21h
    cmp si,bx
    jne p4
    cmp bx,bp
    jne p5
    cmp byte ptr [bx],1
    je ret
 p5:mov dl,'-'
    mov ah,2
    int 21h
    mov dl,'>'
    int 21h
    test byte ptr [bx],1
    jz p10
    ;odd
    mov si,bx
    mov di,si
    mov dx,3
    dec bp
    std
 p6:lodsb
    mul dl
    add al,dh
    aam
    mov dh,ah
    stosb
    cmp si,bp
    jnz p6
    or dh,dh
    jz p7
    mov al,dh
    stosb
    dec bp
 p7:mov si,bx
    mov di,si
 p8:lodsb
    inc al
    xor ah,ah
    aaa
    stosb
    or ah,ah
    jz p9
    cmp si,bp
    jne p8
    mov al,1
    stosb
    jmp p2
 p9:inc bp
    jmp p2
    p10:mov si,bp
    mov di,bp
    xor ax,ax
p11:lodsb
    test ah,1
    jz p12
    add al,10
p12:mov ah,al
    shr al,1
    cmp di,bx
    stosb
    jne p11
    jmp p2

Answer 2

Ruby, 50 chars, no stack overflow

Basically a direct rip of makapuf's Python solution:

def c(n)while n>1;n=n.odd?? n*3+1: n/2;p n end end

Ruby, 45 chars, will overflow

Basically a direct rip of the code provided in the question:

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

Answer 3

Befunge

&>:.:1-|
  >3*^ @
  |%2: <
 v>2/>+

Answer 4

nroff¹

Run with nroff -U hail.g

.warn
.pl 1
.pso (printf "Enter a number: " 1>&2); read x; echo .nr x $x
.while \nx>1 \{\
.  ie \nx%2 .nr x \nx*3+1
.  el .nr x \nx/2
\nx
.\}

---

^{1. groff version}

Answer 5

Haskell, 62 chars 63 76 83, 86, 97, 137

c 1=[1]
c n=n:c(div(n`mod`2*(5*n+2)+n)2)
main=readLn>>=print.c

User input, printed output, uses constant memory and stack, works with arbitrarily big integers.

A sample run of this code, given an 80 digit number of all '1's (!) as input, is pretty fun to look at.

---

Original, function only version:

Haskell 51 chars

f n=n:[[],f([n`div`2,3*n+1]!!(n`mod`2))]!!(1`mod`n)

Who the @&^# needs conditionals, anyway?

(edit: I was being "clever" and used fix. Without it, the code dropped to 54 chars. edit2: dropped to 51 by factoring out f())

Answer 6

dc - 24 chars 25 28

dc is a good tool for this sequence:

?[d5*2+d2%*+2/pd1<L]dsLx

dc -f collatz.dc
21
64
32
16
8
4
2
1

Also 24 chars using the formula from the Golfscript entry:

?[3*1+d2%5*1+/pd1<L]dsLx

57 chars to meet the specs:

[Number: ]n?[Results: ]ndn[d5*2+d2%*+2/[ -> ]ndnd1<L]dsLx

dc -f collatz-spec.dc
Number: 3
Results: 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1