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.

Chairman

I must have dedicated 500 hours in college trying to prove this damned thing. – Candlemaker

Also see projecteuler.net/index.php?section=problems&id=14 – Fogged

must not be vulnerable to stack overflows : You should not have posted it here then! ;) – Congener

My friends stopped calling me, does that mean I solved the problem? – Biddable

You're on SO, but once had friends? ... what was that like? – Greer

Nice and simple golf. Maybe a bit too simple. – Fairman

According to the wikipedia article, the Collatz conjecture is the statement that "this sequence terminates (reaches 1) for all natural numbers". Just to get the terminology right. – Brentonbrentt

@Martinho, then edit my question.. I found the requirements hard to phrase as readable English.. – Chairman

The assembler answer is cool, but it's a bit anti-code-golf to select the longest answer! – Carboxylase

FWIW (~0), of the inputs 1..1000, number 871 requires the greatest number of steps to reach the end - at 178 steps. Extending the range to 100,000 took just under an hour, and reveals that 77031 requires 350 steps to terminate. The biggest number processed is 1570824736 which itself requires 160 steps to terminate. – Otter

Is output to be formatted as shown here, on one line with " -> "? Or is one number per line acceptable (as many entries have)? – Hygrometry

@Hygrometry It doesn't matter, as long as you can clearly see each number – Chairman

Answer 1

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

Biddable

x86 asm and 1337 chars. I weep with joy. – Umlaut

I like the (ab)use of lea for 3n+1. – Valencia

how do i complie in linux cant wait to try it – Lapham

Answer 2

Befunge

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

Alfred

You should read this in 2D. <>^v are arrows that change direction the "program counter" wanders. | and _ are conditionals that go up/down or left/right depending on whether the value on stack is true or false. The whole "code arena" wraps around through top-bottom and left-right. – Tomboy

And only 35 chars including whitespace! Not bad at all! – Churning

Are you sure it's not Perl? – Encircle

Answer 3

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!

Capers

Answer 4

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

Ecthyma

You might want to specify Python 2.x. IIRC, Python 3.x input doesn't do an eval. – Mutazilite

This doesn't fulfil the requirements - it doesn't print the first number – Angeliaangelic

why is this accepted? it's not the shortest one and it doesn't print the first number – Woodruff

I guess input() echoes the characters you type, so this does print the first number :) – Devastation

@Danko: On a different line though. – Pentlandite

You can print the first number for a cost of only 2 bytes by using n=input()*2 – Carboxylase

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())

Hygrometry

After doing my Miranda post (which is basically just older Haskell), at least in Miranda you can cut that down by using just one exclamation mark each - f n=n:[[],[f(n div 2),f(3*n+1)]!(n mod 2)]!(1 mod n) - Works :) – Schaal

Oh, yes, you're missing input and output. – Brentonbrentt

@Martinho: Me too, but thanks to lazy evaluation, the tables are even much cooler than in other languages. – Bowman

What about (%)=mod;f n=n:[[],f([ndiv2,3*n+1]!!(n%2))]!!(1%n)? Has same length but looks much cooler :P – Bowman

An interesting approach is f=(++[1]).takeWhile(>1).iterate(\n->[ndiv2,3*n+1]!!(nmod2)), but unfortunately somewhat longer due to the verbose function names ;) We definitely need some shortcuts ... f=(++[1]).w(>1).i(\n->[n#2,3*n+1]!!(n%2)) – Bowman

Using jleedev's idea: c 1=[1];c n=n:(c$div(nmod2*(5*n+2)+n)2) - 41 characters, this uses the fact that this is k*(3n+1)+(1-k)*n/2 where k=n mod 2 – Regolith

I added a new Haskell answer based on this code that does input/output. Since that increases the size to 97 characters, I didn't just edit this one. Would folks prefer that I edit my full answer into this one (preserving the votes, but upping the size) and delete my 2nd Haskell entry? Or should we keep them separate? – Hygrometry

I deleted my other entry, and moved my code here, and incorporated yet more of the ideas from these comments. Increased to 76 characters, but does input and output. – Hygrometry

Improved function definition and I/O character counts, for a total of 63 keystrokes. – Watanabe

Last edit lost a prior savings in the recursive call to c. I put it back and now we're down to 62! – Hygrometry

Answer 6

Perl

I decided to be a little anticompetitive, and show how you would normally code such problem in Perl.
_{There is also a 46 (total) char code-golf entry at the end.}

These first three examples all start out with this header.

#! /usr/bin/env perl
use Modern::Perl;
# which is the same as these three lines:
# use 5.10.0;
# use strict;
# use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}

• Simple recursive version

  use Sub::Call::Recur;
  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;
    die 'Integer values only' unless $n == int $n;
    say $n;
    given( $n ){
      when( 1 ){}
      when( $_ % 2 != 0 ){ # odd
        recur( 3 * $n + 1 );
      }
      default{ # even
        recur( $n / 2 );
      }
    }
  }
  

• Simple iterative version

  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;
    die 'Integer values only' unless $n == int $n;
    say $n;
    while( $n > 1 ){
      if( $n % 2 ){ # odd
        $n = 3 * $n + 1;
      } else { #even
        $n = $n / 2;
      }
      say $n;
    }
  }
  

