---
tags: number-theory, mobius-function, mobius-inversion, gcd, lcm, coprimes, dirichlet-convolution, multiplicative-functions, sum-multiplicative-function, sublinear
---

# Aplicaciones de la función de Möbius
Recordemos la identidad $(\mu * \textbf{1})(n) = \epsilon(n)$. Escrito de otra forma, lo podemos ver como $\displaystyle \sum_{d|n} \mu(d) = [n==1]$.

## Ejemplos
### Contar pares de coprimos en un rango
Sea $n$ un entero positivo. Entonces lo que queremos es contar cuántos pares de enteros $(a, b)$ hay tales que $1 \leq a, b \leq n$ y $\gcd(a, b) = 1$.

Sea $f(n)$ la respuesta. Entonces, $f(n) = \displaystyle \sum_{a=1}^{n} \sum_{b=1}^{n} [\gcd(a, b) == 1]$. Pero podemos reemplazar la fórmula de inversión de Möbius, por lo tanto:
$$
\begin{align}
f(n) &= \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{d|\gcd(a, b)} \mu(d) \\
&= \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{d=1}^{n} [d | \gcd(a, b)] \mu(d) \\
&= \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{d=1}^{n} [d | a] [d | b] \mu(d) \\
&= \sum_{d=1}^{n} \mu(d) \sum_{a=1}^{n} [d|a] \sum_{b=1}^{n} [d|b] \\
&=\sum_{d=1}^{n} \mu(d) \left( \sum_{a=1}^{n} [d|a] \right)^2 \\
&= \sum_{d=1}^{n} \mu(d) \left\lfloor \dfrac{n}{d} \right\rfloor ^2
\end{align}
$$
Por lo tanto, la complejidad de la solución queda en $O(n)$ si usamos una criba lineal para evaluar la función $\mu$ en el rango $[1, n]$.

### Suma de gcd de pares
Sea $n$ un entero positivo. Ahora lo que queremos es sumar $\gcd(a, b)$ para todo par $(a ,b)$ tal que $1 \leq a, b \leq n$.

Es decir, $f(n) = \displaystyle \sum_{a=1}^{n} \sum_{b=1}^{n} \gcd(a, b)$. Sabemos que $\varphi * \textbf{1} = I$.

Por lo tanto:
$$
\begin{align}
f(n) &= \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{d | \gcd(a, b)} \varphi(d) \\
&= \sum_{d=1}^{n} \varphi(d) \left\lfloor \dfrac{n}{d} \right\rfloor^2
\end{align}
$$

### Generalización
Ahora supongamos que queremos hallar $f(n) = \displaystyle \sum_{a=1}^{n} \sum_{b=1}^{n} h(\gcd(a, b))$, donde $h(n)$ es una función multiplicativa. En los dos ejemplos anteriores, $h$ era igual a $\epsilon$ y a $I$, respectivamente. Entonces:
$$
\begin{align}
f(n) &= \sum_{a=1}^{n} \sum_{b=1}^{n} \sum_{d | \gcd(a,b)} t(d)
\end{align}
$$
Requerimos que $t * \textbf{1} = h$, por lo tanto, $t = h * \mu$. Finalmente:
$$
\begin{align}
f(n) &= \sum_{d=1}^{n} t(d) \left\lfloor \dfrac{n}{d} \right\rfloor^2
\end{align}
$$

### Suma de lcm de pares
Sea $n$ un entero positivo. Ahora lo que queremos es sumar $\text{lcm}(a, b)$ para todo par $(a ,b)$ tal que $1 \leq a, b \leq n$.

Es decir, $f(n) = \displaystyle \sum_{a=1}^{n} \sum_{b=1}^{n} \text{lcm}(a, b)$. Por lo tanto, usando la identidad $\gcd(a, b) \text{lcm}(a, b) = ab$, tenemos que:
$$
\begin{align}
f(n) &= \sum_{a=1}^{n} \sum_{b=1}^{n} \dfrac{ab}{\gcd(a, b)} \\
&= \sum_{a=1}^{n} \sum_{b=1}^{n} ab \cdot \dfrac{1}{\gcd(a, b)}
\end{align}
$$

Podemos definir a $h(n)$ como $h(n) = \dfrac{1}{n}$, por lo tanto:
$$
\begin{align}
f(n) &= \sum_{a=1}^{n} \sum_{b=1}^{n} ab \cdot h(\gcd(a, b)) \\
&= \sum_{a=1}^{n} \sum_{b=1}^{n} ab \sum_{d|\gcd(a, b)} t(d) \\
&= \sum_{a=1}^{n} \sum_{b=1}^{n} ab \sum_{d=1}^{n} [d|a] [d|b] t(d) \\
&= \sum_{d=1}^{n} t(d) \sum_{a=1}^{n} a[d|a] \sum_{b=1}^{n} b[d|b] \\
&= \sum_{d=1}^{n} t(d) \left( \sum_{a=1}^{n} a[d|a] \right)^2
\end{align}
$$

Sea $P_1(n) = \displaystyle \sum_{i=1}^{n} i$ la suma de Gauss. Pero sabemos que $P_1(n) = \dfrac{n(n+1)}{2}$. Entonces:
$$
\begin{align}
f(n) &= \sum_{d=1}^{n} t(d) \left( d \cdot P_1\left( \left\lfloor \dfrac{n}{d} \right\rfloor \right) \right)^2 \\
&= \sum_{d=1}^{n} d^2 t(d) P_1^2\left( \left\lfloor \dfrac{n}{d} \right\rfloor \right)
\end{align}
$$

Finalmente, vemos que $t = h * \mu$, por lo tanto, $t(n) = \displaystyle \sum_{d|n} h(d) \mu \left( \dfrac{n}{d} \right) = \sum_{d|n} \dfrac{1}{d} \mu \left( \dfrac{n}{d} \right)$. Entonces:
$$
\begin{align}
t(p^a) &= \sum_{d | p^a} \dfrac{1}{d} \mu\left( \dfrac{p^a}{d} \right) \\
&= \sum_{i=0}^{a} \dfrac{1}{p^i} \mu \left( \dfrac{p^a}{p^i} \right) \\
&= \sum_{i=0}^{a} \dfrac{1}{p^i} \mu (p^{a-i}) \\
&= \dfrac{1}{p^a} - \dfrac{1}{p^{a-1}}
\end{align}
$$

### Contar pares de coprimos en un arreglo
Sea $a[]$ un arreglo de $n$ enteros positivos. Queremos saber cuántos pares $(i, j)$ existen tales que $1 \leq i, j \leq n$ y $\gcd(a_i, a_j) = 1$.

Entonces, $f(n) = \displaystyle \sum_{i=1}^{n} \sum_{j=1}^{n} [\gcd(a_i, a_j) == 1]$. Por lo tanto:
$$
\begin{align}
f(n) &= \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d | \gcd(a_i, a_j)} \mu(d) \\
&= \sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{d=1}^{MAX} [d | a_i] [d | a_j] \mu(d) \\
&= \sum_{d=1}^{MAX} \mu(d) \sum_{i=1}^{n} [d | a_i] \sum_{j=1}^{n} [d | a_j] \\
&= \sum_{d=1}^{MAX} \mu(d) \left( \sum_{i=1}^{n} [d | a_i] \right)^2 \\
&= \sum_{d=1}^{MAX} \mu(d) (cnt(d))^2
\end{align}
$$

Sea $cnt(d)$ el número de múltiplos de $d$ en el arreglo $a[]$. Sea $freq(x)$ la frecuencia de aparición de $x$ en el arreglo $a[]$. Ambos arreglos se pueden precalcular, el primero con una complejidad de $O(n)$ y el segundo con una complejidad de $O(MAX \log MAX)$. Por lo tanto, logramos una complejidad de $O(MAX \log MAX)$.

**Nota:** todos los ejemplos anteriores se pueden adaptar a su versión con arreglos.

### Generalización a k-tuplas
Sean $n$ y $k$ enteros positivos. Determinar cuántas $k$-tuplas $(a_1, a_2, \ldots, a_k)$ existen tal que $1 \leq a_1, a_2, \ldots, a_k \leq n$ y $\gcd(a_1, a_2, \ldots, a_k) =1$. Entonces:
$$
\begin{align}
f(n) &= \sum_{a_1=1}^{n} \sum_{a_2=1}^{n} \cdots \sum_{a_k=1}^{n} [\gcd(a_1, a_2, \ldots, a_k) == 1] \\
&= \sum_{d=1}^{n} \mu(d) \left\lfloor \dfrac{n}{d} \right\rfloor^k
\end{align}
$$

## Contar números libres de cuadrados en un rango
**Definición:** Un entero positivo $n$ se dice que es *libre de cuadrados* o *square-free* si no tiene factores primos repetidos. Ejemplos: 2, 3, 5, 6, 7, 10, 11, 13, ...

**Problema:** dada una $n$, hallar cuántos números square-free hay en el rango $[1, n]$ ($n \leq 10^{14}$).

Observación: si $x$ es square-free, entonces $\mu(x)=1, -1$.

Por lo tanto, $\displaystyle \sum_{i=1}^{n} \lvert \mu(i) \rvert$ sería la respuesta. La complejidad de esta solución sería $O(n)$ usando una criba lineal.

Otra forma de resolver esto es ir restando a $n$ el número de múltiplos de cada cuadrado perfecto de un primo. Es decir, a $n$ le restamos $\lfloor n/2^2 \rfloor + \lfloor n/3^2 \rfloor + \cdots$. Pero haciendo esto, algunos números serán restados más de una vez, por lo que ahora debemos sumar los múltiplos de los cuadrados de dos primos a la vez, es decir, $\lfloor n/6^2 \rfloor + \lfloor n/10^2 \rfloor + \cdots$. De forma general, restaremos los múltiplos de los cuadrados de productos de un número impar de primos y sumaremos los múltiplos de los cuadrados de productos de un número par de primos.

Entonces, la respuesta sería: $\displaystyle \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu(i) \left\lfloor \dfrac{n}{i^2} \right\rfloor$. La complejidad de esa solución es ahora $O(\sqrt{n})$ usando una criba lineal.

# Función de sumas parciales de una función multiplicativa
Sea $f(n)$ una función multiplicativa. Definimos a $F(n)$ como la *funcion de sumas parciales* de $f(n)$ de la siguiente manera: $F(n) = \displaystyle \sum_{i=1}^{n} f(i)$.

**Definición:** decimos que $\lfloor x \rfloor = y$ si $y$ es el mayor entero menor o igual a $x$. Entonces $y$ es el único entero que satisface $y \leq x < y+1$.

## Harmonic lemma
Sea $h(n) = \displaystyle \sum_{k=1}^{n} f(k) g \left( \left\lfloor \dfrac{n}{k} \right\rfloor \right)$. Una forma de hallar $h(n)$ es simplemente iterando por todos los valores de $k$, logrando una complejidad de $O(n)$.

Otra forma de evaluarla es darnos cuenta que la sucesión $\lfloor n/1 \rfloor$, $\lfloor n/2 \rfloor$, $\ldots$, $\lfloor n/n \rfloor$ solo puede tomar a lo más $O(2 \sqrt{n})$ valores distintos.

Ejemplo:
- Cuando $n=9$, tenemos que:
\begin{align}
h(9) = &f(1)g(9) + f(2)g(4) + f(3)g(3) +\\
&f(4)g(2) + f(5)g(1) + f(6)g(1) + f(7)g(1) + f(8)g(1) + f(9)g(1) \\
&= f(1)g(9) + f(2)g(4) + f(3)g(3) +\\
&[f(4)]g(2) + [f(5) + f(6) + f(7) + f(8) + f(9)]g(1)
\end{align}
Vemos que la suma al parecer se puede dividir en dos partes: la primera está evaluada en $g$ en valores mayores o iguales a $\sqrt{n}$ y la segunda tiene valores en $g$ menores a $\sqrt{n}$. También vemos que la segunda parte de la suma tiende a agrupar términos con el mismo valor de $g$ y varios valores consecutivos de $f$.

- Cuando $n=12$, tenemos que:
\begin{align}
h(12) = &f(1)g(12) + f(2)g(6) + f(3)g(4) + f(4)g(3) \\
&+[f(5)+f(6)]g(2) + [f(7) + \cdots + f(12)]g(1)
\end{align}

- Cuando $n=15$, tenemos que:
\begin{align}
h(15) = &f(1)g(15) + f(2)g(7) + f(3)g(5) + f(4)g(3) + f(5)g(3) \\
&+[f(6)+f(7)]g(2) + [f(8) + \cdots + f(15)]g(1)
\end{align}

