php-deluxe.net - description Hamming numbers

Hamming numbers

Dijkstra attributes to Hamming the problem of building the infinite ascending sequence of all positive numbers greater than 1 containing no prime factors other than 2, 3 and 5, i.e. numbers of the form 2^i x 3^j x 5^k (i,j,k >= 0). The ideas to compute them are the following:

Given a hamming number h, then 2h, 3h, 5h are hamming numbers.

1 is a hamming number, as it is used to start the computation.

To maintain them sorted, it is only needed to compare the numbers coming from the multiplication for 2, 3, 5 not used yet. Other products will result greater than some of then, so they are not candidates to be the first in the sorted list.

This algorithm is often used to demonstrate the power of a lazy functional programming language, because this algorithms can be implemented as described above, while an implementation for a strict functional or imperative programming language is highly non-trivial.

= External links =

Encyclopedia of Integer Sequences [http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgiAnum=A051037 A051037]

Smooth Numbers from Mathworld [http://mathworld.com/SmoothNumber.html]