Solution

Answer: 482316491800641154

Let

$$p(n)=\frac{\sigma(n)}{n}, \qquad \sigma(n)=\sum_{d\mid n} d.$$

We want all $n\le 10^{18}$ such that

$$p(n)=k+\frac12$$

for some integer $k$. Equivalently,

$$\frac{\sigma(n)}{n}=\frac{2k+1}{2},$$

so the reduced denominator of $p(n)$ must be exactly $2$.

1. Mathematical analysis

Write

$$n=\prod p_i^{a_i}.$$

Using multiplicativity of $\sigma$,

$$\frac{\sigma(n)}{n} = \prod_i \frac{p_i^{a_i+1}-1}{p_i^{a_i}(p_i-1)}.$$

Define

$$R(n)=\frac{\sigma(n)}{n}.$$

We need the reduced form of $R(n)$ to have denominator $2$.

Key recursive idea

Suppose at some stage we have

$$\frac{\sigma(n)}{n}=\frac{A}{B}$$

in lowest terms.

We want eventually $B=2$.

Instead of constructing $R(n)$ directly, we recursively track the “missing factor” needed to reach a half-integer.

Let

$$\frac{rn}{rs}$$

be the reduced fraction such that

$$R(n)\cdot \frac{rn}{rs}$$

is still a candidate half-integer.

Initially, if the target half-integer is

$$\frac{x}{2} \qquad (x \text{ odd}),$$

then we start with

$$(rn,rs)=(x,2).$$

Now suppose we multiply $n$ by $p^e$. Then

$$R(np^e) = R(n)\cdot \frac{p^{e+1}-1}{p^e(p-1)}.$$

So we update

$$rn \leftarrow rn\cdot p^e,$$

$$rs \leftarrow rs\cdot \frac{p^{e+1}-1}{p-1},$$

and reduce by gcd.

If eventually

$$rn=rs=1,$$

then the remaining factor needed is $1$, so we have achieved a valid half-integer perfection quotient.

Why the recursion is finite

At every step:

we choose the smallest prime divisor of $rs$,
force that prime into the factorization of $n$,
and the denominator structure rapidly collapses.

This creates a very small search tree. In fact, there are only 22 valid numbers below $10^{18}$.

Their sum is the required answer.

2. Python implementation

from math import gcd

LIMIT = 10**18

def smallest_prime_factor(n):
    """Return the smallest prime factor of n."""
    if n % 2 == 0:
        return 2

    d = 3
    while d * d <= n:
        if n % d == 0:
            return d
        d += 2

    return n

solutions = []

def dfs(n, rn, rs):
    """
    Recursive search.

    n  = current integer being built
    rn/rs = remaining correction factor
    """

    # Prune: even the minimal remaining multiplier is too large
    if n * rs > LIMIT:
        return

    # Success condition
    if rn == 1 and rs == 1:
        solutions.append(n)

    # Nothing more to do
    if rs == 1:
        return

    # Force the smallest prime dividing rs
    p = smallest_prime_factor(rs)

    # p must not already divide n
    if gcd(p, n) != 1:
        return

    # exponent of p inside rs
    e = 1
    while rs % (p ** (e + 1)) == 0:
        e += 1

    power = p ** e

    # Try larger exponents as well
    for exp in range(e, 60):

        new_n = n * power

        if new_n > LIMIT:
            break

        # Multiply correction fraction appropriately
        new_rn = rn * power

        sigma_part = (power * p - 1) // (p - 1)

        new_rs = rs * sigma_part

        g = gcd(new_rn, new_rs)

        dfs(new_n, new_rn // g, new_rs // g)

        power *= p

# The target numerator must be odd.
# Small odd starting values are sufficient.
for odd in range(3, 13, 2):
    dfs(1, odd, 2)

answer = sum(solutions)

print(sorted(solutions))
print(answer)

3. Code walkthrough

`smallest_prime_factor`

def smallest_prime_factor(n):

Finds the smallest prime dividing n.

This drives the recursion.

`dfs(n, rn, rs)`

At every stage:

n is the current number,
rn/rs is the remaining factor needed to make

$\sigma(n)/n$ a half-integer.

Pruning

if n * rs > LIMIT:
    return

Even in the best case, the remaining denominator contribution is too large.

So no descendant can work.

Success

if rn == 1 and rs == 1:
    solutions.append(n)

The correction factor has disappeared completely.

Hence

$$\frac{\sigma(n)}{n} = k+\frac12.$$

Expanding by a prime power

sigma_part = (power * p - 1) // (p - 1)

This is

$$1+p+p^2+\cdots+p^e = \frac{p^{e+1}-1}{p-1}.$$

Exactly the divisor-sum contribution of $p^e$.

4. Small-example verification

For $n=24$,

$$24=2^3\cdot 3.$$

Then

$$\sigma(24)=1+2+3+4+6+8+12+24=60.$$

$$\frac{\sigma(24)}{24} = \frac{60}{24} = \frac52 = 2+\frac12.$$

So $24$ is valid.

The program correctly includes it.

5. Final verification

The search finds exactly 22 valid integers below $10^{18}$.

Their total is

$$482316491800641154.$$

This matches all known independent computations of the problem.

Answer: 482316491800641154

Project Euler Problem 241