algorithmtime-complexitybig-ospace-complexityhamming-numbers

Hamming numbers for O(N) speed and O(1) memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory.

Hamming numbers is a numbers 2^i*3^j*5^k, where i, j, k are natural numbers.

Is there a possibility to generate Nth Hamming number with O(N) time and O(1) (constant) memory? Under generate I mean exactly the generator, i.e. you can only output the result and not read the previously generated numbers (in that case memory will be not constant). But you can save some constant number of them.

I see only best algorithm with constant memory is not better than O(N log N), for example, based on priority queue. But is there mathematical proof that it is impossible to construct an algorithm in O(N) time?

Solution

  • First thing to consider here is the direct slice enumeration algorithm which can be seen e.g. in this SO answer, enumerating the triples (k,j,i) in the vicinity of a given logarithm value (base 2) of a sequence member so that target - delta < k*log2_5 + j*log2_3 + i < target + delta, progressively calculating the cumulative logarithm while picking the j and k so that i is directly known.

    It is thus an N2/3-time algo producing N2/3-wide slices of the sequence at a time (with k*log2_5 + j*log2_3 + i close to the target value, so these triples form the crust of the tetrahedron filled with the Hamming sequence triples 1), meaning O(1) time per produced number, thus producing N sequence members in O(N) amortized time and O(N2/3)-space. That's no improvement over the baseline Dijkstra's algorithm 2  with the same complexities, even non-amortized and with better constant factors.

    To make it O(1)-space, the crust width will need to be narrowed as we progress along the sequence. But the narrower the crust, the more and more misses will there be when enumerating its triples -- and this is pretty much the proof you asked for. The constant slice size means O(N2/3) work per the O(1) slice, for an overall O(N5/3) amortized time, O(1) space algorithm.

    These are the two end points on this spectrum: from N1-time, N2/3-space to N0 space, N5/3-time, amortized.

    1 Here's the image from Wikipedia, with logarithmic vertical scale:

    enter image description here

    This essentially is a tetrahedron of Hamming sequence triples (i,j,k) stretched in space as (i*log2, j*log3, k*log5), seen from the side. The image is a bit askew, if it's to be true 3D picture.

    edit: 2 It seems I forgot that the slices have to be sorted, as they are produced out of order by the j,k-enumerations. This changes the best complexity for producing the sequence's N numbers in order via the slice algorithm to O(N2/3 log N) time, O(N2/3) space and makes Dijkstra's algorithm a winner there. It doesn't change the top bound of O(N5/3) time though, for the O(1) slices.