1
$\begingroup$

The following Math Exchange question deals with a similar problem:

Not divisible by $2,3$ or $5$ but divisible by $7$

However, the answers given become infeasible quite quickly because the amount of permutations increases too rapidly as P grows.

$\endgroup$
  • $\begingroup$ It doesn't become infeasible sooo quickly, because the products of primes in the inclusion-exclusion grow pretty fast. What sort of $N$ and $P$ are you interested in? $\endgroup$ – Daniel Fischer Jun 29 '15 at 8:51
  • $\begingroup$ I'm working with N in the range of 10^9 and P in the range of 10^4, for example. $\endgroup$ – Nicolás Siplis Jun 29 '15 at 8:54
  • $\begingroup$ Then you have around $1000$ primes less than $P$ to consider, and the products of such primes you need to consider do not exceed about $10^5$. That's products of at most six primes. With a good dynamic programming approach to break out as soon as you can, that is feasible. At least unless you have very tight time constraints. If you don't need an exact count and an approximation suffices, Mertens' third theorem becomes relevant. $\endgroup$ – Daniel Fischer Jun 29 '15 at 9:05
  • $\begingroup$ I considered applying Merten's third theorem but I figured inclusion-exclusion would yield a better answer. $\endgroup$ – Nicolás Siplis Jun 29 '15 at 9:07
  • $\begingroup$ Wait. The quotient $N/P$ is only about $10^5$, when $P$ is near the upper end. That calls for sieving. Take the DP approach when $P$ is smaller. $\endgroup$ – Daniel Fischer Jun 29 '15 at 9:08

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.