Mercurial > coderloop

annotate src/collatz.pl @ 0:307a81e46071 tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
initial committ
author Robert McIntyre <rlm@mit.edu>
date Tue, 18 Oct 2011 01:17:49 -0700
parents
children
rev   line source
rlm@0 1 #!/usr/bin/perl
rlm@0 2
rlm@0 3 use bigint;
rlm@0 4 $a = "/home/r/coderloop-test/euler14-a.in";
rlm@0 5 $b = "/home/r/coderloop-test/euler14-b.in";
rlm@0 6
rlm@0 7 sub read_integer{
rlm@0 8 ##reads an integer from a file
rlm@0 9 (my $file) = @_;
rlm@0 10 my $int;
rlm@0 11 open FILE, "<".$file or die $!;
rlm@0 12 for (<FILE>){ chomp; /^\W*(\d+)\W*$/; $int = $1;}
rlm@0 13 close FILE;
rlm@0 14 return $int;}
rlm@0 15
rlm@0 16
rlm@0 17 @collatz = (1);
rlm@0 18
rlm@0 19
rlm@0 20 sub collatz_next {
rlm@0 21 my $n = @_[0];
rlm@0 22 if (1 == $n) {return 1;}
rlm@0 23 if (0 == ($n % 2)){ return $n/2;}
rlm@0 24 if (1 == ($n % 2)){ return (($n*3)+1);}
rlm@0 25 }
rlm@0 26
rlm@0 27 sub different_collatz_length {
rlm@0 28 my $n = $_[0];
rlm@0 29 my $d = 1;
rlm@0 30 while ($n != 1){
rlm@0 31 $d++;
rlm@0 32 $n = collatz_next($n);}
rlm@0 33 return $d;}
rlm@0 34
rlm@0 35 sub collatz_length {
rlm@0 36 ## calculate the length of the collatz sequence
rlm@0 37 ## http://en.wikipedia.org/wiki/Collatz_conjecture
rlm@0 38 ## starting at n
rlm@0 39 my $n = @_[0];
rlm@0 40 #print $n,"\n";
rlm@0 41 #memoization
rlm@0 42 #print "***** ", $collatz[$n], " ********\n";
rlm@0 43 if (defined $collatz[$n]){return $collatz[$n];}
rlm@0 44 if (1 == $n) {return 1;}
rlm@0 45 if (0 == ($n % 2)){ return (1 + &collatz_length($n/2))}
rlm@0 46 if (1 == ($n % 2)){ return (1 + &collatz_length(($n*3)+1));}
rlm@0 47 }
rlm@0 48
rlm@0 49
rlm@0 50 sub max_collatz {
rlm@0 51 my $n = @_[0];
rlm@0 52 my $max_length = 1;
rlm@0 53 my $max_val = 1;
rlm@0 54 for (my $i = 1; $i < $n; $i++){
rlm@0 55 my $collatz = &different_collatz_length($i);
rlm@0 56 #push(@collatz, $collatz);
rlm@0 57 if ( $collatz >= $max_length){
rlm@0 58 $max_length = $collatz ;
rlm@0 59 $max_val = $i}}
rlm@0 60 print "\n number is : $max_length --- ";
rlm@0 61 print &collatz_length($max_val) . "\n";
rlm@0 62 return $max_val;
rlm@0 63 }
rlm@0 64
rlm@0 65
rlm@0 66
rlm@0 67
rlm@0 68 if (defined @ARGV){
rlm@0 69 print &max_collatz(read_integer($ARGV[0])), "\n";}