• Optimized iterative version

  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;
    die 'Integer values only' unless $n == int $n;
    #
    state @next;
    $next[1] //= 0; # sets $next[1] to 0 if it is undefined
    #
    # fill out @next until we get to a value we've already worked on
    until( defined $next[$n] ){
      say $n;
      #
      if( $n % 2 ){ # odd
        $next[$n] = 3 * $n + 1;
      } else { # even
        $next[$n] = $n / 2;
      }
      #
      $n = $next[$n];
    }
    say $n;
    # finish running until we get to 1
    say $n while $n = $next[$n];
  }
  

---

Now I'm going to show how you would do that last example with a version of Perl prior to v5.10.0

#! /usr/bin/env perl
use strict;
use warnings;

while( <> ){
  chomp;
  last unless $_;
  Collatz( $_ );
}
{
  my @next = (0,0); # essentially the same as a state variable
  sub Collatz{
    my( $n ) = @_;
    $n += 0; # ensure that it is numeric
    die 'invalid value' unless $n > 0;

    # fill out @next until we get to a value we've already worked on
    until( $n == 1 or defined $next[$n] ){
      print $n, "\n";

      if( $n % 2 ){ # odd
        $next[$n] = 3 * $n + 1;
      } else { # even
        $next[$n] = $n / 2;
      }
      $n = $next[$n];
    }
    print $n, "\n";

    # finish running until we get to 1
    print $n, "\n" while $n = $next[$n];
  }
}

---

Benchmark

First off the IO is always going to be the slow part. So if you actually benchmarked them as-is you should get about the same speed out of each one.

To test these then, I opened a file handle to /dev/null ($null), and edited every say $n to instead read say {$null} $n. This is to reduce the dependence on IO.

#! /usr/bin/env perl
use Modern::Perl;
use autodie;

open our $null, '>', '/dev/null';

use Benchmark qw':all';

cmpthese( -10,
{
  Recursive => sub{ Collatz_r( 31 ) },
  Iterative => sub{ Collatz_i( 31 ) },
  Optimized => sub{ Collatz_o( 31 ) },
});

sub Collatz_r{
  ...
  say {$null} $n;
  ...
}
sub Collatz_i{
  ...
  say {$null} $n;
  ...
}
sub Collatz_o{
  ...
  say {$null} $n;
  ...
}

After having run it 10 times, here is a representative sample output:

            Rate Recursive Iterative Optimized
Recursive 1715/s        --      -27%      -46%
Iterative 2336/s       36%        --      -27%
Optimized 3187/s       86%       36%        --

---

Finally, a real code-golf entry:

perl -nlE'say;say$_=$_%2?3*$_+1:$_/2while$_>1'

46 chars total

If you don't need to print the starting value, you could remove 5 more characters.

perl -nE'say$_=$_%2?3*$_+1:$_/2while$_>1'

41 chars total
_{31 chars for the actual code portion, but the code won't work without the -n switch. So I include the entire example in my count.}

Coact

Your optimized version, isn't. – Subfamily

@Subfamily These examples are very IO dependent. Having tested them multiple times, the optimized version always maintains a significant lead. – Coact

@Brad, when you run Collatz on one number then the optimization is a pessimization since no number should appear more than once (unless the conjecture is wrong). The reason you're seeing an improvement is that you're running many numbers (as in the Euler problem), in fact I wrote a blog post about this recently lanzkron.wordpress.com/2010/01/18/… – Subfamily

@Subfamily that's the optimization I was talking about. Also, in Perl $i + 1 is always addition (response to the blog entry). Also using Sub::Call::Recur is also an optimization. Otherwise I would use @_=$n;goto &Collatz. (It is 10-20% slower if you change state @next to my @next – Coact

I believe perl golf stroke counting standards do not count the mandatory strokes for invoking the interpreter nor the quotes, but do count one for each flag beside E. Using those rules, your last entries count respectively 37 chars and 32 chars. – Brentonbrentt

@Brad, regarding $i + 1, true, I mixed JavaScript up with Perl on this instance (forgot the . operator). – Subfamily

why didn't you just redirect stdout to /dev/null and print the times to stderr? i.e. perl foo > /dev/null, instead of changing your code. – Rancor

$_=<>; would make it directly comparable to the winning Python answer (Perl golf being a somewhat esoteric sport), and still several characters smaller. – Encircle

Answer 7

Golfscript : 20 chars

  ~{(}{3*).1&5*)/}/1+`
# 
# Usage: echo 21 | ruby golfscript.rb collatz.gs

This is equivalent to

stack<int> s;
s.push(21);
while (s.top() - 1) {
  int x = s.top();
  int numerator = x*3+1;
  int denominator = (numerator&1) * 5 + 1;
  s.push(numerator/denominator);
}
s.push(1);
return s;

Woolpack

"must include full user input and output" – Gunnar

@FX, replacing the 21 with ~ will cause the program to use a number from stdin – Carboxylase

@gnibbler: Is Golfscript.rb updated? I got (eval):1:in initialize': undefined method leftparen' for nil:NilClass (NoMethodError) when replacing 21 with ~. – Pentlandite

@KennyTM, Sadly GolfScript can't read stdin interactively you have to pipe something into stdin, like echo 21 | ruby golfscript.rb collatz.gs – Carboxylase

Answer 8

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.

Equivoque

Change 'n!=1' to `n>1' for 54 chars. – Personify

