Detailed mathematical approach

Problem Summary

For each prime \(p \equiv 1 \pmod{5}\), the problem studies the polynomial map

$f_p(x)=x+x^{(p+4)/5}\pmod p,$

counts how many residues \(x \in \mathbb F_p\) are periodic under iteration of that map, and denotes this count by \(C(p)\). The global quantity computed by the implementations is

$S(L)=\sum_{\substack{p \le L\\ p \equiv 1 \pmod{5}}} C(p).$

A naive method would inspect every residue modulo every relevant prime and explicitly follow the orbit of each starting value. That is already expensive for one large prime, and completely impractical when the limit is \(10^8\). The key simplification is that, for nonzero residues, the map depends only on which fifth-root class the value belongs to, so each prime collapses to a functional graph on exactly five states.

Mathematical Approach

The entire derivation starts from rewriting the exponent and then using the multiplicative structure of \(\mathbb F_p^\times\).

Five multiplicative classes inside \(\mathbb F_p^\times\)

Write

$t=\frac{p-1}{5}, \qquad \frac{p+4}{5}=t+1.$

For every nonzero \(x\),

$f_p(x)=x+x^{t+1}=x(1+x^t).$

Because \(x^{p-1}=1\) in \(\mathbb F_p^\times\), we have

$\left(x^t\right)^5=x^{p-1}=1,$

so \(x^t\) is always a fifth root of unity. Choose an element \(\omega\) of order 5. Then every nonzero residue belongs to exactly one class

$A_r=\{x \in \mathbb F_p^\times : x^t=\omega^r\}, \qquad r=0,1,2,3,4.$

These are the fibers of the homomorphism \(x \mapsto x^t\) from the cyclic group \(\mathbb F_p^\times\) of size \(5t\) onto its subgroup of fifth roots of unity of size 5, so each class has exactly \(t\) elements.

The induced map on the five classes

If \(x \in A_r\), then \(x^t=\omega^r\), hence

$f_p(x)=x(1+\omega^r).$

The multiplier \(1+\omega^r\) is nonzero: a fifth root of unity cannot equal \(-1\) when \(p\) is odd. Therefore

$f_p(x)^t=x^t(1+\omega^r)^t=\omega^r(1+\omega^r)^t.$

Now \((1+\omega^r)^t\) is also a fifth root of unity, so there is a unique \(s_r \in \{0,1,2,3,4\}\) such that

$ (1+\omega^r)^t=\omega^{s_r}. $

It follows that every element of \(A_r\) is sent into the single class

$A_{r+s_r \bmod 5}.$

Thus one prime \(p\) gives a functional graph on five nodes:

$r \longmapsto r+s_r \pmod 5.$

This graph contains all the information needed for periodicity. The actual residue \(x\) still matters for the exact orbit inside a class, but the question “can this orbit ever come back?” is decided entirely by the class graph.

Why cycle classes contribute all of their elements

Suppose a class \(A_r\) lies on a directed cycle of length \(\ell\) in the five-node graph. After \(\ell\) iterations, every \(x \in A_r\) has returned to the same class, so the map on that class is simply multiplication by a fixed nonzero field element \(\lambda\):

$f_p^{(\ell)}(x)=\lambda x.$

Since \(\lambda \in \mathbb F_p^\times\), Fermat's little theorem gives \(\lambda^{p-1}=1\), and therefore

$f_p^{(\ell(p-1))}(x)=x.$

So every element of a cycle class is periodic. Conversely, if a class is not on a cycle of the class graph, its label eventually falls into some other class cycle and never returns to the starting label, so no element of that class can be periodic.

The special residue \(x=0\) is even simpler:

$f_p(0)=0,$

so it is always a fixed point. If \(c_p\) denotes the number of nodes that lie on cycles in the five-node graph, then

$\boxed{C(p)=1+t\,c_p.}$

That formula is exactly what the implementations evaluate.

Worked example: \(p=11\)

For \(p=11\) we have \(t=(11-1)/5=2\). One choice of fifth root of unity is \(\omega=4\), because \(4^5 \equiv 1 \pmod{11}\) and \(4 \not\equiv 1\). Its powers are

$1,\ 4,\ 5,\ 9,\ 3.$

The five classes are

$A_0=\{1,10\},\quad A_1=\{2,9\},\quad A_2=\{4,7\},\quad A_3=\{3,8\},\quad A_4=\{5,6\}.$

Now compute \((1+\omega^r)^2\):

$2^2=4=\omega^1,\quad 5^2=3=\omega^4,\quad 6^2=3=\omega^4,\quad 10^2=1=\omega^0,\quad 4^2=5=\omega^2.$

So the class transitions are

$0 \to 1,\quad 1 \to 0,\quad 2 \to 1,\quad 3 \to 3,\quad 4 \to 1.$

The cycle nodes are \(0\), \(1\), and \(3\): there is a 2-cycle \(0 \leftrightarrow 1\) and a fixed node \(3\). Hence \(c_{11}=3\), and

$C(11)=1+2\cdot 3=7.$

This agrees with a direct brute-force orbit count, but the class-graph method obtains it without enumerating all trajectories.

How the Code Works

Prime enumeration

The C++, Python, and Java implementations first generate all primes up to the required limit with a straightforward sieve, then keep only primes congruent to \(1 \pmod 5\). Everything after that is done prime by prime.

Building the five-node graph for one prime

For a fixed prime \(p\), the implementation sets \(t=(p-1)/5\) and searches for a nontrivial fifth root of unity by scanning small bases \(a\) until \(a^t \not\equiv 1 \pmod p\). Any such value has order 5, because its fifth power is 1 and it is not equal to 1. The five powers \(1,\omega,\omega^2,\omega^3,\omega^4\) are then listed explicitly.

For each class index \(r\), the code evaluates \((1+\omega^r)^t \bmod p\), identifies which power of \(\omega\) it matches, and therefore determines the successor of node \(r\) in the functional graph.

Counting periodic points and accumulating the total

Once the successor table is known, the remaining job is just cycle detection on a graph of five nodes. The implementations use a standard three-state traversal: unseen, currently on the exploration stack, and finished. That counts exactly how many nodes belong to directed cycles.

After obtaining \(c_p\), the contribution of the prime is \(1+t\,c_p\). The compiled implementations also perform small sanity checks by comparing this fast method against direct orbit simulation for a few small primes, and they verify the small aggregate value \(S(100)=127\) before printing the full answer.

Complexity Analysis

The sieve up to \(L\) costs \(O(L \log \log L)\) time and \(O(L)\) memory in the direct form used here. After the sieve, each relevant prime requires only a constant number of modular exponentiations and a constant-size graph traversal. Each modular exponentiation takes \(O(\log p)\) modular multiplications, so the post-sieve work is

$O\!\left(\sum_{\substack{p \le L\\ p \equiv 1 \pmod 5}} \log p\right)=O(\pi(L)\log L)$

up to standard prime-counting bounds.

In practice, the important point is qualitative rather than asymptotic: instead of examining all \(p\) residues and their orbits for every prime, the algorithm reduces each prime to five class transitions and one cycle count on five nodes. That is the reason the method scales to the full limit.

Footnotes and References

1. Project Euler Problem 971: https://projecteuler.net/problem=971
2. Finite field: Wikipedia - Finite field
3. Cyclic group: Wikipedia - Cyclic group
4. Fermat's little theorem: Wikipedia - Fermat's little theorem
5. Root of unity: Wikipedia - Root of unity
6. Functional graph: Wikipedia - Functional graph