Created
February 20, 2011 23:33
-
-
Save sheremetyev/836420 to your computer and use it in GitHub Desktop.
Hamming sequence in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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