Detailed mathematical approach

Problem Summary

Define the coresilience of a positive integer by

$C(n)=\frac{n-\varphi(n)}{n-1}.$

Problem 245 asks for the sum of all composite numbers \(n\le 2\cdot 10^{11}\) whose coresilience is a unit fraction. Equivalently, we must find every composite \(n\) for which

$\frac{n-1}{n-\varphi(n)}\in\mathbb Z.$

If we write

$n-1=k(n-\varphi(n)),\qquad k\in\mathbb Z_{\ge 2},$

then \(C(n)=1/k\). A direct sweep up to \(2\cdot 10^{11}\) with explicit totients would be far too slow, so the solution turns this divisibility condition into a structural classification of the admissible composite numbers.

Mathematical Approach

The integer \(k\) is the natural organizing parameter of the search. Rearranging the defining equation gives the invariant

$k\varphi(n)=(k-1)n+1.$

Everything in the final algorithm comes from forcing this identity to coexist with the prime factorization of \(n\).

Squarefree structure is forced

Suppose \(p^2\mid n\) for some prime \(p\). Then \(p\mid n\), and also \(p\mid \varphi(n)\), because the totient of any integer divisible by \(p^2\) still carries a factor of \(p\). Hence \(p\mid n-\varphi(n)\).

But \(n\equiv 0\pmod p\) implies \(n-1\equiv -1\pmod p\), so \(p\nmid n-1\). Therefore \(n-\varphi(n)\) cannot divide \(n-1\). Every valid composite must be squarefree:

$n=p_1p_2\cdots p_r,\qquad \varphi(n)=\prod_{i=1}^{r}(p_i-1).$

This is why the multi-prime branch of the implementation only builds products of distinct primes.

Every prime factor must be larger than \(k\)

From \(k\varphi(n)=(k-1)n+1\) we obtain

$\frac{n}{\varphi(n)}=\frac{k}{k-1}-\frac{1}{(k-1)\varphi(n)}\lt\frac{k}{k-1}.$

Because \(n\) is squarefree,

$\frac{n}{\varphi(n)}=\prod_{p\mid n}\frac{p}{p-1}.$

The function \(x\mapsto \frac{x}{x-1}\) decreases for \(x\gt 1\). If some prime divisor satisfied \(p\le k\), then

$\frac{p}{p-1}\ge \frac{k}{k-1},$

and multiplying by the remaining factors, all of which are \(\gt 1\), would force \(\frac{n}{\varphi(n)}\) to be at least \(\frac{k}{k-1}\), contradicting the previous inequality. Hence

$p_i\gt k.$

This immediately explains the two main search bounds. If \(n=pq\), then \(n\gt (k+1)^2\), so only \(k\le \sqrt{L}\) can contribute. If \(n\) has at least three prime factors, then \(n\gt (k+1)^3\), so only \(k\lt \sqrt[3]{L}\) need be explored in that branch.

The semiprime case becomes a divisor-pair problem

Let \(n=pq\) with distinct primes \(p\) and \(q\). Then

$\varphi(n)=(p-1)(q-1)=pq-p-q+1,$

so

$n-\varphi(n)=pq-(pq-p-q+1)=p+q-1.$

Substituting into \(n-1=k(n-\varphi(n))\) gives

$pq-1=k(p+q-1).$

Rearranging yields

$pq-kp-kq+k^2=k^2-k+1,$

hence

$\boxed{(p-k)(q-k)=k^2-k+1.}$

Now define

$K(k)=k^2-k+1.$

Every semiprime solution for that \(k\) comes from a divisor pair \(ab=K(k)\):

$p=k+a,\qquad q=k+b.$

So the semiprime stage reduces to factoring \(K(k)\), enumerating its divisor pairs, shifting them by \(k\), and testing primality.

Sieving the polynomial \(k^2-k+1\)

Factoring each \(K(k)\) independently would still be too expensive. The implementations instead sieve the polynomial values arithmetically. If an odd prime \(r\) divides \(K(k)\), then

$k^2-k+1\equiv 0\pmod r\iff (2k-1)^2\equiv -3\pmod r.$

Therefore \(k\) must lie in one of the residue classes

$k\equiv \frac{1\pm \sqrt{-3}}{2}\pmod r.$

For \(r=3\), this collapses to the single class \(k\equiv 2\pmod 3\). For other odd primes, a square root of \(-3\) exists only when the prime is in the right quadratic-residue class, which here means \(r\equiv 1\pmod 3\). That is why the sieve skips \(2\) and all primes \(r\equiv 2\pmod 3\), and uses Tonelli-Shanks only for the relevant primes to recover the admissible residue classes. Once those classes are known, the prime powers are stripped from every matching \(K(k)\), producing the factor tables used later to generate all divisor pairs.

For three or more primes, the last prime is determined explicitly

