¿Una manera de simplificar $\gcd(a,b)$ condición en una suma doble?

Question

Tengo

$$\sum_{{\Large 1 \leq a,b \leq L} \atop {\Large \gcd(a,b)=1}}(L+1-a)(L+1-b)$$

Que significa recorrer $1 \le a \le L$ y $1 \le b \le L$ y sólo añadiendo $(L+1-a)(L+1-b)$ a la suma si $a$ y $b$ son coprimos.

¿Hay una manera más rápida que no $O(N^2)$? Sé cómo contar cuántos pares de coprimos allí están bajo un límite pero no se como tener en cuenta el $a$ y $b$ y cómo contribuyen a la suma

Answer 1

Bueno, se podría simplificar como sigue:\begin{align} \sum_{{\Large 1 \leq a,b \leq L} \atop {\Large \gcd(a,b)=1}}{(L+1-a)(L+1-b)}& =L^2+2 \cdot \left(\sum_{{\Large 1 \leq b<a \leq L} \atop {\Large \gcd(a,b)=1}}{(L+1-a)(L+1-b)}\right) \\ & =L^2+2 \cdot \left(\sum_{\Large 2 \leq a \leq L}{(L+1-a)\sum_{{\Large 1 \leq b<a} \atop {\Large \gcd(a,b)=1}}{(L+1-b)}}\right) \\ & =L^2+2 \cdot \left(\sum_{\Large 2 \leq a \leq L}{(L+1-a)\left((L+1)\varphi{(a)}-\frac{a\varphi{(a)}}{2}\right)}\right) \\ & =L^2+2\cdot \left(\sum_{\Large 2 \leq a \leq L}{(L+1-a)\left(L+1-\frac{a}{2}\right)\varphi{(a)}} \right) \end {Alinee el}

Ahora basta con sumar $a$. ¿Es que lo suficientemente rápido como para usted?

Edición: Una forma simple de calcular de forma recursiva sería $\varphi{(a)}$ $2 \leq a \leq L$ generar la secuencias de Farey $F_n$ hasta $n=L$ y tomar la diferencia del número de términos de secuencias sucesivas en el camino: $|F_a|-|F_{a-1}|=\varphi{(a)}$