The range-restricted Hamming problem

Some years before Dijkstra attributed it to Hamming, Gingerich considered an interesting variant of Hamming's problem: list, in order, only those regular numbers in the interval [60^k,60^k+1).

The motivation comes from the study of Babylonian mathematics. In the sexagesimal system the Babylonians used, which we still use a modified version of for times, latitudes and longitudes, and angles, the power of the initial base-\( 60 \) digit was not specified. That is, if I tell you that a duration of time is 1:12, it's not obvious from that notation whether I mean one hour and twelve minutes (that is, \( 72 \) minutes), or one minute and twelve seconds (that is, \( 72 \) seconds); both are written the same way. So, in a Babylonian table of the reciprocals of regular numbers, one would not have separate entries for \( 72 \), \( 72\times 60 \), and \( 72\times 60\times 60 \); all three would just be written as 1:12. Grouping equivalent numbers in this way allowed the Babylonians a considerable space savings in their arithmetic tables: there are \( O(k^2) \) different \( k \)-digit sexagesimal representations of regular numbers to be listed, while there are \( \Theta(k^3) \) actual regular numbers that can be represented with \( k \) digits. The sorted order of the regular numbers in Gingerich's range is the order in which the Babylonians would have listed these numbers.

Gingerich listed these numbers out of order, and then sorted them. Can we do better, and list them in sorted order in a constant number of arithmetic operations per output value? Yes!

The figure below is something that Gingerich mentions, attributed to a 1934 paper of Neugebauer. Considering two sexagesimal numbers as equivalent whenever their ratio is a power of sixty, we can project the three dimensional lattice of regular numbers \( 2^i\, 3^j\, 5^k \) perpendicularly to the line through 1 and 60 to produce a planar lattice of equivalence classes of regular sexagesimal numbers:

The image shows only the two-digit regular numbers, but we can extend the same idea to form a lattice of regular numbers with any number of digits. The light red arrows show the relation between each number and its neighbors in different directions; for instance, the neighbor to the right of a number \( x \) (as the figure is aligned) is always the number \( 2x \). The lattice describes several interesting relations between these numbers; for instance, the reciprocal of a number is just its reflection around the center at the number 1, and the square of a number is on the same line twice as far from 1, while the product of any two numbers can be found by completing a parallelogram through the two numbers and 1.

If we consider the numbers in this lattice that have representations with \( k \) or fewer digits, interpreted so that their initial digits all have equal powers, then this gives exactly the set of regular numbers in Gingerich's range \( [60^k,60^{k+1}) \). However, if we interpret them differently (as would be conventional for decimal numbers) so that the final digits are all units, they are instead the regular numbers in the range \( [1,60^{k+1}) \) that are not divisible by \( 60 \). That is, there is a straightforward equivalence between these two different subsets of regular numbers. Since we need to refer to them later, let's call the regular numbers not divisible by \( 60 \) from the latter interpretation "reduced regular numbers".

It's not hard to list the reduced regular numbers in sorted order. One method is to apply Dijkstra's idea: let sequence \( H \) be formed by outputting \( 1 \), then merging \( 2H \), \( 3H \), and \( 5H \), however in the merge step remove all multiples of \( 60 \). One can then shift each number into Gingerich's range by multiplying by an appropriate power of \( 60 \), to generate all regular numbers in this range. However, these shifts would destroy the sorted ordering of the numbers. One could imagine extracting sorted subsets of numbers that need equal shifts, and then merging these extracted subsets with each other, but that would use a nonconstant number of merge steps per value.

Instead, let's view the lattice above a little more carefully. Interpreted as the set of reduced regular numbers, it can be seen to be divided into four quadrants, two of which overlap and the other two of which are stretched into \( 135 \) degree angles. In the angle from the northwest to the east, we see a grid of the \( 3 \)-smooth numbers, having as prime factors only \( 2 \) and \( 3 \). Similarly, in the angle from the east to the southwest, we see a grid of the regular decimal numbers, having as prime factors only \( 2 \) and \( 5 \). Finally, in the angle from northwest to southwest, we have an overlay of two such grids, one of the odd regular numbers and another of the doubles of odd regular numbers. The \( k \)-digit numbers that we are interested in form a triangular subset of each grid. If we can generate the numbers in each of these triangles, sorted by their sexagesimal representations rather than by their reduced regular values, then we can merge these four sequences to form our desired output.

So to keep things simpler, let's only consider the \( 3 \)-smooth numbers \( 2^i 3^j \) in the upper right grid. We'll show how to sort all such numbers with \( 0 \le i \lt M \) and \( 0 \le j \lt N \). The k-digit 3-smooth numbers can then be found by choosing \( M \approx k\log_2 60 \) and \( N \approx k\log_3 60 \), giving a rectangular subset half of which is the triangle we want and the other half of which can be discarded. This generates the numbers we need in one of the quadrants of the diagram above; the other quadrants are similar.

Our algorithm will maintain a sorted rectangular region of the grid and double the size of this region at each step until it covers as much of the grid as we want. So, suppose that we have already sorted the \( 3 \)-smooth numbers with \( 0 \le i \lt M \) and \( 0 \le j \lt N \). We wish to double \( M \), say, by sorting the numbers with \( M \le i \lt 2M \) and \( 0 \le j \lt N \). But each such number is just \( 2^M \) times a number from the already-sorted rectangle. If \( 2^M \) has \( d \) sexagesimal digits, then multiplying by \( 2^M \) increases the number of digits by either \( d \) or \( d-1 \). (Note that this would not be true for numbers divisible by \( 15 \), as the length would be additionally reduced by the removal of trailing zeros, but no such numbers exist in this grid.) If two numbers are lengthened by the same amount, then they remain in the same sorted order with respect to each other. So to sort this new rectangle, we partition it into two sorted subsequences, one of the numbers that are lengthened by \( d-1 \) digits and the other of the numbers that are lengthened by \( d \) digits. The sorted sequence of the doubled rectangle that we desire is the merger of the smaller already-sorted grid with these two subsequences.

The same idea allows the efficient generation of regular numbers in any range, not just the ranges considered by Gingerich. To list numbers in another range, find the nearest power of 60 below this range, and apply this algorithm. If the desired range extends past the numbers generated by this algorithm, one can then use Dijkstra's algorithm to extend the sequence through the rest of the range at a constant additional number of operations per generated value.

Comments: