3
$\begingroup$

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?

$\endgroup$

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.