Ahora, intentemos deducir una fórmula para hallar de forma más eficiente $h(n)$. Sea $m=\lfloor \sqrt{n} \rfloor$, entonces:

\begin{align}
h(n) &= \sum_{i=1}^{\lfloor n/m \rfloor} f(i) g \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) + \sum_{i=1}^{m-1} \left[ f(l_i) + \cdots + f(r_i) \right] g(i)
\end{align}

La suma $f(l_i) + \cdots + f(r_i)$ se puede reescribir en términos de sumas prefijo como: $F(r_i) - F(l_i-1)$. Ahora, para determinar $l_i$ y $r_i$, entonces se debe de cumplir que $\displaystyle \left \lfloor \dfrac{n}{k} \right \rfloor = i$. Sabemos que $i \leq \dfrac{n}{k} < i+1$, es decir, $k \leq \dfrac{n}{i}$ y $\dfrac{n}{i+1} < k$. Es decir, $\left\lfloor \dfrac{n}{i+1} \right\rfloor + 1 \leq k \leq \left \lfloor \dfrac{n}{i} \right\rfloor$. Por lo tanto, la fórmula queda como:
\begin{align}
h(n) &= \sum_{i=1}^{\lfloor n/m \rfloor} f(i) g \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) + \sum_{i=1}^{m-1} \left[ F\left( \left \lfloor \dfrac{n}{i} \right\rfloor \right) - F\left( \left \lfloor \dfrac{n}{i+1} \right\rfloor \right) \right] g(i)
\end{align}
Ahora, la complejidad de evaluar $h(n)$ se redujo a $O(\sqrt{n})$ gracias al harmonic lemma.

## Sumas parciales de una convolución de Dirichlet
Sean $f(n)$, $g(n)$ y $h(n)$ funciones aritméticas tales que $h(n) =(f * g)(n)$. Entonces, queremos hallar $H(n)$, es decir, la función de sumas parciales de una convolución de Dirichlet.

Es decir, queremos hallar $H(n) = \displaystyle \sum_{i=1}^{n} h(i) = \sum_{i=1}^{n} \sum_{d | i} f(d) g \left( \dfrac{i}{d} \right)$. Reacomodando los términos a sumar, podemos reescribir esa suma como:
\begin{align}
H(n) &= \sum_{i=1}^{n}f(i) G \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right)
\end{align}
Pero como la convolución es conmutativa, también podemos decir que:
\begin{align}
H(n) &= \sum_{i=1}^{n}g(i) F \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right)
\end{align}

### Ejemplo 1
Hallar $H(n) = \displaystyle \sum_{i=1}^{n} \sigma_0(i)$ ($1 \leq n \leq 10^{14}$).

Sabemos que $\sigma_0(n) = \displaystyle \sum_{d | n} 1 = (\textbf{1} * \textbf{1})(n)$. Entonces, aplicando lo anterior, vemos que $f(n)=1$ y $g(n)=1$. Luego, $G(n)=\displaystyle \sum_{i=1}^{n}1 = n$. Por lo tanto:
\begin{align}
H(n) &= \sum_{i=1}^{n} \left\lfloor \dfrac{n}{i} \right\rfloor
\end{align}
Ahora, aplicando el harmonic lemma, tenemos que:
\begin{align}
H(n) &= \sum_{i=1}^{\lfloor n/m \rfloor} \left\lfloor \dfrac{n}{i} \right\rfloor + \sum_{i=1}^{m-1} \left[ \left \lfloor \dfrac{n}{i} \right\rfloor - \left \lfloor \dfrac{n}{i+1} \right\rfloor \right] \cdot i
\end{align}

### Ejemplo 2
Hallar $M(n) = \displaystyle \sum_{i=1}^{n} \mu(i)$ ($1 \leq n \leq 10^{12}$).

