Hamming Problem

The HammingProblem requires you to generate in ascending order all number divisible only by a given set of primes, usually 2, 3 and 5. It's a standard problem with standards solutions, but the solution types vary according to the "native" language of the programmer.

---

A quick JavaLanguage version of a solution that uses a variant of EwDijkstra's stream-processing algorithm, implemented on top of Java Collections. No doubt full of Java CodeSmell (especially the implementations of unneeded abstract methods, etc.), but nonetheless pretty readable and uses O(N) time, although somewhat closer to O(3*N) space than is necessary due to not optimizing the three queues into a single one with multiple pointers, probably done using Vector if we want to keep things Collection-oriented.

 static class hamNums implements Iterator<BigInteger> {
static class MergedQueue extends AbstractQueue?<BigInteger> {
Queue<BigInteger> first, second;
BigInteger firstBase, secondBase;

public MergedQueue (BigInteger f, BigInteger s,
Queue<BigInteger> first, Queue<BigInteger> second) {
firstBase = f;
secondBase = s;
this.first = first;
this.second = second;
}

public Iterator iterator() {return null;}

public boolean offer(BigInteger e) {
return second.offer(e.multiply(secondBase))
&& first.offer(e.multiply(firstBase));
}

public BigInteger peek() {
int i = first.peek().compareTo(second.peek());
if (i < 0) return first.peek();
return second.peek();
}

public BigInteger poll() {
int i = first.peek().compareTo(second.peek());
if (i < 0) return first.poll();
else if (i > 0) return second.poll();
first.poll();
return second.poll();}
}

public int size() {
return first.size() + second.size();
}
}

MergedQueue a, hams;
LinkedList<BigInteger> p1, p2, p3;

public hamNums() {
p1 = new LinkedList<BigInteger>();
p2 = new LinkedList<BigInteger>();
p3 = new LinkedList<BigInteger>();
a = new MergedQueue (BigInteger.valueOf(2), BigInteger.valueOf(3),
p1, p2);
hams = new MergedQueue (BigInteger.ONE, BigInteger.valueOf(5), a, p3);
hams.offer(BigInteger.ONE);
}

public boolean hasNext() {
return true;
}

public BigInteger next() {
BigInteger b = hams.poll();
hams.offer(b);
return (b);
}

public void remove() {
return;
}
 }

Interesting side-note: We can take the "derivative" of the triple of exponents used to produce each value (i.e. the difference between each triple and the prior one), and throw these transforms into a PriorityQueue based on their own exponential evaluation. The resultant set of transforms can be viewed as a set of "rules" to be applied in order of least to greatest value (which is equivalent to factor by which any transform will increase the prior ham number its applied to). These rules (which are [i think] roughly of size O(1/principal nth root of 2) which is to say essentially O(1)) can be then turned on-the-fly into a new sequence generator which still operates in O(n) time but also in O(1) space. This gives Hamming's sequence the interesting property that while its computation is non-trivial, it is nonetheless highly compressible.

---

A wee bit more readable famous HaskellLanguage one-liner is

 hamm = 1 : map (2*) hamm ## (map (3*) hamm ## map (5*) hamm) 
  where (x:xs) ## (y:ys) = case compare x y of
           LT -> x : xs     ## (y:ys)
           EQ -> x : xs     ## ys
           GT -> y : (x:xs) ## ys
 test = take 20 (tail hamm)       -- prints [2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40]

Here the three lists are merged, each maintaining its back pointer into the correspondent element on the shared resulting (unbounded) list.

---

See LanguageTestCase, LanguageComparisonFramework