I want to find the next $n \in \mathbb{N}$ such that

$$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$

Where $\mathbb{P}_B$ is the set of primes not greater than $B$ I know that we can generate the factors of these numbers recursively with complexity less than

$$ \prod_{p_i \in \mathbb{P}_B} \frac{log(s)}{log(p_i)}$$

Exponentially less I believe.

For the 3-smooth numbers this answer gives a good intuition

$$ \frac{(\log(s))^2}{2\log 2 \log 3} $$

For the 5-smooth we could generalize the geometric view we would have $$ \frac{(\log(s))^3}{2 \log 2 \log 3 \log 5} $$

This paper, cited in the 5-smooth numbers OEIS page, mentions a formula as $$ \frac{(\log(s\sqrt{30}))^3}{6 \log 2 \log 3 \log 5} $$ With an additional term (characteristic function of $a^pb^q$) that I don't understand

Can it be made more efficiently without iterating over all the factors?

An algorithm that comes to my mind is, starting with $a_i = 0$,

Find the smallest number $n_i$ that divides $p_i^{a_i+1}$ and also divides all the $p_j^{a_j}$, then I increase $a_i$ and repeat until we have the exact factorization of $n_i$.

For the factor generation, what is the complexity, if we have one factor it is clear to be $O(s)$, if we have all the primes under $\sqrt{p}$ I think it will be $O(s \log(s))$, like the sieve Eratosthenes. The later does at most $log(s)$ iterations and each iteration requires to find the minimum of $\pi(B)$ candidates, thus $\pi(B) \log(s)$, that if we take $B=s$, and approximate $\pi(s) \approx s/\log(s)$, we reduce the complexity to $O(s)$

My main questions are

• Is the process correct (or I missed something in my reasoning)?

• What would be the complexity for the factor set algorithm?

• Are there standard algorithms for this problem?

I want to find the next $n \in \mathbb{N}$ such that

$$s < n = \prod_{p_i \in \mathbb{P}_B} {p_i}^{a_i}$$

Where $\mathbb{P}_B$ is the set of primes not greater than $B$ I know that we can generate the factors of these numbers recursively with complexity less than

$$ \prod_{p_i \in \mathbb{P}_B} \frac{log(s)}{log(p_i)}$$

If we restrict the search to the values such that $n < z$, we have $\sum a_i \log(p_i) < \log(z)$, or $\sum a_i \log(p_i)/log(z) < 1$.

accordingly to wikipedia the volume of under a standard $n-$simlex $1/(n+1)!$, so we reduce the number of candidates to

$$ \frac{1}{\pi(B)!}\prod_{p_i \in \mathbb{P}_B} \frac{log(z)}{log(p_i)}$$

In particular we know that there is one power of $p_i$ between $n$ and $n p_i$, and the formula becomes

$$ \frac{2^{\pi(B)}}{\pi(B)!}\prod_{p_i \in \mathbb{P}_B} \frac{log(s)}{log(p_i)} = \frac{(2\log(s))^{\pi(B)}}{\pi(B)!}\prod_{p_i \in \mathbb{P}_B} \frac{1}{log(p_i)}$$

• What would be the complexity for the factor set algorithm?

• Are there standard algorithms for this problem?