n-th number with given prime divisors

Question

I would like to compute th $n$-th positive integer whose prime divisors are among numbers $2$, $3$ and $5$. $n$ is at most $12500$.

My first approach was sieving but i found out that there are less than $1500$ such numbers below $8\cdot10^8$ and such computation took me almost $14$ seconds.

My next idea is to compute them somehow recusively but how? We need to list all the numbers of the form $~2^a 3^b 5^c~$ and I don't understand how to generate them in natural order so that $n$-th number is found as fast as possible. Well, we can generate them just somehow and then sort the list but how to understand when it's time to stop generation? We can put the limit $c,b,a <= 12500$ but this approach will be extremely inefficient.

So the problem, as i see it, reduces to finding some $~A~$ such that listing all numbers of the form $2^a 3^b 5^c$ with $c \leq b \leq a \leq A$ guarantees that first $n$ numbers of such form are listed. And this $A$ should be not too large so that listing them can be done in reasonable amount of time (less than a second is OK).

Thanks in advance for any ideas.

Answer 1

The algorithm:

As you said, a brute-force approach like sieving or going through each number and testing it is going to take too long. We must use a recursive approach. We represent each number $2^a3^b5^c$ by a triplet $(a, b, c)$, called a 'node'. Note that each number $2^a3^b5^c$ can generate three new 'child' nodes -- $2^{a+1}3^b5^c$, etc. -- by incrementing any one of the three numbers in the triplet. We begin with an empty list of 'open' nodes, i.e. nodes whose children have yet to be generated. Each node has three flags indicating whether which of its children has been generated.

To this list of open nodes, we add the root node $(0, 0, 0)$ with no flags set. Now we repeat the following steps $n$ times:

1. We generate all the ungenerated children of all the nodes in the open list. (We do not mark all of them as 'generated'; see the next step.)
2. We compare their values to find the smallest one and mark this child as 'generated'.
3. We add this child node to the open list and set the corresponding flag in its parent node.
4. If any node in the opens list has all three flags set, then we remove it from the list.

At the end of this procedure the last child node generated will be the one you are looking for.

Optimizations:

An obvious optimization is to pregenerate all the nodes and store them in a table, but this seems like cheating. Instead, I simply do not clear the table of existing nodes after each time the $n$th number is generated, but I merely reset their flags.

Note that to "compare the values" of the children, we need to do heavy computing to calculate $2^a3^b5^c$ and then figure out which is larger. I avoid this by precomputing the logarithm of this value for each node when it is created, and comparing these to find the smallest. The logarithm is easy to calculate: $a\log 2 + b\log 3 + c\log 5$, where $\log 2$, $\log 3$, and $\log 5$ are constants.

All the other optimizations are code-based, such as using HashMaps, using good hashing strategies, carefully choosing when to actually calculate the logarithms, tweaks using a profiling tool, etc.

Performance:

The code is available here. I apologize for the nonexistence of documentation. The code is in Java and requires Java 8 to run. I had initially made a Python version to test the algorithm, but that is slow.

On a 1 GHz AMD Athlon (64-bit), the average run-time after warmup is a little less than 0.6 seconds. The worst case run-time without warmup is less than 2 seconds. On a 2.7 GHz Intel i5 (64-bit), the corresponding numbers are 0.24 and 1. (This is all assuming $n \leq 12500$.) The algorithm does not use parallel processing, but I doubt it will help much.