Now consider a squarefree candidate with at least three prime factors. Suppose we have already chosen distinct primes \(q_1,\dots,q_t\) and set

$m=\prod_{i=1}^{t}q_i,\qquad A=\prod_{i=1}^{t}(q_i-1).$

If the final number is \(n=mp\), then \(\varphi(n)=A(p-1)\). Substituting this into

$k\varphi(n)=(k-1)n+1$

gives

$kA(p-1)=(k-1)mp+1.$

Collecting the terms containing \(p\),

$p\bigl(kA-(k-1)m\bigr)=kA+1,$

so the final prime is forced to be

$\boxed{p=\frac{kA+1}{kA-(k-1)m}.}$

This formula is the backbone of the recursive search. A branch succeeds only if the denominator is positive, it divides the numerator exactly, the resulting \(p\) is prime, it is larger than the primes already chosen, and \(mp\le L\).

Worked examples

The semiprime \(n=15=3\cdot 5\) comes from \(k=2\). Here

$K(2)=2^2-2+1=3,$

and the divisor pair \((1,3)\) yields

$p=2+1=3,\qquad q=2+3=5.$

Indeed \(\varphi(15)=8\), so

$\frac{15-1}{15-\varphi(15)}=\frac{14}{7}=2.$

A three-prime example is \(n=255=3\cdot 5\cdot 17\), again with \(k=2\). After choosing \(m=3\cdot 5=15\) and \(A=(3-1)(5-1)=8\), the forced last prime is

$p=\frac{2\cdot 8+1}{2\cdot 8-(2-1)\cdot 15}=\frac{17}{1}=17.$

Since \(\varphi(255)=128\), we get

$\frac{255-1}{255-\varphi(255)}=\frac{254}{127}=2.$

These two examples are exactly the two mechanisms used by the code: divisor pairs for semiprimes, and the forced-final-prime formula for the squarefree recursive branch.

How the Code Works

Prime tables and primality checks

The full implementations first generate all primes up to \(\sqrt{L}\). Those primes drive the congruence sieve for \(K(k)\), provide the candidates used in the recursive squarefree search, and answer small primality queries directly. Larger candidates are checked with a deterministic Miller-Rabin test in the relevant 64-bit range.

Semiprime enumeration

For each \(k\le \sqrt{L}\), the implementation stores the current remainder of \(K(k)\) together with the prime exponents found so far. Each admissible sieve prime contributes one or two residue classes of \(k\), and the algorithm walks exactly those progressions while stripping powers of that prime from the corresponding \(K(k)\). After the sieve phase, every divisor of \(K(k)\) is generated from the recorded factorization, translated into \(p=k+a\) and \(q=k+b\), tested for primality, and kept only when \(pq\le L\).

Recursive squarefree search

The multi-prime branch runs only for \(k\lt \sqrt[3]{L}\). It performs a depth-first search over strictly increasing primes \(\gt k\), maintaining the pair \((m,A)\). At every node, the formula

$p=\frac{kA+1}{kA-(k-1)m}$

is evaluated as a potential closing step. Whenever it produces a valid prime and at least two primes have already been chosen, a composite with at least three factors is recorded. The pruning is strong: if \(kA-(k-1)m\le 0\), no completion is possible, and if the next prime \(q\) would already force \(mq^2\gt L\), then there is no room for both \(q\) and a larger final prime.

What the three language implementations do

The C++ implementation contains the full optimized search and parallelizes both collection stages with worker threads. It also includes small-limit brute-force checks to validate the fast method. The Java implementation mirrors the same number-theoretic search directly in one process. The Python implementation is deliberately thin: it ensures a compiled solver is available and then invokes that same fast search, so all three language entries correspond to the same mathematics and the same final answer.

Complexity Analysis

The semiprime stage is the dominant part of the runtime. It covers all \(k\le \sqrt{L}\), but its cost is much lower than naive independent factorization because each sieve prime only visits the residue classes where \(k^2-k+1\) can actually be divisible by that prime. Divisor enumeration is then done from compact factorizations rather than from trial division.

The multi-prime branch is smaller. It only runs up to \(k\lt \sqrt[3]{L}\), only explores increasing primes \(\gt k\), and is pruned by the positivity test for \(kA-(k-1)m\), by exact divisibility of the forced-final-prime formula, by primality of the recovered last prime, and by the product bound \(n\le L\). Memory usage is moderate: a prime list, factor tables for the polynomial values, and a set of accepted solutions before sorting and deduplication. In practice the method is fast because it replaces an impossible totient sweep up to \(2\cdot 10^{11}\) with two highly structured searches.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=245
2. Euler totient function: Wikipedia - Euler's totient function
3. Squarefree integer: Wikipedia - Squarefree integer
4. Tonelli-Shanks algorithm: Wikipedia - Tonelli-Shanks algorithm
5. Miller-Rabin primality test: Wikipedia - Miller-Rabin primality test