Detailed mathematical approach

Problem Summary

For a positive integer \(n\), the perfection quotient is \(\sigma(n)/n\), where \(\sigma(n)\) is the sum of the positive divisors of \(n\). The task is to sum every \(n \le 10^{18}\) whose perfection quotient is a half-integer. For the bound used here, the implementations split the search into the six target values

$\frac{3}{2},\ \frac{5}{2},\ \frac{7}{2},\ \frac{9}{2},\ \frac{11}{2},\ \frac{13}{2}.$

A direct scan up to \(10^{18}\) is hopeless. The successful strategy is to build \(n\) prime-power by prime-power, while tracking an exact residual quotient that measures how far the current partial factorization is from the chosen target.

Mathematical Approach

Fix one target value \(T=\frac{A}{2}\). We want all integers \(n\) satisfying

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

The quotient factors cleanly over prime powers

If

$n=\prod_i p_i^{e_i},$

then multiplicativity gives

$\sigma(n)=\prod_i \sigma(p_i^{e_i}),\qquad \frac{\sigma(n)}{n}=\prod_i \frac{\sigma(p_i^{e_i})}{p_i^{e_i}}.$

For a single prime power,

$\sigma(p^e)=1+p+p^2+\cdots+p^e=\frac{p^{e+1}-1}{p-1},$

so its contribution to the perfection quotient is

$\frac{\sigma(p^e)}{p^e}=1+\frac1p+\frac1{p^2}+\cdots+\frac1{p^e}.$

This is always greater than 1. Therefore every time we append a new prime power to \(n\), the quotient \(\sigma(n)/n\) increases, and the reciprocal quantity \(n/\sigma(n)\) decreases.

The residual quotient is the real search invariant

Instead of testing \(\sigma(n)/n\) from scratch at every node, the search keeps the reduced residual quotient

$Q(n)=T\frac{n}{\sigma(n)}=\frac{u}{v},\qquad \gcd(u,v)=1.$

At the root, \(n=1\), so \(Q(1)=T\). If we extend the current partial factorization by a new prime power \(p^e\), then

$Q(np^e)=Q(n)\cdot \frac{p^e}{\sigma(p^e)}.$

Since \(\sigma(p^e)/p^e>1\), each update multiplies \(Q\) by a factor strictly smaller than 1. The target condition becomes

$Q(n)=1 \iff T\frac{n}{\sigma(n)}=1 \iff \frac{\sigma(n)}{n}=T.$

So the entire search is a controlled descent from \(Q=T\) down to \(Q=1\).

Why the denominator forces the next prime

Assume the current state is \(Q(n)=u/v\) in lowest terms, and suppose that some unused cofactor \(m\) finishes the construction. Then

$1=Q(n)\frac{m}{\sigma(m)}=\frac{u}{v}\frac{m}{\sigma(m)},$

which is equivalent to

$u\,m=v\,\sigma(m).$

Because \(\gcd(u,v)=1\), this forces

$v \mid m.$

That divisibility is the key invariant. Every prime that appears in the current denominator must still appear later in the unfinished part of the number. Let \(p\) be the smallest prime divisor of \(v\). Then any completion must contain some power \(p^e\), so the recursion branches only on that prime \(p\).

There is also a lower bound on the exponent. If \(p^a \mid v\), then the new numerator must contribute at least \(p^a\) in order to cancel that denominator power after reduction. But in the update factor

$\frac{p^e}{\sigma(p^e)},$

the only source of \(p\)-adic valuation in the numerator is \(p^e\) itself, because \(\sigma(p^e)\equiv 1 \pmod p\). Therefore the branch must start at \(e \ge a\).

Canonical prime order avoids duplicate factorizations

Once a prime has been inserted into the current partial factorization, the search never comes back to that prime later. This is not an arbitrary restriction. If a valid solution contains \(p^e\), then that full exponent must be chosen precisely when the denominator first forces the prime \(p\). Revisiting \(p\) later would only recreate the same final number in a different order. The recursion therefore explores each admissible exponent exactly once, in a canonical order dictated by the changing denominator of \(Q\).

Two strong pruning rules come directly from the invariant

First, if the reduced residual quotient satisfies \(u<v\), then \(Q(n)<1\). From that point onward every extra prime power multiplies by another factor \(p^e/\sigma(p^e)<1\), so the branch can only move farther below 1. Such a branch is already lost.

Second, the divisibility \(v\mid m\) implies \(m\ge v\). Hence every completion \(N=nm\) satisfies

$N \ge n\,v.$

So whenever \(n\,v>10^{18}\), no completion can stay inside the problem limit, and the branch can be discarded immediately.

There is also monotonicity inside a fixed prime loop. For one prime \(p\), the factor

$\frac{p^e}{\sigma(p^e)}=\frac{1}{1+\frac1p+\cdots+\frac1{p^e}}$

decreases as \(e\) grows. Therefore, once a chosen exponent pushes the reduced residual below 1, larger exponents cannot repair the branch, so the loop may stop at once.

Worked example: reaching the target \(5/2\)

Take \(T=\frac52\). Start from

$Q(1)=\frac52.$

The denominator is 2, so the next forced prime is \(2\). Choose the exponent \(e=3\). Then

$Q(2^3)=\frac52\cdot\frac{8}{1+2+4+8}=\frac52\cdot\frac{8}{15}=\frac43.$

Now the denominator is 3, so the next forced prime is \(3\). Taking exponent \(e=1\) gives

$Q(2^3\cdot 3)=\frac43\cdot\frac{3}{1+3}=\frac43\cdot\frac34=1.$

Thus

$\frac{\sigma(24)}{24}=\frac52,$

so \(24\) is a valid term. This example shows the exact rhythm of the search: read the denominator, force its smallest prime, try admissible exponents, reduce the residual quotient, and repeat until either \(Q=1\) or a pruning rule fires.

How the Code Works

The C++, Python, and Java implementations follow the same number-theoretic plan. They solve the six target quotients independently and add the six partial sums.

Residual states and denominator factorization

Each recursive state stores the current partial number together with the reduced numerator and denominator of \(Q\). To keep the denominator-driven search fast, the implementations repeatedly ask for the smallest prime factor of the current denominator. Those denominators can still be large 64-bit integers, so primality is tested with deterministic Miller-Rabin bases, and composite denominators are split with Pollard-Rho. A small cache avoids refactoring the same denominator many times.

Depth-first search over forced prime powers

At each node, the implementation extracts the smallest prime dividing the current denominator and counts its multiplicity. It then walks through exponents starting at that multiplicity, while updating \(p^e\), \(\sigma(p^e)\), and the reduced residual quotient. The branch stops as soon as one of the mathematical impossibility tests is triggered: the partial number exceeds the limit, the residual quotient drops below 1, or the lower bound \(n\,v\le 10^{18}\) fails.

The implementation also rejects any attempt to reuse a prime that is already present in the partial factorization. That enforces the canonical prime order and removes duplicates automatically.

Independent target searches and parallel execution

The six half-integer targets are independent tasks, so they can be processed separately. The compiled implementations distribute them across worker threads, and the Python implementation uses multiple processes when possible. The arithmetic logic is the same in all three languages; only the surrounding execution model differs.

Complexity Analysis

There is no simple closed-form running time, because the algorithm is a heavily pruned search tree rather than a regular table-filling recurrence. The practical cost is determined by how many residual states survive the pruning rules and by how expensive it is to factor the denominators that appear along those states.

Memory use is modest. The recursion depth is the number of distinct primes chosen on the current branch, and the auxiliary storage is mainly a cache of previously factored denominators plus a few larger integer temporaries for overflow-safe arithmetic. The main gain is structural: instead of iterating through all \(10^{18}\) candidates, the search visits only states that are compatible with the exact divisor-sum constraints.

Footnotes and References

1. Project Euler problem page: https://projecteuler.net/problem=241
2. Divisor function: Wikipedia - Divisor function
3. Multiplicative function: Wikipedia - Multiplicative function
4. Pollard's rho algorithm: Wikipedia - Pollard's rho algorithm
5. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test