1
$\begingroup$

Give a list from $1$ to $N$ where $N$ is a positive non-zero integer and a list of prime numbers $p$, $q$, $r$, etc. What are the number of cases left from the $N$ list that are not a divisible by any of the these primes. For example, given two primes $q$ and $q$ I have the count as $N - \left\lfloor{N/p}\right\rfloor - \left\lfloor{N/q}\right\rfloor + \left\lfloor{N/\left({p\, q}\right)}\right\rfloor$. What is the general formula for a list of $n$ primes.

$\endgroup$
  • 1
    $\begingroup$ your few first terms generalize to $\sum_{n \in E} \mu(n) \lfloor N/n\rfloor$ where $E$ is the set of integers whose all prime factors are in your list of prime numbers, and $\mu(n)$ is the Möbius_function. you can understand this in term of the $\zeta(s)$ function for your list of primes $A$ : $\zeta_A(s) = \prod_{p \in A} \frac{1}{1-p^{-s}} = \sum_{n \in E} n^{-s}$ so that $\frac{1}{\zeta_A(s)} = \sum_{n \in E} \mu(n) n^{-s}$ and the en.wikipedia.org/wiki/Dirichlet_convolution $\endgroup$ – reuns Jun 13 '16 at 21:35
  • $\begingroup$ If you're intimidated by the notation in the previous comment, the general formula is that you sum over all $2^n$ possible products of $n$ primes, and you negate the terms which have an odd number of primes in them. For instance for $p,q,r$ you'd have $N - \lfloor N/p \rfloor - \lfloor N/q \rfloor - \lfloor N/r \rfloor + \lfloor N/pq \rfloor + \lfloor N/qr \rfloor + \lfloor N/pr \rfloor - \lfloor N/pqr \rfloor$. $\endgroup$ – Erick Wong Jun 13 '16 at 22:05
  • $\begingroup$ I have also noticed the case for three primes. I am following the notation from the first comment. I am going through the derivation. $\endgroup$ – Lorenz H Menke Jun 13 '16 at 22:39

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.