Notemos que $\mu * \textbf{1} = \epsilon$. Hallemos ahora las sumas parciales de la función $\epsilon$, es decir, $E(n)$. Por lo tanto, $E(n)=1$. Pero ahora notemos lo siguiente:
\begin{align}
E(n) &= \sum_{i=1}^{n} M \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) \\
1 &= \sum_{i=1}^{n} M \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right)
\end{align}
Ahora, vemos que la suma anterior se puede expandir como $M(n) + M(\lfloor n/2 \rfloor) + \cdots + M(\lfloor n/n \rfloor) = 1$. Una idea podría ser ser despejar la función $M(n)$ en términos de ella misma, es decir, $M(n) = 1 -M(\lfloor n/2 \rfloor) - \cdots - M(\lfloor n/n \rfloor)$:
\begin{align}
M(n) &= 1 - \sum_{i=2}^{n} M \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right)
\end{align}
Ahora, aplicando el harmonic lemma con $f(n)=1$ y $g(n)=M(n)$, tenemos que $F(n)=n$ y
\begin{align}
M(n) &= 1 - \sum_{i=2}^{\lfloor n/m \rfloor} M \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) - \sum_{i=1}^{m-1} \left[ \left \lfloor \dfrac{n}{i} \right\rfloor - \left \lfloor \dfrac{n}{i+1} \right\rfloor \right] M(i)
\end{align}
Para implementar esa función, como es recursiva, podemos memorizar los valores de $M(n)$ para evitar recalcularlos. Esta función recursiva no va a visitar todos los estados del $1$ al $n$, solo visitará los estados $1, 2, \ldots, m$ y $\lfloor n/1 \rfloor, \lfloor n/2 \rfloor, \ldots, \lfloor n/m \rfloor$, es decir, aproximadamente $O(\sqrt{n})$ estados y la memoria también sería $O(\sqrt{n})$.

¿Cuál sería la complejidad en tiempo? Sumemos la complejidad de cada estado de evaluar $M(n)$, vemos que dicha complejidad es $O(\sqrt{n})$. Sumando para todos los estados, tenemos que la complejidad total será:
\begin{align}
&\sum_{i=1}^{\sqrt{n}} \sqrt{i} + \sum_{i=1}^{\sqrt{n}} \sqrt{n/i} \\
&\approx \int_{0}^{\sqrt{n}} \sqrt{x} dx + \int_{0}^{\sqrt{n}} \sqrt{n/x} dx \\
&= \dfrac{2}{3} x^{3/2} |_0^{\sqrt{n}} + 2\sqrt{n}\sqrt{x} |_0^{\sqrt{n}} \\
&= \dfrac{2}{3} n^{3/4} + 2n^{3/4} \\
&= O(n^{3/4})
\end{align}
Pero podemos mejorar aún más la complejidad a $O(n^{2/3})$ si precalculamos con la criba lineal los primeros valores de $M(n)$ hasta $n^{2/3}$.

### Ejemplo 3
Hallar $\Phi(n) = \displaystyle \sum_{i=1}^{n} \varphi(i)$ ($1 \leq n \leq 10^{12}$).

Tenemos que $\varphi * \textbf{1} = I$. Sea $P_1(n)$ la función de sumas parciales de $I(n)$, es decir, $P_1(n) = \displaystyle \sum_{i=1}^{n} i = \dfrac{n(n+1)}{2}$. Ahora, aplicando la función de sumas parciales de una convolución con $f=\varphi$ y $g=\textbf{1}$, tenemos que:
\begin{align}
P_1(n) &= \sum_{i=1}^{n} \Phi \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) \\
\dfrac{n(n+1)}{2} &= \sum_{i=1}^{n} \Phi \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) \\
\Phi(n) &= \dfrac{n(n+1)}{2} - \sum_{i=2}^{n} \Phi \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) \\
\Phi(n) &= \dfrac{n(n+1)}{2} - \sum_{i=2}^{\lfloor n/m \rfloor} \Phi \left( \left\lfloor \dfrac{n}{i} \right\rfloor \right) - \sum_{i=1}^{m-1} \left[ \left \lfloor \dfrac{n}{i} \right\rfloor - \left \lfloor \dfrac{n}{i+1} \right\rfloor \right] \Phi(i)
\end{align}

### Generalización
De forma general, si queremos hallar $F(n) = \displaystyle \sum_{i=1}^{n} f(i)$ y de alguna manera logramos encontrar una función $g(n)$ tal que $h(n) = (f * g)(n)$ y tanto $G(n)$ como $H(n)$ sean fáciles de calcular, podemos hallar $F(n)$ con una complejidad de $O(n^{2/3})$.