Detailed mathematical approach

Problem Summary

Define

$g(n)=\sum_{i=1}^{n}(-1)^i\gcd(n,i^2),\qquad G(N)=\sum_{n=1}^{N} g(n).$

For the actual problem, \(N=12{,}345{,}678\). Computing every \(\gcd(n,i^2)\) directly would require a quadratic amount of work, so the implementation rewrites the alternating sum as a divisor sum with a multiplicative weight.

Mathematical Approach

The key is to transform the inner alternating gcd sum into something that depends only on divisors of \(n\), and then to package those divisor contributions into a multiplicative arithmetic function.

Step 1: Expand the GCD with Euler's Totient Identity

For any positive integers \(u\) and \(v\),

$\gcd(u,v)=\sum_{d\mid \gcd(u,v)} \varphi(d).$

Applying this to \(u=n\) and \(v=i^2\) gives

$g(n)=\sum_{i=1}^{n}(-1)^i\sum_{\substack{d\mid n\\ d\mid i^2}} \varphi(d).$

Interchanging the order of summation yields

$g(n)=\sum_{d\mid n}\varphi(d)\,S_d(n),$

where

$S_d(n)=\sum_{\substack{1\le i\le n\\ d\mid i^2}} (-1)^i.$

So the problem is reduced to understanding the sign pattern of those \(i\) for which \(d\mid i^2\).

Step 2: Replace \(d\mid i^2\) by a Simpler Divisibility Condition

Write

$d=\prod_{p^{e_p}\parallel d} p^{e_p}.$

The condition \(d\mid i^2\) means \(e_p\le 2v_p(i)\) for every prime \(p\), so it is equivalent to

$v_p(i)\ge \left\lceil \frac{e_p}{2}\right\rceil \quad \text{for all } p\mid d.$

Define

$\rho(d)=\prod_{p^{e_p}\parallel d} p^{\lceil e_p/2\rceil}.$

This is the smallest positive integer whose square is divisible by \(d\). Then

$d\mid i^2 \iff \rho(d)\mid i.$

Because \(\rho(d)\mid d\) and \(d\mid n\), we also have \(\rho(d)\mid n\). Therefore

$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^{\rho(d)k}.$

Step 3: Separate Odd and Even Divisors

The parity of \(\rho(d)\) is the same as the parity of \(d\), so two different cases appear.

If \(d\) is even, then \(\rho(d)\) is even, every sign is \(+1\), and

$S_d(n)=\frac{n}{\rho(d)}.$

If \(d\) is odd, then \(\rho(d)\) is odd, so

$S_d(n)=\sum_{k=1}^{n/\rho(d)} (-1)^k=\begin{cases} 0, & n \text{ even},\\ -1, & n \text{ odd}. \end{cases}$

Indeed, dividing by an odd number preserves parity, so \(n/\rho(d)\) has the same parity as \(n\).

For odd \(n\), all divisors of \(n\) are odd, hence

$g(n)=-\sum_{d\mid n}\varphi(d)=-n,$

using the standard identity \(\sum_{d\mid n}\varphi(d)=n\). For even \(n\), the odd-divisor contribution vanishes. Thus

$g(n)= -n\,\mathbf{1}_{n\text{ odd}}+\sum_{\substack{d\mid n\\ d\text{ even}}}\varphi(d)\frac{n}{\rho(d)}.$

Step 4: Package the Even Part into a Multiplicative Weight

It is convenient to rewrite the even-divisor term as a divisor sum of \(n/d\). Define

$a(d)=\frac{\varphi(d)\,d}{\rho(d)}.$

Then

$\varphi(d)\frac{n}{\rho(d)}=a(d)\frac{n}{d},$

so the formula becomes

$g(n)= -n\,\mathbf{1}_{n\text{ odd}}+\sum_{\substack{d\mid n\\ d\text{ even}}} a(d)\frac{n}{d}.$

The function \(a\) is multiplicative because both \(\varphi(d)\) and \(d/\rho(d)\) are multiplicative. For a prime power \(p^e\),

