Alternating GCD Sum

For a positive integer $n$, the function $g(n)$ is defined as

$$\displaystyle g(n)=\sum_{i=1}^{n} (-1)^i \gcd \left(n,i^2\right)$$

For example, $g(4) = -\gcd \left(4,1^2\right) + \gcd \left(4,2^2\right) – \gcd \left(4,3^2\right) + \gcd \left(4,4^2\right) = -1+4-1+4=6$.
You are also given $g(1234)=1233$.

Let $\displaystyle G(N) = \sum_{n=1}^N g(n)$. You are given $G(1234) = 2194708$.

Find $G(12345678)$.

This is a challenging number theory problem. Here is the solution using a little bit of series manipulation, the principle of inclusion-exclusion, and the theorem of Möbius inversion.

Firstly, let’s simplify $\sum_{i=1}^n (-1)^i \gcd(n,i^2)$.

Notice that for every integer $n$, $g(n)$ only changes values at square integers. More specifically, when $i^2$ crosses a divisor $d$ of $n$, $\gcd(n, i^2)$ changes from $d$ to $n$. So effectually, we can rewrite the function as summing over the divisors of $n$ instead of summing over every integer from $1$ to $n$. We just need to take care whether the sum is positive or negative, depending on whether the divisor is a perfect square.

Now write $g(n)$ as $\sum_{i=1}^n (-1)^{\sqrt{i}} \gcd(n,i)$.

Here, $(-1)^{\sqrt{i}}$ is $-1$ or $1$ depending on whether $i$ is square-free or not. So the function can be written as the difference between the sum of $n$ over the square divisors of $n$ and the sum of $n$ over the non-square divisors of $n$.

That can be written as $\sum_{\substack{d \mid n \\ d \text{ is square}}} n – \sum_{\substack{d \mid n \\ d \text{ is not square}}} n$.

Using the principle of inclusion-exclusion and Möbius inversion formula, the function $g(n)$ simplifies to $n \mu(\sqrt{n})$ where $\mu(x)$ is the Möbius function.

So $g(n)$ equals $n$ if $n$ is a square, $-n$ if $n$ is twice a square, and $0$ otherwise.

We then need to compute $G(N) = \sum_{n=1}^N g(n)$, which is equivalent to substracting the sum of positive integers not exceeding $N$ which are twice a square from the sum of squares not exceeding $N$. This equals $\frac{N(N+1)(2N+1)}{6} – 2\sum_{i=1}^{\lfloor \sqrt{N/2} \rfloor} i^2$.

These sums can be further simplified to closed-form expressions using the formula for the sum of the first $n$ natural numbers ($n(n+1)/2$) and the formula for the sum of the squares of the first $n$ natural numbers ($n(n+1)(2n+1)/6$).

Applying these simplifications, we finally find that the value of $G(12345678)$ is $\frac{12345678 \cdot 12345679 \cdot 24691357}{6} – 2 \cdot \frac{\lfloor \sqrt{12345678/2} \rfloor \cdot (\lfloor \sqrt{12345678/2} \rfloor +1) \cdot (2\lfloor \sqrt{12345678/2} \rfloor +1)}{6}$.

Finally, after evaluating the expression above, you will find the value of $G(12345678)$.

More Answers: