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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.