Detailed mathematical approach

Problem Summary

Let \(M=10^9\). For each integer \(n\), we want the positive residue \(x\in\{1,2,\dots,M-1\}\) satisfying

$n^x \equiv x \pmod{M}.$

If no positive fixed point exists, we set \(f(n)=0\). The required sum is

$\sum_{n=2}^{10^6} f(n).$

The checkpoint values used by the implementations are \(f(4)=411728896\), \(f(10)=0\), \(f(157)=743757\), and

$\sum_{n=2}^{1000} f(n)=442530011399.$

Mathematical Approach

Step 1: Rewrite the condition as a fixed-point equation

Define the map

$F_n(x)=n^x \bmod M.$

Then the desired values are exactly the positive fixed points of \(F_n\):

$F_n(x)=x.$

Because all arithmetic is reduced modulo \(M\), every iterate lies in the finite set \(\{0,1,\dots,M-1\}\). It is also useful to remember that

$M=10^9=2^9\cdot 5^9,$

so the equation means that the last nine decimal digits of \(n^x\) must reproduce \(x\) itself.

Step 2: Follow the orbit starting from \(0\)

The implementations study the orbit generated by

$x_0=0,\qquad x_{k+1}=F_n(x_k)=n^{x_k}\bmod M.$

The first step is always

$x_1=n^0 \bmod M=1,$

so after the initial state the sequence immediately moves into positive exponents. Each later term is obtained by taking the previous residue as an exponent and then keeping only the last nine digits.

If at some stage

$x_{k+1}=x_k>0,$

the orbit has stabilized at a positive fixed point, and that value is returned as \(f(n)\).

Step 3: Why cycle detection is sufficient

The state space is finite, so every orbit must eventually repeat. In other words, there exist indices \(i<j\) with

$x_i=x_j.$

Since the map \(F_n\) is deterministic, repeating one value forces the entire future tail to repeat as well. Therefore the orbit can end in only two ways:

$\text{fixed point} \qquad \text{or} \qquad \text{nontrivial cycle}.$

If the repetition happens at a genuine fixed point, we are done. If a previously seen value reappears without equality to the current state, the orbit has entered a cycle that is not a positive fixed point, so the implementations return \(0\).

Step 4: A useful observation for multiples of \(10\)

The checkpoint \(f(10)=0\) is not accidental. Suppose \(10\mid n\) and \(2\le n\le 10^6\). Then the orbit begins

$0 \to 1 \to n.$

Now \(n\ge 10\), so \(n^n\) contains at least \(10\) factors of \(10\). Hence

$n^n \equiv 0 \pmod{10^9}.$

Therefore the orbit becomes

$0 \to 1 \to n \to 0 \to 1 \to n \to \cdots,$

a cycle of length \(3\) with no positive fixed point. So every such \(n\) contributes \(0\).

Step 5: Worked examples from the orbit

For \(n=157\), the iterates are

$0 \to 1 \to 157 \to 201583757 \to 204743757 \to 400743757 \to 743757 \to 743757.$

The last value equals its own image, so

$f(157)=743757.$

For \(n=4\), the same procedure produces

$0 \to 1 \to 4 \to 256 \to 6084096 \to 261392896 \to 264208896 \to 405328896 \to 363728896 \to 51728896 \to 211728896 \to 411728896,$

and one more application still gives \(411728896\), matching the published checkpoint.

Step 6: Efficient evaluation of \(n^x \bmod M\)

A naive computation of \(n^x\) would require \(x\) multiplications, which is impossible when \(x\) may be close to \(10^9\). The implementations therefore use repeated squaring. Writing

$x=\sum_{i=0}^{t} b_i 2^i,\qquad b_i\in\{0,1\},$

we can compute \(n^x \bmod M\) by repeatedly squaring the base and multiplying it into the accumulator only when \(b_i=1\). This reduces one modular-power evaluation to \(O(\log x)\) modular multiplications instead of \(O(x)\).

How the Code Works

The C++, Python, and Java implementations all use the same strategy. For each \(n\), they iterate the map \(x\mapsto n^x \bmod 10^9\) starting from \(0\), evaluate each modular power by binary exponentiation, and store the residues already seen on that single orbit. If the new residue equals the current one and is positive, the algorithm returns it immediately. If the new residue has appeared earlier, the orbit is declared cyclic without a positive fixed point and the result is \(0\). The outer loop simply sums these values for all \(2\le n\le 10^6\).

Complexity Analysis

Let \(I(n)\) be the number of orbit steps examined for a given \(n\). Each step needs one modular exponentiation, and the exponent is always less than \(M\), so one step costs \(O(\log M)\). Therefore

$f(n)\text{ is computed in }O(I(n)\log M)\text{ time and }O(I(n))\text{ memory.}$

Summing over all \(n\) gives

$O\left(\sum_{n=2}^{10^6} I(n)\log M\right).$

In practice the observed orbit lengths are small, which is why the direct iteration used by the implementations is fast enough for the target range.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=455
2. Modular arithmetic: Wikipedia — Modular arithmetic
3. Modular exponentiation: Wikipedia — Modular exponentiation
4. Cycle detection and functional graphs: Wikipedia — Cycle detection