Skip to content

Instantly share code, notes, and snippets.

@diakopter
Created February 22, 2011 23:24
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save diakopter/839655 to your computer and use it in GitHub Desktop.
Save diakopter/839655 to your computer and use it in GitHub Desktop.
my $three = BigInteger.Parse("3");
my $five = BigInteger.Parse("5");
sub updateFrontier(BigInteger $value, SortedSet[BigInteger] $frontierSet) {
$frontierSet.Add(BigInteger.op_LeftShift($value, 1));
$frontierSet.Add($value * $three);
$frontierSet.Add($value * $five)
}
sub getHammingNumbers(int $howMany, boolean $all --> List[BigInteger]) {
my $completedNumbers = List[BigInteger].new;
if ($howMany == 0) {
return $completedNumbers;
}
my $frontierSet = SortedSet[BigInteger].new;
$completedNumbers.Add(BigInteger.One);
updateFrontier(BigInteger.One, $frontierSet);
my $count = 1;
while ($count < $howMany) {
my $lowestNumber = $frontierSet.Min;
$frontierSet.Remove($lowestNumber);
if ($all) {
$completedNumbers.Add($lowestNumber)
} else {
$completedNumbers[0] = $lowestNumber;
}
$count++;
updateFrontier($lowestNumber, $frontierSet);
}
return $completedNumbers
}
say "First 20 Hamming numbers: ";
my $twenty = getHammingNumbers(20, true);
loop (my $i=0;$i<$twenty.Count;++$i) { say $twenty[$i] }
say "1691st Hamming number: " ~ getHammingNumbers(1691, false)[0];
say "One millionth Hamming number: " + getHammingNumbers(1000000, false)[0]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment