Code Golf: Collatz Conjecture
- by Earlz
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.
