# treat lottery wheel as 90 coins tossed simultaneously. # use C-like loops as ".." style uses lots of memory on # perl 5.004, and not everyone is using 5.005 yet sub clean { my $input=shift; return $input<0?0:$input; } sub max { my ($a,$b) = @_; if ($a>$b) { return $a; } else { return $b; } } # all the work happens here. # note that arguments are n,r when calling the function since # that's how I've always done it. but the hash uses r,n for # administrative convenience. sub h { my $n=shift; my $r=shift; if (exists $h{$r}{$n}) { return $h{$r}{$n}; } if ($n<$r) { return 1; } if ($r==1) { $h{$r}{$n}=$p**$n; return $h{$r}{$n}; } if ($r==0) { return 0; } if ($n==$r) { $h{$r}{$n}=1-$q[$n]; return $h{$r}{$n}; } unless (exists $h{$r}{$n-1}) { for ($i=$r;$i<$n;$i++) { $t=h($i,$r); } } $h{$r}{$n}=clean(h($n-1,$r)-$p*$q[$r]*h($n-$r-1,$r)); if ($n-$r-1>=$r) { delete $h{$r}{$n-$r-1}; } return $h{$r}{$n}; } # main program here $p=1/18; $q=17/18; $coins=90; # make this 900 to do whole of Italian lottery $n_limit=shift; $file= (shift || "modes.".$n_limit); open OUTPUT, ">$file"; $oldmode=0; $l=1/log(1/$q); $phase2=0; # phase 1 is when n is the mode. phase 2 starts the first time # the mode is less than n. $q[0]=0; for (1..1000) { $q[$_]=$q**$_; } $r_min=0; for ($n=1;$n<=$n_limit;$n++) { $mode=0; $modeprob=0; $old_h=($r_min==0)?0:h($n,$r_min)**$coins; for ($r=$r_min;$r<=$n;$r++) { $new_h=h($n,$r+1)**$coins; $pr=clean($new_h-$old_h); $old_h=$new_h; if ($pr>=$modeprob) { $modeprob=$pr; $mode=$r; } else { last; } } if ($phase2==0) { $pr=clean(1-(1-$q[$n])**$coins); if ($pr>$modeprob) { $r_min=$mode; $modeprob=$pr; $mode=$n; } if ($mode<$n) { $phase2=1; %h=(); } } if ($phase2==1) { $r_min=$mode; } if ($mode!=$oldmode) { $sam=int(0.5+log($p*$coins*$n)*$l); if ($phase2==1) { delete $h{$oldmode}; } print OUTPUT "$n $mode $sam\n"; print "$n $mode $sam\n"; $oldmode=$mode; } }