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 *N ^{2/3}*-time algo producing

`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 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(N ^{2/3})* work per the

These are the two end points on this spectrum: from *N ^{1}*-time,

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

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(N ^{2/3} log N)* time,

- How to generate uniformly distributed subintervals of an interval?
- Generating random number in a non-power-of-2 range from random bits
- Algorithm - Search and Replace a string
- Looking for a branchless algorithm for converting a specific set of 4-bit integers
- Different results for XIRR between Excel and ExcelFinancialFunctions 3.2.0
- Find four,whose sum equals to target
- A* algorithm can't find the goal in Python
- Efficiently getting all divisors of a given number
- Are there any existed API to split IEnumerable<T> to many Vector<T> in CSharp？
- Generating all divisors of a number given its prime factorization
- Efficient way to insert a number into a sorted array of numbers?
- BFS Maximize Minimum Distance from a Monster along a path
- Is there effective algorithm that will return all different combination?
- Big O of algorithm that steps over array recursively
- Modification of Dijkstra's algorithm to make it work with negative weights and its time complexity
- Traversing/Moving over an unfolded cube
- Fibonacci Recursion using Golden Ratio(Golden Number)
- Karatsuba implementation in C
- Why is O(n) better than O( nlog(n) )?
- What is Sliding Window Algorithm? Examples?
- How to write a function to navigate through a non-binary tree?
- Evenly distribute QDate values into certain number of slots
- Find max product using divide and conqure in O(n) time
- Cache-friendly sqare matrix transposition logic issue
- Why doesn't Dijkstra's algorithm work for negative weight edges?
- Fast Convertion From Adjacency List to Edge List
- I convert ASCII words into numbers but am stuck trying to decode them. How to convert 1=a, 2=b, 28=ab etc? (psudeocode okay)
- Reversing the word order in a string in place
- Trying to make a 2x2 rubik's cube solving algorithm , how do i find the solution path (DFS)?
- question about missing element in array