algorithmmathhamming-numbers# Hamming number using custom functions instead of prime

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?**

Solution

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.

- 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