Project Euler Problem 699
Let sigma(n) be the sum of all the divisors of the positive integer n, for example: sigma(10) = 1+2+5+10 = 18.
Solution
Answer: 37010438774467572
Write
$$n=3^a m,\qquad a\ge 1,\qquad (m,3)=1.$$
Because $\sigma$ is multiplicative,
$$\frac{\sigma(n)}{n} = \frac{\sigma(3^a)}{3^a}\cdot \frac{\sigma(m)}{m}.$$
Now
$$\sigma(3^a)=1+3+\cdots+3^a=\frac{3^{a+1}-1}{2}.$$
Define
$$c_a=\frac{3^{a+1}-1}{2}.$$
Since $3\nmid c_a$,
$$\frac{\sigma(n)}{n} = \frac{c_a,\sigma(m)}{3^a m}.$$
The reduced denominator is therefore a power of $3$ iff every prime $p\neq 3$ dividing $m$ cancels against the numerator $c_a\sigma(m)$. Equivalently,
$$m\mid c_a\sigma(m).$$
Thus the problem becomes:
For every $a\ge1$ with $3^a\le N$, enumerate all $m\le N/3^a$, $(m,3)=1$, satisfying
$$m\mid c_a\sigma(m),$$
and sum all $3^a m$.
A DFS over prime powers works efficiently because
$$\sigma(p^e)=\frac{p^{e+1}-1}{p-1},$$
and only primes appearing in the evolving numerator can help cancel denominator factors. Using Pollard–Rho + Miller–Rabin factorisation, the search remains tiny (only a few thousand valid numbers up to $10^{14}$).
The algorithm reproduces the checks:
$$T(100)=270, \qquad T(10^6)=26089287.$$
Carrying the computation through to $10^{14}$ gives:
Answer: 37010438774467572