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

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?

• Is your formula for $\phi(n,k)$ missing some floor functions. Could you please enter those in or provide link that derives the formulas? Commented Sep 14, 2020 at 20:34
• yes, will add them, thank you Commented Sep 14, 2020 at 21:00
• $$\sum_{n\le x, \gcd(n,m)=1} |\mu(n)| = \sum_{d| m} \mu(d) \sum_{n\le x/d} |\mu(dn)|=\sum_{d\in A_m} \lambda(d)\sum_{n\le x/d}|\mu(n)|$$ where $A_m$ are the integers whose every prime factors divide $m$. Commented May 1, 2021 at 21:36
• @reuns Hey, I tried the formula, but it doesn't agree with a brute-force calculation. I interpreted $\lambda (d)$ as Carmichael function. Calculating $f(10,2)$ for example gives $24$ instead of $3$. Are you sure it is correct? Commented Sep 7, 2021 at 8:44

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))$$.

• Thank you very much for such a detailed answer. Some of the math is too complex for me, so I will have to do some extra reading. Is the representation that you mentioned for $f(n,k)$ computable? Commented Sep 15, 2020 at 10:48
• @MCFromScratch $\mu$ is computable because factoring is, but intersecting with the kernel of its absolute value, not sure. I shortened the post a bit by taking out the part about binary operations applied to sets elementwise. Commented Sep 15, 2020 at 19:03
• For small values of $n$ you can test whether $\gcd(p_1 \cdots p_k, n) = 1$ and $|\mu(n)| = 1$. Since $n$ is small you can factor it quickly enough. Commented Sep 15, 2020 at 19:18
• @MCFromScratch see bolded part I added. $\ker g, \ker |\mu|$ are not monoids, but if $a, b \in \ker g$ and $\gcd(a,b) = 1$, then $ab \in \ker g$. Commented Sep 17, 2020 at 18:18