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

Question

Disclaimer: There are many questions about this, but I have not found any requirements with permanent memory.

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

Is it possible to generate an Nth Hamming number with O (N) time and O (1) (permanent) memory? In the generate section, I mean the generator, i.e. You can display the result and not read previously generated numbers (in this case, the memory will not be constant). But you can save some of them.

I see that only the best algorithm with read-only memory is not better than O (N log N), for example, based on a priority queue. But is there any mathematical proof of the impossibility of constructing an algorithm in O (N) time?

Answer 1

The first thing to consider here is the direct slicing numbering algorithm, which can be seen, for example. in this answer SO , listing triples (k,j,i) in a neighborhood of a given value of the logarithm (base 2) of a sequence member, so that target - delta < k*log2_5 + j*log2_3 + i < target + delta , progressively calculating the cumulative logarithm when choosing j and k , so i directly known.

Thus, this is N ^2/3 -time algo, producing N ^2/3 pan-national sequence fragments at a time (with k*log2_5 + j*log2_3 + i close to the target value, so these triples form a tetrahedron peel filled with the Hamming sequence of the triple ¹ ), which means time O (1) per produced number, thus producing N members of the sequence in O (N) amostated time and O (N ^2/3 ) - space. This is not an improvement over the basic Dijkstra ² algorithm with the same complexities, even unamortized and with better constant factors.

To make this an O (1) space, the width of the cortex will need to be narrowed as it moves along the sequence. But the smaller the crust, the more and more misses there will be when listing its triples - and this is largely the proof that you requested. A constant slice size means that O (N ^2/3 ) works per unit O (1) for the total depreciation time O (N ^5/3 ), O (1) spatial algorithm.

These are two endpoints on this spectrum: from N ¹ -time, N ^2/3 space to the space N ⁰ N 5/3-time, amortized.

---

¹ Here is a Wikipedia image with a logarithmic vertical scale:

This is essentially the tetrahedron of the Hamming sequence, i.e. stretched in space as (i*log2, j*log3, k*log5) , visible from the side. The image is slightly distorted if it is a true three-dimensional image.

edit: ² It seems I forgot that the fragments need to be sorted, since they are produced out of order using j, k-enumerations. This changes the best complexity for creating serial numbers N in order using the algorithm to cut to O (N ^2/3 log N) time, O (N ^2/3 ) space and makes the Dijkstra algorithm the winner there. It does not change the upper bound of time O (N ^5/3 ), although for O (1) slices.