Detailed mathematical approach

Problem Summary

We must evaluate

$S(N)=\sum_{n=2}^{N}\gcd(n,n'),$

where \(n'\) is the arithmetic derivative, defined by \(p'=1\) for every prime \(p\) and by the product rule \((ab)'=a'b+ab'\). For \(n=\prod p^{e_p}\), this implies

$n'=n\sum_{p^{e_p}\parallel n}\frac{e_p}{p}.$

The target value uses \(N=5\times 10^{15}\), so factoring every integer up to \(N\) is completely infeasible. The solution therefore turns \(\gcd(n,n')\) into a multiplicative quantity and sums it by grouping integers according to their repeated prime factors.

Mathematical Approach

Write

$g(n)=\gcd(n,n').$

The whole problem is to compute \(\sum_{n\le N} g(n)\) and then exclude \(n=1\).

Step 1: Find the Local Prime-Power Factor

Fix a prime \(p\), and write \(n=p^e m\) with \(p\nmid m\). Using the product rule,

$n'=(p^e m)'=e\,p^{e-1}m+p^e m'=p^{e-1}(e\,m+p\,m').$

Because \(m\) is not divisible by \(p\), the \(p\)-adic valuation of \(n'\) behaves in a simple way:

$v_p(n')=\begin{cases} e-1,& p\nmid e,\\ \ge e,& p\mid e. \end{cases}$

Therefore the \(p\)-part of \(\gcd(n,n')\) is

$v_p(g(n))=\min\!\bigl(e,v_p(n')\bigr)=\begin{cases} e-1,& p\nmid e,\\ e,& p\mid e. \end{cases}$

Equivalently, for one prime power,

$g(p^e)=\begin{cases} p^{e-1},& p\nmid e,\\ p^e,& p\mid e. \end{cases}$

Since each prime valuation is determined independently, \(g\) is multiplicative:

$g(n)=\prod_{p^e\parallel n} g(p^e).$

Step 2: Separate the Powerful Part from the Squarefree Tail

If a prime appears only once, then \(g(p)=1\). So primes of exponent \(1\) do not change \(g(n)\). This suggests writing every integer uniquely as

$n=u\,s,$

where \(u\) is the product of all prime powers \(p^e\) with \(e\ge 2\), and \(s\) is the product of the remaining primes of exponent \(1\).

Then:

$u \text{ is powerful},\qquad s \text{ is squarefree},\qquad \gcd(s,u)=1,$

and, crucially,

$g(n)=g(u).$

If we define the radical of \(u\) by

$\operatorname{rad}(u)=\prod_{p\mid u} p,$

then for each fixed powerful part \(u\), the admissible tails are exactly the squarefree integers \(s\le N/u\) that are coprime to \(\operatorname{rad}(u)\). Hence

$S(N)+1=\sum_{\substack{u\le N\\ u\ \mathrm{powerful}}} g(u)\,Q\!\left(\left\lfloor\frac{N}{u}\right\rfloor,\operatorname{rad}(u)\right),$

where

$Q(x,r)=\#\{\,s\le x:\ s\text{ is squarefree and }\gcd(s,r)=1\,\}.$

The extra \(1\) comes from \(n=1\), which is handled separately at the end.

Step 3: Count the Squarefree Coprime Tail

The indicator of squarefreeness is

$1_{\mathrm{sqf}}(s)=\sum_{d^2\mid s}\mu(d),$

so Möbius inversion gives

$Q(x,r)=\sum_{\substack{d\le \sqrt{x}\\ \gcd(d,r)=1}}\mu(d)\,\Phi_r\!\left(\left\lfloor\frac{x}{d^2}\right\rfloor\right),$

where \(\Phi_r(y)\) counts integers up to \(y\) that are coprime to \(r\):

$\Phi_r(y)=\#\{\,m\le y:\gcd(m,r)=1\,\}.$

Because \(r=\operatorname{rad}(u)\) is squarefree, inclusion-exclusion over the primes dividing \(r\) gives

$\Phi_r(y)=\sum_{t\mid r}\mu(t)\left\lfloor\frac{y}{t}\right\rfloor.$

This is the exact counting formula used by the full implementation: one outer Möbius sum for squarefree numbers, and one inner divisor sum for the coprimality condition.

Step 4: Enumerate All Powerful Parts Efficiently

Every powerful number can be built by choosing distinct primes and assigning each chosen prime an exponent at least \(2\). A depth-first search over increasing primes therefore visits each powerful part \(u\le N\) exactly once.

At each node, the algorithm knows three pieces of information:

\(u\) itself, the already accumulated value \(g(u)\), and the prime set of \(\operatorname{rad}(u)\). With those data, it immediately adds

$g(u)\,Q\!\left(\left\lfloor\frac{N}{u}\right\rfloor,\operatorname{rad}(u)\right)$

to the answer, then extends \(u\) by appending a new prime with exponent \(2,3,4,\dots\) as long as the product stays within \(N\).

The shorter implementations encode the same idea in an equivalent telescoping recursion. If \(G_e(p)=g(p^e)\), then each increase

$\Delta_e(p)=G_e(p)-G_{e-1}(p)$

is multiplied by the number of integers whose powerful part first acquires the exponent \(e\) at that prime, and the recursion continues with larger primes only. This compact recursion and the explicit \(Q(x,r)\) formulation compute the same sum.

Worked Example: \(N=20\)

The powerful parts not exceeding \(20\) are

$1,\ 4,\ 8,\ 9,\ 16.$

Now count the squarefree tails for each one:

$\begin{aligned} u=1&:&&g(u)=1,\quad Q(20,1)=13,&&\text{contribution }13,\\ u=4&:&&g(u)=4,\quad Q(5,2)=3,&&\text{contribution }12,\\ u=8&:&&g(u)=4,\quad Q(2,2)=1,&&\text{contribution }4,\\ u=9&:&&g(u)=3,\quad Q(2,3)=2,&&\text{contribution }6,\\ u=16&:&&g(u)=16,\quad Q(1,2)=1,&&\text{contribution }16. \end{aligned}$

Therefore

$\sum_{n=1}^{20} g(n)=13+12+4+6+16=51,$

so after removing the \(n=1\) term we get

$\sum_{n=2}^{20}\gcd(n,n')=50.$

This small checkpoint matches the multiplicative formula perfectly.

How the Code Works

The C++, Python, and Java implementations all begin from the same prime-power formula for \(g(p^e)\). The C++ implementation first validates that formula on small ranges, then sieves primes and Möbius values up to \(\sqrt{N}\). It enumerates powerful parts by depth-first search and, for each one, counts squarefree coprime tails with the Möbius-plus-inclusion-exclusion formula above. The same file also contains a more compact equivalent recursion, and that is the version mirrored by the Python and Java implementations: they recurse over increasing primes, let the exponent at one prime grow from \(2\) upward, and whenever the local factor of \(g\) increases they add that increment times the number of admissible remaining multiples. All three languages therefore compute the same decomposition, just with different levels of explicit counting infrastructure.

Complexity Analysis

Let \(M=\lfloor\sqrt{N}\rfloor\). The sieve stage costs \(O(M\log\log M)\) time and \(O(M)\) memory. The search space of powerful numbers is sparse: there are far fewer powerful integers up to \(N\) than ordinary integers, so the recursion visits only a tiny fraction of the interval \([1,N]\). For each visited powerful part, the squarefree-coprime count sums over squarefree \(d\le \sqrt{N/u}\), while the inner inclusion-exclusion runs over divisors of \(\operatorname{rad}(u)\), whose prime support is small. In practice this is many orders of magnitude faster than iterating over every \(n\le N\), which is why \(N=5\times 10^{15}\) becomes feasible.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=484
2. Arithmetic derivative: Wikipedia - Arithmetic derivative
3. Möbius function: Wikipedia - Möbius function
4. Squarefree integer: Wikipedia - Squarefree integer
5. Inclusion-exclusion principle: Wikipedia - Inclusion-exclusion principle