Solution

Answer: 955892601606483

Let

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

We seek

$$G(N)=\sum_{n=1}^N g(n), \qquad G(12345678).$$

1. Mathematical analysis

Step 1: Expand the gcd using Euler's totient identity

A standard identity is

$$\gcd(a,b)=\sum_{d\mid \gcd(a,b)}\varphi(d).$$

Therefore,

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

Swap the order of summation:

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

Define

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

Then

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

Step 2: Characterize the condition $d\mid i^2$

Write

$$d=\prod p^{a_p}.$$

Then $d\mid i^2$ iff

$$p^{a_p}\mid i^2 \iff p^{\lceil a_p/2\rceil}\mid i.$$

Hence the condition is equivalent to

$$q(d)\mid i,$$

where

$$q(d)=\prod p^{\lceil a_p/2\rceil}.$$

So the valid $i$'s are exactly the multiples of $q(d)$.

Step 3: Evaluate the alternating sum

Case A: $q(d)$ odd

Then the multiples of $q(d)$ alternate parity.

If $n$ is even, there are equally many even and odd multiples, so

$$S(n,d)=0.$$

If $n$ is odd, there is one extra odd term, giving

$$S(n,d)=-1.$$

Thus for odd $n$,

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

(using $\sum_{d\mid n}\varphi(d)=n$).

Case B: $q(d)$ even

Then every multiple of $q(d)$ is even, so every term contributes $+1$.

The number of multiples is

$$\frac{n}{q(d)}$$

(because $q(d)\mid n$ whenever $d\mid n$).

Hence

$$S(n,d)=\frac{n}{q(d)}.$$

This only occurs for even $d$.

Therefore, for even $n$,

$$g(n) = \sum_{\substack{d\mid n\ d\text{ even}}} \varphi(d)\frac{n}{q(d)}.$$

2. Summing to obtain $G(N)$

Split odd and even $n$.

For odd $n$,

$$g(n)=-n.$$

The odd numbers up to $N$ sum to

$$1+3+5+\cdots+(2m-1)=m^2, \quad m=\left\lfloor\frac{N+1}{2}\right\rfloor.$$

So the odd contribution is

$$-\left\lfloor\frac{N+1}{2}\right\rfloor^2.$$

Now handle even $n$:

$$\sum_{\substack{n\le N\ n\text{ even}}}g(n) = \sum_{d\text{ even}\le N} \varphi(d) \sum_{\substack{n\le N\ d\mid n}} \frac{n}{q(d)}.$$

Write $n=dk$. Then

$$= \sum_{d\text{ even}\le N} \frac{\varphi(d)d}{q(d)} \sum_{k\le N/d}k.$$

Since

$$\sum_{k\le m}k=\frac{m(m+1)}2,$$

we get

$$G(N) = -\left\lfloor\frac{N+1}{2}\right\rfloor^2 + \sum_{d\text{ even}\le N} \frac{\varphi(d)d}{q(d)} \cdot \frac{m(m+1)}2,$$

where

$$m=\left\lfloor\frac{N}{d}\right\rfloor.$$

3. Multiplicative coefficient

Define

$$f(d)=\frac{\varphi(d)d}{q(d)}.$$

This is multiplicative.

For a prime power $p^e$,

$$q(p^e)=p^{\lceil e/2\rceil},$$

$$f(p^e) = (p-1)p^{e-1} \cdot p^{e-\lceil e/2\rceil} = (p-1)p^{2e-1-\lceil e/2\rceil}.$$

This allows a linear sieve computation in $O(N)$.

4. Python implementation

from array import array

N = 12345678

# f(n) = phi(n) * n / q(n)
# where q(p^e) = p^ceil(e/2)

f = array('Q', [0]) * (N + 1)
exp = array('B', [0]) * (N + 1)
pp  = array('I', [0]) * (N + 1)

primes = []
f[1] = 1

def local_value(p, e):
    # f(p^e) = (p-1) * p^(2e-1-ceil(e/2))
    return (p - 1) * (p ** (2 * e - 1 - ((e + 1) // 2)))

# Linear sieve
for i in range(2, N + 1):

    if pp[i] == 0:
        primes.append(i)
        pp[i] = i
        exp[i] = 1
        f[i] = local_value(i, 1)

    for p in primes:
        v = i * p

        if v > N:
            break

        if i % p == 0:
            # extend prime power
            pp[v] = pp[i] * p
            exp[v] = exp[i] + 1

            e = exp[v]

            new_local = local_value(p, e)
            old_local = local_value(p, e - 1)

            f[v] = (f[i] // old_local) * new_local
            break

        else:
            # new prime factor
            pp[v] = p
            exp[v] = 1
            f[v] = f[i] * local_value(p, 1)

# Odd contribution
m = (N + 1) // 2
G = -m * m

# Even divisor contribution
for d in range(2, N + 1, 2):
    t = N // d
    G += f[d] * t * (t + 1) // 2

print(G)

5. Code walkthrough

Arrays

f[n] stores

$$f(n)=\frac{\varphi(n)n}{q(n)}.$$

exp[n] stores the exponent of the smallest prime factor.
pp[n] stores the corresponding prime power.

This is the standard structure for a linear sieve.

`local_value(p,e)`

Implements

$$f(p^e)=(p-1)p^{2e-1-\lceil e/2\rceil}.$$

Because $f$ is multiplicative, every value can be built from prime powers.

Final summation

The formula implemented is exactly

$$G(N) = -\left\lfloor\frac{N+1}{2}\right\rfloor^2 + \sum_{d\text{ even}\le N} f(d)\cdot \frac{\lfloor N/d\rfloor(\lfloor N/d\rfloor+1)}2.$$

6. Verification on the given example

The program gives:

$$G(1234)=2194708,$$

matching the problem statement exactly.

It also reproduces:

$$g(4)=6, \qquad g(1234)=1233.$$

7. Final computation

Running the program for

$$N=12345678$$

gives

$$G(12345678)=955892601606483.$$

Answer: 955892601606483

Project Euler Problem 795