Detailed mathematical approach

Problem Summary

For each integer \(n \gt 1\), consider the linear maps

$f(x)\equiv ax+b \pmod{n},\qquad 0 \lt a \lt n,\quad 0\le b \lt n.$

The map is a retraction if it is idempotent on every residue class:

$f(f(x))\equiv f(x)\pmod{n}\qquad\text{for all }x.$

Let \(R(n)\) be the number of such maps. The target of the problem is

$S(N)=\sum_{k=1}^{N-1} R\left(\binom{N}{k}\right),\qquad N=10^7,$

and the final result is required modulo \(M=10^9+7\). The main challenge is that the binomial coefficients are enormous, so the implementations never factor them from scratch.

Mathematical Approach

Step 1: Translate the retraction condition into divisibility conditions

Starting from \(f(x)=ax+b\), we compose once more:

$f(f(x))\equiv a(ax+b)+b \equiv a^2x+ab+b \pmod{n}.$

For this to equal \(ax+b\) for every \(x\), the coefficient of \(x\) and the constant correction must both vanish modulo \(n\). Therefore

$n\mid a(a-1),\qquad n\mid ab.$

So every retraction is determined by two simultaneous conditions: \(a\) must satisfy an idempotence congruence, and once \(a\) is fixed, \(b\) must solve a linear congruence.

Step 2: Solve the condition on \(a\) prime power by prime power

Write the modulus as

$n=\prod_{i=1}^{m} p_i^{e_i}.$

Because consecutive integers are coprime, \(\gcd(a,a-1)=1\). Hence if \(p_i^{e_i}\mid a(a-1)\), the full prime power \(p_i^{e_i}\) must divide exactly one of the two factors. For each \(p_i^{e_i}\parallel n\), we must have

$a\equiv 0 \pmod{p_i^{e_i}}\qquad\text{or}\qquad a\equiv 1 \pmod{p_i^{e_i}}.$

These choices are independent for distinct prime powers, and the Chinese remainder theorem combines them into exactly one residue class modulo \(n\).

If we define

$d=\gcd(a,n),$

then \(d\) is a unitary divisor of \(n\): it satisfies \(d\mid n\) and \(\gcd(d,n/d)=1\). Conversely, every unitary divisor \(d\lt n\) determines one admissible residue \(a\). The excluded case \(d=n\) corresponds to \(a\equiv 0\pmod{n}\), but the problem requires \(0 \lt a \lt n\).

Step 3: Count the admissible values of \(b\)

Fix one valid \(a\), and let \(d=\gcd(a,n)\). Write

$a=d\,a_1,\qquad n=d\,n_1,\qquad \gcd(a_1,n_1)=1.$

The second condition becomes

$n\mid ab \iff d\,n_1 \mid d\,a_1 b \iff n_1 \mid a_1 b.$

Since \(a_1\) is invertible modulo \(n_1\), this is equivalent to

$n_1\mid b.$

Among the residues \(0\le b\lt n=d\,n_1\), exactly \(d\) values are multiples of \(n_1\). Therefore each admissible \(a\) contributes exactly \(d=\gcd(a,n)\) choices for \(b\).

Summing over all unitary divisors gives

$R(n)=\sum_{\substack{d\parallel n\\ d\lt n}} d = \left(\sum_{d\parallel n} d\right)-n.$

Thus

$\boxed{R(n)=\sigma^*(n)-n},$

where \(\sigma^*(n)\) is the sum of unitary divisors. Because each prime power is either chosen completely or not chosen at all,

$\sigma^*(n)=\sum_{d\parallel n} d=\prod_{p^e\parallel n}(1+p^e).$

Step 4: Apply the formula to the binomial coefficients

Let

$B_k=\binom{N}{k}.$

If

$B_k=\prod_p p^{e_p(k)},$

then the closed form above becomes

$R(B_k)=\prod_{e_p(k)\gt 0}\left(1+p^{e_p(k)}\right)-B_k.$

So the entire problem reduces to maintaining the prime exponents of \(B_k\) while \(k\) moves across the row of Pascal's triangle.

Step 5: Update \(\binom{N}{k}\) incrementally

The standard recurrence

$B_k=B_{k-1}\cdot \frac{N-k+1}{k}$

implies, for every prime \(p\),

$e_p(k)=e_p(k-1)+v_p(N-k+1)-v_p(k).$

This means the implementations only factor the two ordinary integers \(N-k+1\) and \(k\) at each step. They do not factor \(\binom{N}{k}\) itself.

At the same time they maintain

$Q_k=\prod_{e_p(k)\gt 0}\left(1+p^{e_p(k)}\right)\pmod{M},$

and then compute

$R(B_k)\equiv Q_k-B_k \pmod{M}.$

Because \(M\) is prime and \(N \lt M\), the recurrence for \(B_k \bmod M\) can also use modular inverses:

$B_k \equiv B_{k-1}(N-k+1)k^{-1}\pmod{M}.$

Step 6: Use symmetry and check a small example

Binomial coefficients satisfy

$\binom{N}{k}=\binom{N}{N-k},$

so the sum is symmetric. The implementations only iterate up to \(\lfloor N/2\rfloor\), using weight \(2\) except for the middle term when \(N\) is even.

For \(N=10\), the distinct values are

$\binom{10}{1}=10,\quad \binom{10}{2}=45,\quad \binom{10}{3}=120,\quad \binom{10}{4}=210,\quad \binom{10}{5}=252.$

Applying \(R(n)=\sigma^*(n)-n\):

$\begin{aligned} R(10)&=(1+2)(1+5)-10=8,\\ R(45)&=(1+9)(1+5)-45=15,\\ R(120)&=(1+8)(1+3)(1+5)-120=96,\\ R(210)&=(1+2)(1+3)(1+5)(1+7)-210=366,\\ R(252)&=(1+4)(1+9)(1+7)-252=148. \end{aligned}$

Hence

$S(10)=2(8+15+96+366)+148=1118,$

which is the small checkpoint matched by the implementation.

How the Code Works

The C++, Python, and Java implementations first build a smallest-prime-factor table up to \(N\). They also precompute modular inverses \(1^{-1},2^{-1},\dots,N^{-1}\pmod M\) so that the current binomial coefficient can be updated in constant time once the numerator and denominator factors are known.

During the main loop, the implementation stores for each active prime its current exponent in \(B_k\) and the current value of \(p^{e_p(k)} \bmod M\). When a prime exponent changes, the old factor \((1+p^e)\) is removed from the running product \(Q_k\), the exponent is adjusted, and the new factor is inserted.

Division inside the modulus is handled by multiplying with inverses. The implementations cache inverses of previously seen nonzero factors, and they also keep track of how many factors are currently \(0 \pmod M\). If at least one such factor exists, then \(Q_k\equiv 0\pmod M\), so the running product remains correct even in that edge case.

Complexity Analysis

The smallest-prime-factor preprocessing uses \(O(N)\) memory. The total factor work over all updates is governed by the number of prime factors, counted with multiplicity, appearing in the integers \(1,2,\dots,N\), which is near \(O(N\log\log N)\) in aggregate. The remaining arithmetic per step is constant. Therefore the full method runs in near \(O(N\log\log N)\) time and \(O(N)\) memory, which is practical for \(N=10^7\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=445
2. Chinese remainder theorem: Wikipedia — Chinese remainder theorem
3. Unitary divisor: Wikipedia — Unitary divisor
4. Binomial coefficient: Wikipedia — Binomial coefficient
5. Hardy and Wright, An Introduction to the Theory of Numbers, sections on multiplicative arithmetic functions and congruences.