Secuencia interesante en el tamaño de las clases de equivalencia coprima

Question

En el transcurso del cálculo de un problema del Proyecto Euler, estaba probando una función y me di cuenta de un patrón extraño.

Tomemos los números naturales $\{2 , 3 , \dots n\}$ . Llame a $a \sim b$ si todos los números naturales coprimos a $a$ también son coprimos de $b$ y viceversa. Es lo mismo que decir que tienen la misma factorización primaria si ignoramos los exponentes.

Llame a $f(n)$ el número de clases de equivalencia $$f(n) = \left|(\{2,3,\dots n\}/\sim) \right|$$

Ejemplo n = 10 : Las clases de equivalencia son $\{\{2,4,8\},\{3,9\},\{6\},\{5\},\{7\},\{10\}\}$

Ejemplo n = 20 : Las clases de equivalencia son $\{\{2,4,8,16\},\{3,9\},\{6,12,18\},\{5\},\{10,20\},\{7\},\{11\},\{13\},\{14\},\{15\},\{17\},\{19\}\}$

Estos son algunos valores de muestra para $f$ para poderes de $10$ :

$$\begin{align} f(10) &= 6 \\ f(100) &= 60 \\ f(1000) &= 607 \\ f(10000) &= 6082 \\ f(100000) &= 60793 \\ f(1000000) &= 607925 \end{align}$$

Llámame supersticioso, pero esto parece un patrón. De hecho, parece la expansión decimal de $6/\pi^2$ .

---

¿Alguien sabe si hay un patrón genuino aquí, y por qué?

Answer 1

Otra forma de pensar $f(n)$ es como el número de números libres de cuadrados por debajo de $n$ ya que hay exactamente un número sin cuadrado en cada una de las clases de equivalencia que describes, y el número sin cuadrado es el elemento más pequeño de cada clase. Por lo tanto, $f(n)/n$ es la fracción de números por debajo de $n$ que son libres de cuadrados.

Para un primo dado $p$ como $n$ llega hasta el infinito, $1-1/p^2$ de los números siguientes $n$ no son divisibles por $p^2$ . Informalmente, la fracción de números por debajo de $n$ no divisible por el cuadrado de ningún primo debe ser aproximadamente $$\prod_{p} (1 - p^{-2}) = \left(\prod_{p} \frac{1}{1 - p^{-2}} \right)^{-1} = \frac{1}{\zeta(2)} = \frac{6}{\pi^2}$$

Answer 2

La respuesta de @BoltonBailey lo explica muy bien. Sólo añadiré algunos detalles triviales sobre el cálculo. De hecho, $n$ es libre de cuadrados si $\mu(n)\not=0$ es decir, $(\mu(n))^2=1$ . Así que $f(n)/n$ se evalúa como $$\begin{align}\frac{f(n)}n & =\frac 1 n \sum_{i\leq n}(\mu(i))^2\\ & = \frac 1 n\sum_{i\leq n}\sum_{d^2\mid i}\mu(d)\\ & =\frac 1 n\sum_{d\leq\sqrt n}\mu(d)\left(\frac{n}{d^2}+O(1)\right)\\ & =\sum_{d\leq\sqrt n}\frac{\mu(d)}{d^2}+O(n^{-1/2})\\ & =\frac 1 {\zeta(2)}+O(n^{-1/2})\end{align}$$

Answer 3

Vaya, quizá debería haber borrado mi pregunta, ya que enseguida vi esta cita en la OEIS (Online Encyclopedia of Integer Sequences):

$6/\pi^2$ es la probabilidad de que dos números elegidos al azar sean coprimos

Sin embargo, esto sigue dejando la cuestión de por qué .