Here's a command line for generating random arbitrary-length numbers for this entry (10000 digits in this case): cat /dev/urandom | tr -dc '0-9' | head -c 10000 | bc collatz-conjecture.bc – Tracay

@Tracay - I had to test it :), it took 3 minutes and 12 seconds to process the 10,000 digits number. I saved the output to a file, it's about 1.2gb long, but yes it did finish correctly in 1. Point for bc – Poling

Answer 9

Perl : 31 chars

perl -nE 'say$_=$_%2?$_*3+1:$_/2while$_>1'
#         123456789 123456789 123456789 1234567

Edited to remove 2 unnecessary spaces.

Edited to remove 1 unnecessary space.

Jassy

You can remove two unnecessary spaces (after say and after while) – Jarrett

Try perl -E 'say$_=10;say$_=$_%2?$_*3+1:$_/2 while$_>1' – Jarrett

I figured that the user would be aware of the starting number of the sequence ;-). – Multistage

Sometimes when I come across base64 encoded text, I sometimes mistake it for Perl source code. – Biddable

@Martin:I can't imagine how you'd do that. Base64 is much more readable. – Personify

Won't the extra -n flag count as a stroke? – Brentonbrentt

37 characters with "$_=<>;", which means it's not a command-line but a full program; still safely shorter than the winning Python answer. – Encircle

Answer 10

MS Excel, 35 chars

=IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1)

Taken straight from Wikipedia:

In cell A1, place the starting number.
In cell A2 enter this formula =IF(A1/2=ROUND(A1/2,0),A1/2,A1*3+1) 
Drag and copy the formula down until 4, 2, 1

It only took copy/pasting the formula 111 times to get the result for a starting number of 1000. ;)

Incertitude

I guess it's too late for me to point out that this is what the fill handle is for, huh? ehow.com/how_2284668_use-fill-handle-microsoft-excel.html :) – Hubie

That's a pretty handy feature that I didn't even know existed. I just copied the first cell and then highlight all of the other cells and pasted once. – Incertitude

I learned about area-paste roughly ten years after i discovered the fill handle. figures. – Propinquity

Answer 11

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

Woolpack

Answer 12

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

Trammel

Answer 13

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

Equivoque

Answer 14

Scheme: 72

