Counting Squarefree Integers $i \le n$ Coprime to the First $k$ Primes

Question

The number of positive squarefree integers $i \le n$ is given by: $$C(n)=\sum_{k=1}^{\lfloor\sqrt{n}\rfloor}\mu(k)\left\lfloor\frac{n}{k^{2}}\right\rfloor.$$ The number of positive integers $i\le n$ coprime to the first $k$ prime numbers admits the recurrence relation: $$\phi(n, k) = \lfloor n / p_k \rfloor - \phi(\lfloor n/p_k \rfloor, k-1) + \phi(n, k-1)$$

But I haven't managed to find any literature regarding the subject of numbers that are both squarefree AND coprime to the first $k$ prime numbers, with the exception of odd/even such integers ($k=1, p = 2$). Let $P_k = p_1\cdot p_2 \cdot...\cdot p_k$ be the primorial of the first $k$ primes. If we define $$f(n,k) = \sum_{i = 1 \atop gcd(i,P_k)=1}^{n}|\mu(i)|$$

to be the count of squarefree integers coprime to the first $k$ primes, then does this formula admit any elegant representations? Is there any way to efficiently exactly count (not an approximation) such numbers mathematically or at least compute this count efficiently?

Answer 1

To approach your problem, I would just write down your formula in terms of images and inverse images of the involved functions.

So take $|\mu|(n)$ to be the absolute value of $\mu(n)$ for each $n \in \Bbb{N}$.

Then:

$$ f(n,k) = \sum_{a=1}^n|\mu|(a \in \gcd^{-1}( p_1\cdots p_k,\cdot)(1)) $$

Where, if you look at $\gcd(p_1\cdots p_k, n) = g(n)$ as a multiplicative function, then we're interested in $\ker g$.

Thus $f(n,k) = |[1,..,n]\cap \ker |\mu| \cap \ker g|$,

$|\mu|$ also being a multiplicative function.

This is about as elegant a formula that I can come up with.

Note that $\ker g$ here is defined here as $\ker g = \{ n \in \Bbb{N}: g(n) = 1\}$, but the set $\ker |\mu|, \ker g$ are not monoids. They do however satisfy: if $a, b \in \ker g: \gcd(a,b) = 1 \implies ab \in \ker g$.

---

This means that the limit supremum exists for $a_n = f(n,k)/n$, i.e. $\lim\sup_{n \to \infty} a_n = \overline{d}(A)$, where $A = \ker g \cap \ker |\mu|$.

See natural density examples. Since the bound is from above, we must have: $\overline{d}(A) \leq \lim_{n \to \infty} \dfrac{|[1..n] \cap \ker |\mu||}{n} = 6/\pi^2$.

And $\underline{d}(A) \geq 0$.

---

I thought that I'd mention natural density because the problem naturally takes that form (just add a denominator $n$ and take lim sup/inf).

---

We also have a related formula:

$$\ker |\mu| \cap \ker g = \ker (|\mu| \cdot g) = \{ n \in \Bbb{N} : |\mu(n)|g(n) = 1 \}$$, where $|\mu| \cdot g$ is also a multiplicative function, i.e. for all $a,b \in \Bbb{N}$ such that $\gcd(a,b) = 1$, you have that $|\mu|(ab)g(ab) = (|\mu|(a)g(a))(|\mu|(b)g(b))$.