$a(p^e)=\frac{\varphi(p^e)p^e}{p^{\lceil e/2\rceil}}=(p-1)p^{\lfloor 3e/2\rfloor-1}.$

Equivalently,

$a\bigl(p^{2t-1}\bigr)=(p-1)p^{3t-3},\qquad a\bigl(p^{2t}\bigr)=(p-1)p^{3t-1}.$

This immediately gives the recurrence used by the implementations: when a new prime \(p\) is attached, multiply by \(p-1\); when the exponent of the current smallest prime increases, multiply by \(p\) if the new exponent is odd and by \(p^2\) if the new exponent is even.

Step 5: Sum Over All \(n\le N\)

Now sum the formula for \(g(n)\) from \(1\) to \(N\). The odd baseline contributes

$\sum_{\substack{1\le n\le N\\ n\text{ odd}}} n = 1+3+\cdots +(2\lceil N/2\rceil-1)=\left\lceil \frac N2\right\rceil^2.$

For a fixed even divisor \(d\), write \(n=dm\). Then

$\sum_{\substack{1\le n\le N\\ d\mid n}} \frac{n}{d}=\sum_{m=1}^{\lfloor N/d\rfloor} m=\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.$

Therefore

$\boxed{G(N)=-\left\lceil \frac N2\right\rceil^2+\sum_{\substack{2\le d\le N\\ d\text{ even}}} a(d)\,\frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}{2}.}$

This is the exact formula evaluated by the implementation.

Worked Example: \(N=4\)

From the original definition,

$g(4)=-\gcd(4,1)+\gcd(4,4)-\gcd(4,9)+\gcd(4,16)=-1+4-1+4=6.$

The divisor formula gives the same result. The even divisors of \(4\) are \(2\) and \(4\). Here

$\rho(2)=2,\quad a(2)=\frac{\varphi(2)\cdot 2}{2}=1,$

$\rho(4)=2,\quad a(4)=\frac{\varphi(4)\cdot 4}{2}=4.$

Since \(4\) is even, there is no odd baseline term, and

$g(4)=a(2)\frac{4}{2}+a(4)\frac{4}{4}=1\cdot 2+4\cdot 1=6.$

For the cumulative sum,

$G(4)=g(1)+g(2)+g(3)+g(4)=-1+1-3+6=3.$

The closed form matches this exactly:

$G(4)=-\left\lceil \frac 42\right\rceil^2+a(2)\frac{2\cdot 3}{2}+a(4)\frac{1\cdot 2}{2}=-4+3+4=3.$

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline. First they build a linear sieve that records the least prime factor of every integer up to \(N\). That makes it possible to derive the factorization of each new integer from the already processed quotient obtained after removing one least prime factor.

During the same pass, the implementation evaluates the multiplicative weight \(a(d)\) for every \(d\le N\). If the least prime factor appears for the first time, the new prime-power contribution is \(p-1\). If that same prime factor continues an existing prime power, the parity of the updated exponent determines whether the multiplier is \(p\) or \(p^2\). This incremental rule is just the prime-power formula above written in a sieve-friendly form.

After the weight table is complete, the final accumulation starts from the baseline \(-\lceil N/2\rceil^2\). Then it loops over even \(d\), computes \(m=\lfloor N/d\rfloor\), adds \(a(d)\,m(m+1)/2\), and obtains the required value of \(G(N)\) without ever evaluating the original double sum directly.

Complexity Analysis

The least-prime-factor sieve is linear, and the weight table is filled in the same linear pass, so the preprocessing cost is \(O(N)\). The final summation over even \(d\) is also \(O(N)\). The overall running time is therefore \(O(N)\), and the memory usage is \(O(N)\) for the sieve data and the coefficient table.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=795
2. Greatest common divisor: Wikipedia — Greatest common divisor
3. Euler's totient function: Wikipedia — Euler's totient function
4. Multiplicative functions: Wikipedia — Multiplicative function
5. Linear sieve for least prime factors: cp-algorithms — Linear Sieve