Regular Number - Algorithms

Algorithms

Algorithms for calculating the regular numbers in ascending order were popularized by Edsger Dijkstra. Dijkstra (1981) attributes to Hamming the problem of building the infinite ascending sequence of all 5-smooth numbers; this problem is now known as Hamming's problem, and the numbers so generated are also called the Hamming numbers. Dijkstra's ideas to compute these numbers are the following:

• The sequence of Hamming numbers begins with the number 1.

• The remaining values in the sequence are of the form 2h, 3h, and 5h, where h is any Hamming number.

• Therefore, the sequence H may be generated by outputting the value 1, and then merging the sequences 2H, 3H, and 5H.

This algorithm is often used to demonstrate the power of a lazy functional programming language, because (implicitly) concurrent efficient implementations, using a constant number of arithmetic operations per generated value, are easily constructed as described above. Similarly efficient strict functional or imperative sequential implementations are also possible whereas explicitly concurrent generative solutions might be non-trivial.

In the Python programming language, lazy functional code for generating regular numbers is used as one of the built-in tests for correctness of the language's implementation.

A related problem, discussed by Knuth (1972), is to list all k-digit sexagesimal numbers in ascending order, as was done (for k = 6) by Inakibit-Anu, the Seleucid-era scribe of tablet AO6456. In algorithmic terms, this is equivalent to generating (in order) the subsequence of the infinite sequence of regular numbers, ranging from 60k to 60k + 1. See Gingerich (1965) for an early description of computer code that generates these numbers out of order and then sorts them; Knuth describes an ad-hoc algorithm, which he attributes to Bruins (1970), for generating the six-digit numbers more quickly but that does not generalize in a straightforward way to larger values of k. Eppstein (2007) describes an algorithm for computing tables of this type in linear time for arbitrary values of k.