Hamming Problem is a famous problem which basically generates all integers which prime factors are {2,3,5} only. (And it can be extended to any set of prime factors I think)
To find the n-th Hamming number, there is a clever O(N) constructing algorithm by Dijkstra, which pseudo code is as following:
List<int> H
int i=0,j=0,k=0, n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
int next = min(2*H[i], 3*H[j], 5*H[k])
H.add(next)
if(next == 2*H[i]) ++i
if(next == 3*H[j]) ++j
if(next == 5*H[k]) ++k
output(H[10])
The key point in this solution is that, if H is a hamming number, then 2H, 3H, 5H is also a hamming number
I came across a problem, which I sensed it's a bit like Hamming Problem, but it's not constructing number using set of prime factors, instead if I rephase the problem statement, it is like the following:
1 is in the result set. If H is in result set, then 2H+1 and 3H+1 is also in the result set. Find the n-th number in the result set
Then I wonder if the same constructing algorithm works for this problem, turns out it does! (And I even have no idea why it works)
Def f(x) 2x+1
Def g(x) 3x+1
List<int> H
int i=0,j=0,n=10 // find the 10-th hamming number
H.add(1)
for(i=0 to 10)
int next = min(f(H[i]), g(H[j]))
H.add(next)
if(next == f(H[i])) ++i
if(next == g(H[j])) ++j
output(H[10])
So then I wonder:
Is this constructing algorithm works for problems of generating numbers, given a rule like "If x is in the result, then all f(x), g(x), p(x), q(x)... are also in the result", provided that these functions will give a result >= x?
A sufficient condition is that all functions f_i from the integers to the integers must be monotonic increasing and have n < f_i(n) for all i and n.
An example demonstrating that you need something like the integers part of the rule is the pair of functions (n+0.5, (n + floor(n+1))/2). This will lead to the sequence 1, 3/2, 7/4, 15/8, ... and you'll never get to 2.
The functions (2^n, 20 - 5n + n^2) comes out in the order 1, 2, 4, 16, 14, ... and is clearly not in order. Hence the need for non-decreasing.
The function (n-3) gives the sequence (1, -2, -5, ...) and shows the importance of n < f_i(n).
So why does this work?
First of all it is clear that anything output by this algorithm is in the set.
Going the other way, suppose all three conditions are met. We then have to prove by induction that if you belong in the sequence, we begin looking for you before we get there, and then must produce it when we pass you. (That we pass you is guaranteed by the fact that the sequence is an increasing set of integers.) The proof is a little messy, but straightforward.