First $k$ numbers with given prime factors

Question

Please help me with the following question. There are three prime numbers given $p_1, p_2$ and $p_3$. Print the first $k$ numbers with only these prime numbers as factors.

Expected solution complexity: $O(k)$

For example: the three prime numbers are $2, 3, 7$.

First $7$ numbers with these as factors are $2, 3, 4, 6, 7, 8, 9$.

Answer 1

Without loss of generalization we can assume $p_1 < p_2 < p_3$

OK, the first one is obvious: $p_1$

For the second one, pick the smallest one of $p_1^2$ and $p_2$

If that was $p_1^2$, then for the third one pick the smallest one of $p_1^3$, $p_2$

If the second was $p_2$, then for the third one pick the smallest one of $p_1^2$ and $p_3$.

For ones after that, see other Answers!

Answer 2

This is a graph problem where each node is a number of the form $n=p_1^{e_1}p_2^{e_2}p_3^{e_3}$ From every number there are three edge of the form $(n,p_in)$. You start exploring all the nodes from smallest to largest starting with $s=1$ (you ignore it later if you want) If you keep track of the visited nodes and the neighbors of them, the next node will be in the neighbor list, so you only need to pick the smallest and update the neighbors. Complexity of this approach is $O(k \cdot logk)$ since you need a heap and probably a set to maintain both sets (visited and neighbors).

I've got another algorithm that might improve the complexity of the previous. Let fix some value $T$ and generate all number of interest less than $T$. This can be done in the same way as I mention before. The complexity of this step is $O($Total numbers of interest less than $T)$. Now lets do the following: Start with $T=1$ and while the numbers you have found so far are less than $k$ let $T:=2\cdot T$. After we finish we will have at most $2\cdot k$ numbers. To recover the first $k$ elements you can find the $k^{th}$ element in linear time. So the total complexity of this algorithm will be $O(2 \cdot k + $Times we double $T)$ Since we know that $T \le 2\cdot p_1^{k}$ (Being $p_1$ the smallest among the three of them) $log(T)\le k\cdot log(p_1) + c$ So we will double $T$ at most $k \cdot log(p_1) $, I think a thigther bound might be proved but at least we have an algorithm which is $O(k + klog(p_1))$

Answer 3

I think the following algorithm will work:

1. Guess an upper bound $u$ for the numbers you're looking for. Your initial guess is some fixed number $\ge 2$. (For simplicity, just say it is $2$).

2. Calculate all multiples of your three primes that are smaller than $u$, but not necessarily in increasing order. This can be done in time linear in the number of multiples you find, by a depth-first search in an (implicit) tree where each multiple appears once -- say, remember for each number you've produced what the largest prime factor of it is, and then consider its children to be its product with that and any larger primes.

3. If you find fewer than $k$ multiples in step 2, your $u$ was too small. Set $u\leftarrow u^2$ and try again.

4. Use a linear selection algorithm to find the $k$th smallest among the products you computed in step 2.

5. Output the numbers in the list that are less than or equal to the one you just found. (They won't be in increasing order, but nobody asked for that!)

Why does this run in linear time?

Each time you square $u$, roughly eight times as many multiples will be found in the next round. To see this, consider the task of finding the $k$ smallest integer combinations of $\log p_1$, $\log p_2$ and $\log p_3$. This amounts to cutting a tetrahedral corner off the three-dimensional integer lattice $\mathbb N^3$, by a plane whose orientation depends on the ratio between the logarithms. Squaring $u$ corresponds to doubling the side lengths in the tetrahedron, so $8$ times as many lattice points will be in the corner we cut off next.

Therefore the last round will find at most $8k$ numbers, give or take a few.

And the total effort made in all rounds other than the last will be dwarfed by the last round anyway: By familiar properties of geometric series, they will add up to only a seventh of the last round.

---

Actually, you may get away with less work than that, if in each round you keep the results of earlier rounds and just continue the search from the points you discarded as too large in the previous round (which you would also remember). Then you don't have to square $u$ for each round, as long as it does grow fast enough that each discarded point will be accepted for the next round (so we can amortize the cost of discarding and reconsidering it). This would correspond to $u\leftarrow p_3u$ instead of $u\leftarrow u^2$, like Marcelo Fornet suggests.

The downside of this is that for fixed $k$, $p_1$ and $p_2$, the work we need to spend will then potentially increase when $p_3$ is chosen larger.

To get the best of both worlds we could instead set $u\leftarrow\min(p_3u,u^2)$.