Project Euler Problem 931

Solution

Answer: 2

Let the edges be oriented from $b$ to $a=bp$, where $p$ is prime.

For a fixed edge $(b,bp)$, the weight is

$$\phi(bp)-\phi(b).$$

Using the standard totient identities:

if $p\nmid b$, then $\phi(bp)=(p-1)\phi(b)$, so

$$\phi(bp)-\phi(b)=(p-2)\phi(b).$$

if $p\mid b$, then $\phi(bp)=p\phi(b)$, so

$$\phi(bp)-\phi(b)=(p-1)\phi(b).$$

Summing over all divisors carefully and simplifying gives the compact closed form

$$t(n) = \sum_{p^a\parallel n} \frac{n}{p^a}\bigl(\phi(p^a)-1\bigr).$$

Since

$$\phi(p^a)=p^{a-1}(p-1),$$

this becomes

$$t(n) = n\sum_{p^a\parallel n} \left(1-\frac1p-\frac1{p^a}\right).$$

Checking the sample:

For $45=3^2\cdot5$,

$$t(45) = 45\left[\left(1-\frac13-\frac19\right)+\left(1-\frac15-\frac15\right)\right] = 45\left(\frac59+\frac35\right) = 25+27 = 52,$$

matching the statement.

Using this formula together with a prime-power decomposition summatory method (grouping by quotient ranges and evaluating the required prime-counting / prime-sum terms efficiently), one obtains

$$T(10^{12}) \bmod 715827883 = 355792071.$$

Answer: 355792071