Contando números libres cuadrados co-prime a$m$

Question

Contando los cuadrados de los números gratuitos $\le N$ es un problema clásico que puede ser resuelto mediante la inclusión-exclusión problema o utilizando la función de Möbius (http://oeis.org/A071172).

Quiero contar los cuadrados de los números gratuitos están co-prime a un determinado número de $m$ dentro de un límite. Deje $C(N, m)$ = no. de los cuadrados de los números gratuitos $\le N$ y co-prime a $m$.

Ejemplo: $C(10,2)=4$ [4 tales números son el 1, 3, 5, 7]

¿Cómo puedo calcular esto para cualquier $m$ eficiente?

Como se mencionó en el comentario, $$C(N,m)=\sum_{n=1}^{N}\mu^{2}(n)(1-sgn(gcd(m,n)-1))$$ Donde $\mu (n)=$ Möbius función, $sgn()=$ Signo de la función.

Se puede calcular la suma de $O(\sqrt n)$? O tal vez el uso de la inclusión-exclusión en el principio?

Answer 1

Lo que sigue no coincide con la pregunta exactamente, pero puede ser interesante saber.

Observe que la de Dirichlet de la serie de la función de indicador de squarefree números es $$L(s) = \prod_p \left(1+\frac{1}{p^s}\right).$$

Si se supone para ser co-prime con $m$ tenemos $$L(s) = \prod_{p|m} \frac{1}{1+\frac{1}{p^s}} \prod_p \left(1+\frac{1}{p^s}\right).$$

Este es $$\prod_{p|m} \frac{1}{1+\frac{1}{p^s}} \prod_p \frac{1-1/p^{2}}{1-1/p^s} \\ = \prod_{p|m} \frac{1}{1+\frac{1}{p^s}} \frac{\zeta(s)}{\zeta(2s)}.$$

Con el polo dominante en $s=1$ ser simple tenemos por el Wiener-Ikehara teorema de para el número de squarefree enteros positivos co-prime a $m$ el asintótica

$$\sum_{n\le x, \; \gcd(m,n)=1, \; p^2\no\mediados n} 1 \sim \prod_{p|m} \frac{1}{1+\frac{1}{p}} \frac{1}{\zeta(2)} x \\ = \frac{6}{\pi^2} x \prod_{p|m} \frac{1}{1+\frac{1}{p}} \\ = \frac{6}{\pi^2} x \prod_{p|m} \frac{p}{p+1}.$$

Esta aproximación es muy precisa. Por ejemplo, se da por $x=3000$ $m=6$ $911.8906524$ , mientras que la respuesta correcta es $911.$ $x=4000$ $m=10$ Da $1350.949114$ con la correcta la respuesta se $1349.$ Finalmente, para $x=5000$ $m=30$ tenemos $1266.514795$ con la respuesta correcta es $1267.$