Skip to content

Instantly share code, notes, and snippets.

@sheremetyev
Created February 20, 2011 23:33
Show Gist options
  • Save sheremetyev/836420 to your computer and use it in GitHub Desktop.
Save sheremetyev/836420 to your computer and use it in GitHub Desktop.
Hamming sequence in JavaScript
// Hamming sequence http://oeis.org/A051037
// multipliers for subsequences and corresponding next element
var index = [ { mul: 2, next: 0 }, { mul: 3, next: 0 }, { mul: 5, next: 0 } ];
var queue = [];
function next() {
// special case for the seed of the sequence
if (queue.length == 0) {
queue.push(1);
return 1;
}
// 'merge' subsequences H*2, H*3, H*5 by finding the next min value
var min = Number.MAX_VALUE;
for (var i = 0; i < index.length; i++) {
var x = queue[ index[i].next ] * index[i].mul;
if (x < min)
min = x;
}
queue.push(min)
// advance all sequnces having the same min value
for (var i = 0; i < index.length; i++) {
if (queue[ index[i].next ] * index[i].mul == min)
index[i].next++;
}
// shift the queue when all subsequnces have used the first item
// (note: we are assuming that multipliers are non-decreasing)
if (index[index.length-1].next == 1) {
queue.shift();
for (var i = 0; i < index.length; i++)
index[i].next--;
}
return min;
}
for (var i = 0; i < 1000; i++)
console.log( next() );
console.log( "Queue length: ", queue.length );
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment