Detailed mathematical approach

Problem Summary

The implementations do not explore the prime-ary tree by testing every integer up to \(N\) separately. Instead, they use a structural reduction: first identify which primes \(q\) satisfy the orbit condition that governs the problem, and then sum the squarefree products built from those primes. For the full task, the limit is \(N=10^7\).

The dynamical object attached to a prime modulus \(q\) and a prime exponent \(r\) is the orbit

$x_0=1,\qquad x_{k+1}\equiv x_k^r+1 \pmod q.$

A prime \(q\) is kept precisely when this orbit reaches \(0\) for every distinct prime divisor \(r\mid(q-1)\). Once those primes are known, the answer is the sum of all admissible squarefree products that do not exceed \(N\).

Mathematical Approach

Write \(\mathcal P(m)\) for the set of distinct prime divisors of \(m\). The computation naturally splits into two layers: classify the primes that survive the orbit test, then enumerate the integers obtained by multiplying those primes without repetition.

The orbit attached to a pair \((q,r)\)

For a prime \(q\) and a prime \(r\in\mathcal P(q-1)\), define

$x_0^{(q,r)}=1,\qquad x_{k+1}^{(q,r)}\equiv \left(x_k^{(q,r)}\right)^r+1 \pmod q.$

The implementations use the following acceptance criterion:

$q\in\mathcal G \iff \forall r\in\mathcal P(q-1),\ \exists k\ge 0\text{ such that }x_k^{(q,r)}=0.$

Only distinct prime divisors of \(q-1\) matter. If \(r^a\) divides \(q-1\), the condition attached to \(r\) is still checked only once, because the orbit depends on the prime exponent \(r\), not on its multiplicity in \(q-1\).

Why the test is finite

Modulo \(q\) there are only \(q\) possible residues, so every orbit is a finite-state process. Therefore exactly one of two things must happen:

$\text{either some }x_k^{(q,r)}=0,\qquad\text{or a nonzero state repeats before }0\text{ appears.}$

If the orbit ever repeats a nonzero value, the future evolution is periodic and \(0\) will never be reached afterward. This is why cycle detection with constant memory is enough; there is no need to store a full visited set.

There is also a useful invariant at the moment of success. If \(x_k^{(q,r)}=0\), then

$x_{k+1}^{(q,r)}\equiv 0^r+1\equiv 1 \pmod q.$

So hitting \(0\) means that the orbit starting from \(1\) has closed into a cycle containing both \(1\) and \(0\). The code exploits exactly this hit-or-cycle dichotomy.

From qualifying primes to admissible nodes

Let \(\mathcal G\) be the set of primes that pass every required orbit test. The implementations then treat the admissible integers up to \(N\) as

$\mathcal S(N)=\left\{\prod_{q\in T} q:\ T\subseteq\mathcal G,\ \prod_{q\in T} q\le N\right\}.$

The empty subset contributes the empty product \(1\), so \(1\) is always included. The desired sum is therefore

$A(N)=\sum_{n\in\mathcal S(N)} n=\sum_{\substack{T\subseteq\mathcal G\\ \prod_{q\in T}\le N}}\prod_{q\in T} q.$

This description is squarefree by construction: each accepted prime can appear at most once. The compiled implementations even contain spot-checks against naively extending an accepted prime to \(q^2\), which supports the fact that repeated prime powers are not part of the final search space.

Hand-checking the smallest primes

The first few primes already show how the criterion behaves.

For \(q=2\), we have \(q-1=1\), so \(\mathcal P(q-1)=\varnothing\). The condition is vacuous, hence \(2\in\mathcal G\).

For \(q=3\), the only relevant exponent is \(r=2\), and the orbit is

$1\to 2\to 2\to 2\to\cdots \pmod 3,$

so \(0\) is never reached. Therefore \(3\notin\mathcal G\).

For \(q=5\), again only \(r=2\) matters, but now

$1\to 2\to 0\to 1\to\cdots \pmod 5,$

so \(5\in\mathcal G\).

For \(q=7\), the relevant exponents are \(2\) and \(3\). The orbit for \(r=3\) is

$1\to 2\to 2\to 2\to\cdots \pmod 7,$

which already fails, so \(7\notin\mathcal G\).

Hence, up to \(20\), the accepted primes are exactly \(\{2,5\}\). The admissible squarefree products are

$1,\ 2,\ 5,\ 10,$

and therefore

$A(20)=1+2+5+10=18.$

This is the first built-in checkpoint in the implementations. A second checkpoint is \(A(1000)=2089\), which tests the same logic on a larger range.

How the Code Works

All three language paths follow the same mathematical decomposition: build arithmetic infrastructure first, classify primes second, and enumerate squarefree products last.

Screening primes by orbit detection

The first stage is a linear sieve up to \(N\). It produces the prime list together with the smallest prime factor of every integer up to the limit, so factoring \(q-1\) is fast for each candidate prime \(q\).

For every \(q\), the implementation extracts the distinct primes in \(\mathcal P(q-1)\) and runs the orbit test modulo \(q\) for each of them. The transition \(x\mapsto x^r+1\pmod q\) is computed directly when \(r=2\), and by modular exponentiation for larger \(r\). Because the orbit can only hit \(0\) or enter a disjoint cycle, constant-memory cycle detection is sufficient.

The C++ implementation parallelizes this prime-screening phase across several workers. The Java implementation performs the same logic serially. The Python entry point reuses the same compiled computation instead of re-implementing the full search in pure Python.

Summing the squarefree products

After \(\mathcal G\) has been constructed, the remaining task is a depth-first enumeration over increasing prime indices. At each recursive state, the current product is added to the running sum, and the search continues only with later accepted primes. That ordering rule automatically prevents repeated use of the same prime.

The essential pruning inequality is

$\text{current} \gt \frac{N}{q_{\text{next}}}.$

Once it holds, multiplying by the next available prime would already exceed \(N\), so the entire suffix of that branch can be skipped. The compiled implementations also keep the checkpoints \(A(20)=18\) and \(A(1000)=2089\), plus small spot-checks involving \(q^2\), before running the full computation at \(N=10^7\).

Complexity Analysis

The sieve stage is \(O(N)\) time and \(O(N)\) memory in the implemented model, because it stores the smallest prime factor of every integer up to \(N\). Once that table exists, extracting \(\mathcal P(q-1)\) is cheap.

For a fixed test pair \((q,r)\), the orbit phase inspects at most \(q\) residues before it either finds \(0\) or proves that the orbit cycles elsewhere. Each step costs \(O(1)\) when \(r=2\) and \(O(\log r)\) modular multiplications otherwise. A direct expression for the screening cost is

$O\!\left(N+\sum_{\substack{q\le N\\ q\text{ prime}}}\ \sum_{r\in\mathcal P(q-1)} q\log r\right).$

The final depth-first search is output-sensitive in practice rather than powerset-sized, because it explores only branches whose current squarefree product is still at most \(N\). Its memory usage is the recursion depth plus the stored list of accepted primes, both much smaller than the sieve table.

Footnotes and References

1. Problem page: Project Euler 927
2. Modular arithmetic: Wikipedia - Modular arithmetic
3. Modular exponentiation: Wikipedia - Modular exponentiation
4. Cycle detection: Wikipedia - Brent's algorithm
5. Squarefree integers: Wikipedia - Square-free integer
6. Integer factorization: Wikipedia - Integer factorization