Code Golf: Collatz Conjecture
Language AgnosticCode GolfRosetta StoneCollatzLanguage Agnostic Problem Overview
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.
Language Agnostic Solutions
Solution 1 - Language Agnostic
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
Solution 2 - Language Agnostic
Befunge
&>:.:1-|
>3*^ @
|%2: <
v>2/>+
Solution 3 - Language Agnostic
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!
Solution 4 - Language Agnostic
95 64 51 46 char
Python - Obviously does not produce a stack overflow.
n=input()
while n>1:n=(n/2,n*3+1)[n%2];print n
Solution 5 - Language Agnostic
63 76 83, 86, 97, 137
Haskell, 62 chars 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()
)
Solution 6 - Language Agnostic
#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.
Solution 7 - Language Agnostic
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;
Solution 8 - Language Agnostic
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 20x258 (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 220,000+1 (aprox. 3.98e6,020) in 68 seconds, 144,404 cycles.
Solution 9 - Language Agnostic
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.
Solution 10 - Language Agnostic
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. ;)
Solution 11 - Language Agnostic
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... :| )
Solution 12 - Language Agnostic
Another assembler version. This one is not limited to 32 bit numbers, it can handle numbers up to 1065534 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
Solution 13 - Language Agnostic
25 28
dc - 24 chars [dc
][1] 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][2] 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[1]: http://linux.die.net/man/1/dc [2]: https://stackoverflow.com/questions/2388254/code-golf-collatz-conjecture/2388910#2388910
Solution 14 - Language Agnostic
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.]
Solution 15 - Language Agnostic
50 chars
Mathematica, 45 c=NestWhileList[If[OddQ@#,3#+1,#/2]&,#,#>1&]&
Solution 16 - Language Agnostic
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
Solution 17 - Language Agnostic
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);
}
}
Solution 18 - Language Agnostic
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
Solution 19 - Language Agnostic
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
Solution 20 - Language Agnostic
Haskell : 50
c 1=[1];c n=n:(c$if odd n then 3*n+1 else n`div`2)
Solution 21 - Language Agnostic
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.
Solution 22 - Language Agnostic
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);}}
Solution 23 - Language Agnostic
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)))))
Solution 24 - Language Agnostic
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...
Solution 25 - Language Agnostic
nroff1
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
Solution 26 - Language Agnostic
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"
Solution 27 - Language Agnostic
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
Solution 28 - Language Agnostic
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/>";
}
}
}
Solution 29 - Language Agnostic
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.
Solution 30 - Language Agnostic
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
Solution 31 - Language Agnostic
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);
}
}
}
Solution 32 - Language Agnostic
Windows cmd - 68 chars
@set/pd=
:l
@set/ad=(d+d%%2*(d*5+2))/2&echo %d%&if %d% NEQ 1 goto:l
Solution 33 - Language Agnostic
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
Solution 34 - Language Agnostic
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
Solution 35 - Language Agnostic
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!)
Solution 36 - Language Agnostic
78 72 67 characters
PHP, 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 either1
or0
, 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";}
Solution 37 - Language Agnostic
67 56 chars
Javascript, for(a=[i=prompt()];i-1;a.push(i=i%2?i*3+1:i/2));alert(a)
Solution 38 - Language Agnostic
Ruby, 41 chars
n=gets.to_i
p n=[n/2,n*3+1][n%2]while n>1
Solution 39 - Language Agnostic
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>
andIM OUTTA YR <loopname>
statements VISIBLE
is used to print to STDOUT- The
O RLY?
,YA RLY
, andOIC
statements handle the conditional If/Then/Else logic - The
WTF?
,OMG <expression>
, andOIC
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>
.
Solution 40 - Language Agnostic
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)
Solution 41 - Language Agnostic
Perl, 59 characters:
sub c{print my$x="@_\n";@_=$x&1?$x*3+1:$x/2,goto&c if$x!=1}
Solution 42 - Language Agnostic
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
Solution 43 - Language Agnostic
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.
Solution 44 - Language Agnostic
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)
Solution 45 - Language Agnostic
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.
Solution 46 - Language Agnostic
Small Basic
MicrosoftTextWindow.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
Solution 47 - Language Agnostic
GW-BASIC - 54 chars
1INPUT N
2N=(N+(N*5+2)*(N MOD 2))/2:?N:IF N>1GOTO 2
Solution 48 - Language Agnostic
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.
Solution 49 - Language Agnostic
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="->";}}
Solution 50 - Language Agnostic
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<<" -> ";}
Solution 51 - Language Agnostic
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)
Solution 52 - Language Agnostic
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
Solution 53 - Language Agnostic
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
Solution 54 - Language Agnostic
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
Solution 55 - Language Agnostic
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";}?>
Solution 56 - Language Agnostic
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
Solution 57 - Language Agnostic
70 character with input
JavaScript, 61 Iterative, precision depends on JS limits
var i=prompt('');while(i>1){console.log(i);i=(i%2)?3*i+1:i/2}
Solution 58 - Language Agnostic
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.
Solution 59 - Language Agnostic
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
Solution 60 - Language Agnostic
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
Solution 61 - Language Agnostic
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
Solution 62 - Language Agnostic
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
Solution 63 - Language Agnostic
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.
Solution 64 - Language Agnostic
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
Solution 65 - Language Agnostic
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
Solution 66 - Language Agnostic
76 74 chars
Common Lisp, (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))))))
Solution 67 - Language Agnostic
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.)
Solution 68 - Language Agnostic
Ruby 55 chars
n=gets.to_i
while(n>1) do n=((n%2)==1)?3*n+1:n/2;p n end
Solution 69 - Language Agnostic
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;
}
Solution 70 - Language Agnostic
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