(define(c n)(if(= n 1)`(1)(cons n(if(odd? n)(c(+(* n 3)1))(c(/ n 2))))))

This uses recursion, but the calls are tail-recursive so I think they'll be optimized to iteration. In some quick testing, I haven't been able to find a number for which the stack overflows anyway. Just for example:

(c 9876543219999999999000011234567898888777766665555444433332222 7777777777777777777777777777777798797657657651234143375987342987 5398709812374982529830983743297432985230985739287023987532098579 058095873098753098370938753987)

...runs just fine. [that's all one number -- I've just broken it to fit on screen.]

Personify

Answer 15

Mathematica, 45 50 chars

c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&

Weeper

I counted 58 chars. And you can replace OddQ[#] with OddQ@# to save 1 char. – Pentlandite

50 characters: c[n_]:=NestWhileList[If[OddQ@#,3#+1,#/2]&,n,#>1&] – Spiros

Answer 16

Python 45 Char

Shaved a char off of makapuf's answer.

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

Orgasm

very clever use of the ~ operator. I had to look it up to see what it did (I try to avoid binary operators in Python, so I', not very familiar with them). – Zabrina

Answer 17

import java.math.BigInteger;
public class SortaJava {

    static final BigInteger THREE = new BigInteger("3");
    static final BigInteger TWO = new BigInteger("2");

    interface BiFunc<R, A, B> {
      R call(A a, B b);
    }

    interface Cons<A, B> {
      <R> R apply(BiFunc<R, A, B> func);
    }

    static class Collatz implements Cons<BigInteger, Collatz> {
      BigInteger value;
      public Collatz(BigInteger value) { this.value = value; }
      public <R> R apply(BiFunc<R, BigInteger, Collatz> func) {
        if(BigInteger.ONE.equals(value))
          return func.call(value, null);
        if(value.testBit(0))
          return func.call(value, new Collatz((value.multiply(THREE)).add(BigInteger.ONE)));
        return func.call(value, new Collatz(value.divide(TWO)));
      }
    }

    static class PrintAReturnB<A, B> implements BiFunc<B, A, B> {
      boolean first = true;
      public B call(A a, B b) {
        if(first)
          first = false;
        else
          System.out.print(" -> ");
        System.out.print(a);
        return b;
      }
    }

    public static void main(String[] args) {
      BiFunc<Collatz, BigInteger, Collatz> printer = new PrintAReturnB<BigInteger, Collatz>();
      Collatz collatz = new Collatz(new BigInteger(args[0]));
      while(collatz != null)
        collatz = collatz.apply(printer);
    }
}

Valencia

Java: the language where you have to use BigIntegers just to count the number of characters in the code of the solution. – Ursal

@Jared I totally agree that Java is verbose. You have to admit that the solution presented a) meets the requirements b) is way longer than really necessary and c) plays with the java type system in a pleasing way – Valencia

Answer 18

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

Hubie

What version of Ruby is that? I get n.odd?? not defined. Also, that is vulnerable to stack overflows with large numbers. – Chairman

That's interesting. I have 1.8.7. Adding a space between the question marks should fix that. And you're right about the stack overflow. I'll edit my answer to make a note of that. – Hubie

You can save four characters with p n=[n/2,n*3+1][n%2] – Isidora

Answer 19

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

Ellipsis

Answer 20

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}

Gill

Scary! Still, at least the output should be formatted nicely. – Otter

Hey, run it as groff -U hail.g and you get PostScript! :-) – Gill

Answer 21

Scala + Scalaz

import scalaz._
import Scalaz._
val collatz = 
   (_:Int).iterate[Stream](a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) // This line: 61 chars

And in action:

scala> collatz(7).toList
res15: List[Int] = List(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2)

Scala 2.8

val collatz = 
   Stream.iterate(_:Int)(a=>Seq(a/2,3*a+1)(a%2)).takeWhile(1<) :+ 1

This also includes the trailing 1.

scala> collatz(7)
res12: scala.collection.immutable.Stream[Int] = Stream(7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1)

With the following implicit

implicit def intToEven(i:Int) = new {
  def ~(even: Int=>Int, odd: Int=>Int) = { 
    if (i%2==0) { even(i) } else { odd(i) }
  }
}

this can be shortened to

val collatz = Stream.iterate(_:Int)(_~(_/2,3*_+1)).takeWhile(1<) :+ 1

Edit - 58 characters (including input and output, but not including initial number)

var n=readInt;while(n>1){n=Seq(n/2,n*3+1)(n%2);println(n)}

Could be reduced by 2 if you don't need newlines...

Angeliaangelic

Answer 22

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

Depolymerize

Answer 23

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);}}

Veinule

You should mention your code accepts more than one input. Or take that away and shave off a few chars. – Brentonbrentt

You could shorten Action<object> and possibly more to dynamic in C#4. – Fairman

@Dykam: Just checked it: fails with "error CS0428: Cannot convert method group 'Write' to non-delegate type 'dynamic'. Did you intend to invoke the method?". – Brentonbrentt

Oh, ofcourse... implicit converting to delegates... requires denoting the delegate. Bummer... – Fairman

Answer 24

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.

Peal

Answer 25

Haskell : 50

c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)

Alfred

Using jkff's idea: c 1=[1];c n=n:(c$[ndiv2,3*n+1]!!(nmod2)), 44 chars – Regolith

Answer 26

JavaScript - 68 chars

Unlike the other JS (and most other languages) this one actually adheres to the -> in the output.

for(s='',c=' -> ',i=readline();i>1;i=i%2?i*3+1:i/2)s+=i+c
print(s+1)

If we avoid that, this is a 53 char alternative, prints one number per line:

for(p=print,i=readline(),p(i);i>1;)p(i=i%2?i*3+1:i/2)

Meant to run with SpiderMonkey:

echo 21 | js thisfile.js

21 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Tunnell

Answer 27

Windows cmd - 68 chars

@set/pd=
:l 
@set/ad=(d+d%%2*(d*5+2))/2&echo %d%&if %d% NEQ 1 goto:l

Equivoque

Answer 28

C# : 659 chars with BigInteger support

using System.Linq;using C=System.Console;class Program{static void Main(){var v=C.ReadLine();C.Write(v);while(v!="1"){C.Write("->");if(v[v.Length-1]%2==0){v=v.Aggregate(new{s="",o=0},(r,c)=>new{s=r.s+(char)((c-48)/2+r.o+48),o=(c%2)*5}).s.TrimStart('0');}else{var q=v.Reverse().Aggregate(new{s="",o=0},(r, c)=>new{s=(char)((c-48)*3+r.o+(c*3+r.o>153?c*3+r.o>163?28:38:48))+r.s,o=c*3+r.o>153?c*3+r.o>163?2:1:0});var t=(q.o+q.s).TrimStart('0').Reverse();var x=t.First();q=t.Skip(1).Aggregate(new{s=x>56?(x-57).ToString():(x-47).ToString(),o=x>56?1:0},(r,c)=>new{s=(char)(c-48+r.o+(c+r.o>57?38:48))+r.s,o=c+r.o>57?1:0});v=(q.o+q.s).TrimStart('0');}C.Write(v);}}}

Ungolfed

using System.Linq;
using C = System.Console;
class Program
{
    static void Main()
    {
        var v = C.ReadLine();
        C.Write(v);
        while (v != "1")
        {
            C.Write("->");
            if (v[v.Length - 1] % 2 == 0)
            {
                v = v
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = r.s + (char)((c - 48) / 2 + r.o + 48), o = (c % 2) * 5 })
                    .s.TrimStart('0');
            }
            else
            {
                var q = v
                    .Reverse()
                    .Aggregate(
                        new { s = "", o = 0 }, 
                        (r, c) => new { s = (char)((c - 48) * 3 + r.o + (c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 28 : 38 : 48)) + r.s, o = c * 3 + r.o > 153 ? c * 3 + r.o > 163 ? 2 : 1 : 0 });
                var t = (q.o + q.s)
                    .TrimStart('0')
                    .Reverse();
                var x = t.First();
                q = t
                    .Skip(1)
                    .Aggregate(
                        new { s = x > 56 ? (x - 57).ToString() : (x - 47).ToString(), o = x > 56 ? 1 : 0 }, 
                        (r, c) => new { s = (char)(c - 48 + r.o + (c + r.o > 57 ? 38 : 48)) + r.s, o = c + r.o > 57 ? 1 : 0 });
                v = (q.o + q.s)
                    .TrimStart('0');
            }
            C.Write(v);
        }
    }
}

Diego

Answer 29

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

Gill

Answer 30

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.

Rebato

Any finite integer types cannot prevent integer overflow. Not even unsigned long long. – Pentlandite

Answer 31

PHP

function Collatz($n)
{
        $i = 0;
    while($n>1)
    {
        if($n % 2)
        {
            $n = (3*$n) + 1;
            $i++;
            echo "step $i:  $n <br/>";
        }

        else 
        {
            $n = $n/2;
            $i++;
            echo "step $i:  $n <br/>";
        }
    }

}

Rondeau

You're duplicating the $i++; and echo "step ..."; twice. Move those after the else block to save some characters. – Photo

Answer 32

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 

Schumann

Almost. There's no header for the 2nd line. I could've shaved 3 chars off ignoring the arrow, another 3-4 eliding unnecessary spaces, but I'm happy with a multiple of 3. – Schumann

Answer 33

F#, 90 characters

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))

> c 21;;
val it : seq<int> = seq [21; 64; 32; 16; ...]

Or if you're not using F# interactive to display the result, 102 characters:

let c=Seq.unfold(function|n when n<=1->None|n when n%2=0->Some(n,n/2)|n->Some(n,(3*n)+1))>>printf"%A"

Inside

Answer 34

Since there seems to be a bit of interest with the LOLCODE solution, I thought I'd compare implementations of the two solution approaches (iterative and tail-recursive) in this language.

First, there is the iterative solution at 203 characters:

HAI 1.2
    I HAS A n
    GIMMEH n
    IM IN YR l
        VISIBLE n
        BOTH SAEM 1 BIGGR OF 1 n
        O RLY?
            YA RLY
                GTFO
        OIC
        MOD OF n 2
        WTF?
            OMG 0
                n R QUOSHUNT OF n 2
                GTFO
            OMG 1
                n R SUM OF 1 PRODUKT OF 3 n
        OIC
    IM OUTTA YR l
KTHXBYE

To give you the gist of what's going on:

• Input is read from STDIN using the GIMMEH keyword
• Looping is done between the IM IN YR <loopname> and IM OUTTA YR <loopname> statements
• VISIBLE is used to print to STDOUT
• The O RLY?, YA RLY, and OIC statements handle the conditional If/Then/Else logic
• The WTF?, OMG <expression>, and OIC statements handle the conditional Switch/Case logic
• Assignment is performed using <variable> R <value>
• GTFO breaks from a loop or conditional Switch/Case

And then there is the tail-recursive solution which manages to shave off 2 additional characters for a final count of 201:

HAI 1.2
    HOW DUZ I c YR n
        VISIBLE n
        DIFFRINT 1 BIGGR OF 1 n
        O RLY?
            YA RLY
                MOD OF n 2
                WTF?
                    OMG 0
                        c QUOSHUNT OF n 2
                        GTFO
                    OMG 1
                        c SUM OF 1 PRODUKT OF 3 n
                OIC
        OIC
    IF U SAY SO
    I HAS A i
    GIMMEH i
    c i
KTHXBYE

Differences here are the definition of a function between the HOW DUZ I <funcname> YR <args> and IF U SAY SO statements. Functions are called with <funcname> <args>.

Reek

@Chairman I wanted to show the code in it's minimal-character form (without indentation) but what the heck, I'll add it in. :) – Nuclease

Answer 35

Ruby, 41 chars

n=gets.to_i
p n=[n/2,n*3+1][n%2]while n>1

Lauritz

Answer 36

Javascript, 67 56 chars

for(a=[i=prompt()];i-1;a.push(i=i%2?i*3+1:i/2));alert(a)

Messere

Why waste the chars on var ? Also doesn't include the ` -> ` from the output. Using the ternary instead of the array index will save 3 more chars too. – Tunnell

ok. i squeezed it even more. The ' -> ' is not really interesting part and most solutions omit it. Just replace alert(a) with: alert(a.join(' -> ')). – Messere

Answer 37

PHP, 78 72 67 characters

I actually wrote this program about two years ago, after I read about the sequence in a Pickover book. I cleaned it up a bit, and this is the smallest I can make it and still have user input and a nice, readable output:

<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?($n/2):(($n*3)+1);echo"$n\n";}?>

One has to assume short tags are enabled, and I'm not so sure that input will work on all consoles. But it works perfectly on my Windows machine.

---

Update: By cheating on the math just a little, we can shave off some characters:

<?$n=fgets(STDIN);while($n!=1){$n=(($n&1)==0)?$n/2:$n*3+1;echo"$n\n";}?>

---

Update:

• Given that $n&1 returns either 1 or 0, we can take advantage of PHP's loose typedness and remove a couple more characters.
• Also, incorporating Christian's comment below (with a minor alteration to prevent infinite looping), we can remove one more.
• Finally, since PHP scripts don't need a terminating ?>, we can get rid of yet two more characters:

The end result:

<?$n=fgets(STDIN);while($n>1){$n=(!($n&1))?$n/2:$n*3+1;echo"$n\n";}

Crustal

suggest changing to "while($n>0)" to adhere with the 'Given a positive integer greater than 0" requirements. – Bicknell

@Bicknell Close; had to do while($n>1) to prevent infinite looping, but good suggestion. – Essequibo

Answer 38

Fortran: 71 chars

n=1
1 if(n==1)read*,n
n=merge(n/2,3*n+1,mod(n,2)==0)
print*,n
goto1
end

---

Because someone had to do it :)

The count includes required newlines. Fully conformant Fortran 95 (and later) code. Includes full I/O, and performs as many times as you want!

Edit: one less char using a goto (points for style!)

Asleyaslope

Answer 39

MATLAB 7.8.0 (R2009a): 58 characters

n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end

Test case:

>> n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2;disp(n);end
21
    64
    32
    16
     8
     4
     2
     1

Mahler

Hey gnovice, we can avoid the disp(n), with: n=input('');while n>1,n=n/2+rem(n,2)*(n*5+2)/2,end --- *50 characters! – Undergo

@Jacob: Yeah, that would work. But I was trying to stay reasonably close to a decently formatted output like the question has. ;) – Mahler

Answer 40

GW-BASIC - 54 chars

1INPUT N
2N=(N+(N*5+2)*(N MOD 2))/2:?N:IF N>1GOTO 2

Equivoque

Answer 41

Microsoft Small Basic

TextWindow.Write( "Number: " )
n = TextWindow.ReadNumber()
TextWindow.Write( "Results: " )
While ( n > 1 )
  TextWindow.Write( n + " -> " )
  If Math.Remainder( n, 2 ) = 0  Then
    n = n / 2
  Else
    n = n * 3 + 1
  EndIf 
EndWhile
TextWindow.WriteLine(1) 

You can run it at: http://smallbasic.com/program/?ZZR544

Torus

Answer 42

J, 45 characters

(-: * 0&=@(2&|)) + (1 + 3&*) * -.@(0&=@(2&|))

I'm no expert in J. Since the function for mean is +/%#, I'm sure this can be made shorter.

Childers

I like how the program starts with a smile :-) – Justifier

Answer 43

F# 82 Chars

let rec f n=printfn "%A" n;if n>1I then if n%2I=0I then f(n/2I)else f(3I*n+1I)

Phellem

Answer 44

Bash, 130 including spaces and newlines:

#!/bin/bash
if [ $1 == 1 ]; then echo $1
else if [ $(($1%2)) == 0 ]; then n=$(($1/2))
else n=$(($1*3+1))
fi
echo "$1 -> `c $n`"
fi

This assumes that c is the name of the script file, and it is in the path of the user who's running the script.

Krug

Answer 45

VB.Net, about 180 characters

Sub Main()
    Dim q = New Queue(Of Integer)
    q.Enqueue(CInt(Console.ReadLine))
    Do
        q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
        Console.WriteLine(q.Peek)
    Loop Until q.Peek = 1
End Sub

funny thing is converting this code into c# create more characters

to make it work in an empty .vb file (about 245 characters)

Imports System.Collections.Generic
Imports System
Module m
    Sub Main()
        Dim q = New Queue(Of Integer)
        q.Enqueue(CInt(Console.ReadLine))
        Do
            q.Enqueue(CInt(If(q.Peek Mod 2 = 0, q.Dequeue / 2, q.Dequeue * 3 + 1)))
            Console.WriteLine(q.Peek)
        Loop Until q.Peek = 1
    End Sub
End Module

Knap

Can you actually do away with the Import statements and the class around Main? Can I type this in notepad and vbc will eat it? – Brentonbrentt

@Martinho Fernandes, What I do is create an empty console program and paste that in and it work. I didn't try what you said. – Knap

that's what I suspected. VS hides a lot away in project files somehow. – Brentonbrentt

Answer 46

Perl, 59 characters:

sub c{print my$x="@_\n";@_=$x&1?$x*3+1:$x/2,goto&c if$x!=1}

Bron

Answer 47

Python:

def collatz(n):
    if (n%2) == 0:
        return n/2
    else:
        return 3*n+1
def do_collatz(n):
    while n > 1:
        print n
        n = collatz(n)
    print n
do_collatz(int(input("Start number: ")))

Not vulnerable to stack overflows, but does not terminate on a sequence that does not converge on 1. (edit: forgot the input part)

Thunderpeal

Well done Raceimaztion, now as a bonus challenge, simply prove that your program always terminates, or find an example where it doesn't. – Collincolline

@jsn, maybe I should make a code golf to find the number where it doesn't and see the people suffer :) – Chairman

@Chairman That would be more like a "proof golf". – Alfred

I once read about a professor who puts such unsolved problems as questions on his final exams for some advanced class, and every once in a rare while a student solved one... – Azelea

There is no such number that would not converge to 1. – Engraft

Answer 48

Perl, 59 Chars

$n=shift;for($i=1;$n>1;$i++){$n=$n%2==0?$n/2:$n*3+1;printf"%002s: %s\n",$i,$n;}

However, I like this version at 79 chars (not counting whitespace) better because it prints the line number and the iteration value:

$n = shift; for($i = 1; $n > 1; $i++){ $n = $n % 2 == 0 ? $n / 2 : $n*3 + 1; printf "%002s: %s\n", $i, $n;}

$n = shift; 

for($i = 1; $n > 1; $i++){ 
    $n = $n % 2 == 0 ? $n / 2 : $n*3 + 1; 
    printf "%002s: %s\n", $i, $n;
}

Barbital

Answer 49

Ruby 55 chars

n=gets.to_i
while(n>1) do n=((n%2)==1)?3*n+1:n/2;p n end

Perspicacity

Answer 50

Smalltalk, 103 characters

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l]

Call by sending it the message #value: with the desired parameter:

[:n||l|l:=OrderedCollection with:1.[n>1]whileTrue:[l addLast:n.n:=n odd ifTrue:[3*n+1]ifFalse:[n/2]].l] value: 123

Or, more sanely:

[:n | | result |
        result := OrderedCollection with: 1.
        [n > 1] whileTrue: [
                result addLast: n.
                n := n odd ifTrue: [3*n + 1] ifFalse: [n / 2]].
        result] value: 123

(The Proper Way would be to define the above as a method on Integer so you'd say "123 collatz", rather than as an anonymous closure.)

Yate

Answer 51

Common Lisp, 76 74 chars

(defun c(n)(if (eql n 1)'(1)(cons n(if(oddp n)(c(1+(* 3 n)))(c(/ n 2))))))

or, written properly,

(defun collatz (n)
  (if (eql n 1)
      '(1)
    (cons n (if (oddp n)
                (collatz (1+ (* 3 n)))
                (collatz (/ n 2))))))

Yate

Answer 52

J, 31 characters

-:`(>:@(3&*))`1:@.(1&=+2&|)^:a:

Usage:

-:`(>:@(3&*))`1:@.(1&=+2&|)^:a: 9
9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Preconize

Answer 53

Grooovy - 59 chars

int n=args[0] as int
while(n>1){println n=n%2==0?n/2:n*3+1}

Example

$ ./collatz.groovy 5
16
8
4
2
1

---

With prettier output (66 chars)

int n=args[0] as int
while(n>1){print " -> ${n=n%2==0?n/2:n*3+1}"}

Example

$ ./collatz.groovy 5
-> 16 -> 8 -> 4 -> 2 -> 1

Lifeguard

Answer 54

Clojure - 70 chars

((fn[n](prn n)(if(> n 1)(recur(if(odd? n)(+(* 3 n)1)(/ n 2)))))(read))

Or, with proper whitespace and indentation:

((fn [n]
  (prn n)
  (if (> n 1)
    (recur
      (if (odd? n)
        (+ (* 3 n) 1)
        (/ n 2)))))
  (read))

recur forces Clojure to use tail call recursion, so no stack overflows. Works with arbitrarily big numbers. Includes input and output, although it will crash if you enter a non-number :).


Note: shortly after posting my answer I noticed another Clojure implementation with pretty much the same algorithm. However, since that one doesn't attempt to be short, I'll leave my answer here, for what it's worth.

Jackquelin

Answer 55

Josl - 58 characters

This version will not stack overflow due to tail recursion.

c dup println dup 1 > if dup odd? if 3 * 1+ else 2 / end c

Use:

main 21 c

Or, other examples:

main 
  21 c
  63,728,127 c

Chadwell

Answer 56

Erlang, 120 chars

-module (f).
-export ([f/1]).
f(1)->1;
f(N)->
    io:format("~p ",[N]),
    if N rem 2 =:= 0
        ->f(trunc(N/2));
        true->f(3*N+1)
end.

test:

f:f(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

Gaullism

Answer 57

Fortran - 60 Chars

read*,n
1 if(n/2*2<n)n=6*n+2
n=n/2
print*,n
if(n>1)goto1
end

Carboxylase

Answer 58

Go, 130 characters

package main
import(."os"
."strconv")
func main(){n,_:=Atoi(Args[1])
println(n)
for n>1{if n%2!=0{n=n*3+1}else{n/=2}
println(n)}}

Example

./collatz 3
3
10
5
16
8
4
2
1

Tahoe

Answer 59

C: 63 chars

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

This is based on an answer from KennyTM. The for loop was chaged to a while loop and the code brought inside the while.

Stites

Answer 60

JavaScript, 61 70 character with input

Iterative, precision depends on JS limits

var i=prompt('');while(i>1){console.log(i);i=(i%2)?3*i+1:i/2}

Justifier

Can get it to 55 symbols with alert instead of console.log, but usability will suffer. – Justifier

Save 4 to remove var and save more chars with for(i=prompt();i>1;i=i%2?3*i+1:i/2) removing the braces too... However - your code doesn't print the final 1 or include the -> – Tunnell

Answer 61

bash 57/61/60

Another bash entry. Does not perform infinite precision math, and it may overflow.

#!/bin/bash
x=$1;echo $x;((x>1))&&$0 $((x%2?x*3+1:x/2))

A version that should not overflow could be

#!/bin/bash
x=$1;echo $x;((x>1))&&exec $0 $((x%2?x*3+1:x/2))

(edit) An iterative version as well:

#!/bin/bash
for((x=$1;x>1;x=x%2?x*3+1:x/2));do echo $x;done

Falsity

Answer 62

PHP. 69 Characters

Thanks to Danko Durbić for the fgets(STDIN), hope you dont mind :)

<?$i=fgets(STDIN);while($i!=1){echo ($i=$i%2?$i*3+1:$i/=2),"\r\n";}?>

Prado

As with above, suggest changing to while($1>0) – Bicknell

Answer 63

Factor:

without golfing

USE: math
: body ( n -- n ) >integer dup . "->" . dup odd? = [ 3 * 1 + ] [ 2 / ] if ;
: hailstone ( n --  ) dup 1 > [ body hailstone ] [ . ] if  ;
21 hailstone

golfed:

21 [ dup 1 > ] [ >integer dup . "->" . dup 2 mod 1 = [ 3 * 1 + ] [ 2 / ] if ] while .

Output:

21
"->"
64
"->"
32
"->"
16
"->"
8
"->"
4
"->"
2
"->"
1

Dogtrot

Answer 64

VBScript: 105 Characters

Apparently I'm a glutton for punishment.

c(InputBox("?"))
Public Sub c(i)
msgbox(i)
If i>1 Then
If i mod 2=0 Then
c(i/2)
Else
c(3*i+1)
End If
End If
End Sub

Sawbuck

Answer 65

Powershell : 80 characters

One-liner:

"Results: $(for($x=read-host Number;1%$x;$x=@($x/2;3*$x+1)[$x%2]){""$x ->""}) 1"

Pretty-printed:

"Results: $( for( $x = read-host Number; 1%$x; $x = @( $x/2; 3*$x+1 )[ $x%2 ] )
             { 
                 ""$x ->"" 
             }
           ) 1"

Without input prompt and output formatting - 44 characters:

for($x=read-host;1%$x;$x=@($x/2;3*$x+1)[$x%2]){$x}1

Torus

PS Z:\> for($x=read-host;1%$x;$x=@($x/2;3*$x+1)[$x%2]){$x}1 0 Attempted to divide by zero. At line:1 char:20 + for($x=read-host;1%$ <<<< x;$x=@($x/2;3*$x+1)[$x%2]){$x}1 1 – Outfit

Answer 66

Miranda (101 characters)

c n=" 1",if n=1
   =" "++shownum(n)++c(n*3+1),if n mod 2=1
   =" "++shownum(n)++c(n div 2),otherwise

(whitespace is syntactically important)

Schaal

Answer 67

C++ 113 100 95

#include <iostream>
int main(int i){for(std::cin>>i;i>1;i=i&1?i*3+1:i/2)std::cout<<i<<" -> ";}

Personify

It may not be too standard but doing #include <iostream.h> is suppose to translate to #include <iostream> \n using namespace std; – Chairman

Yeah -- I considered that, but none of the compilers I normally use has an <iostream.h> any more... – Personify

Answer 68

C#, 88 chars I think. Recursive

void T(int i,string s){Console.Write("{0}{1}",s,i);if(i!=1)T(i%2==0?i/2:(i*3)+ 1,"->");}

Plus this initial call

T(171, "");

Here is a non-recursive method, 107 chars I think

void T2(int i){string s="";while(i>=1){Console.Write("{0}{1}",s,i);i=i==1?-1:i=i%2==0?i/2:(i*3)+1;s="->";}}

Busyness

Plus using statements, plus a class definition, plus a Main method, plus a Console.ReadLine call, plus an int.Parse or long.Parse or ulong.Parse call. You need a full program with full user input and output.. – Brentonbrentt

Answer 69

Based on ar's code, here's a perl version which actually conforms to the output requirements

perl -E 'print"Number: ";$_=<STDIN>;chomp;print"Results: $_";$_=$_%2?$_*3+1:$_/2,print" -> ",$_ while$_!=1;say""'

Length: 114 counting the perl invocation and quotes, 104 withouit

I'm sure some experienced golfer can reduce this crude version further.

Jarrett

Answer 70

Using an extension of HQ9+ (that I haven't written yet), called HQ9+C where C prints the Collatz Sequence on a number taken from stdin.

C

:P

Susceptive

Why does someone do this every code golf? It was funny once. – Awaken

I'm sorry that I haven't memorized the entirety of StackOverflow like you apparently have. – Susceptive

Some [] jokes are funny once. Do it once, you're a wit; do it twice you're a half-wit. -Robert Heinlein in the voice of Manny – Trickish