Project Euler Problem 445

Project Euler Problem 445

Solution

Answer: 659104042

Let

$$f(x)\equiv ax+b \pmod n$$

with $0<a<n$, $0\le b<n$. We want

$$f(f(x))\equiv f(x)\pmod n$$

for every $x$.

1. Mathematical analysis

We compute:

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

The retraction condition gives

$$a^2x+ab+b\equiv ax+b \pmod n,$$

so for all $x$,

$$(a^2-a)x+ab\equiv 0\pmod n.$$

Since this must hold for every $x$, we require

$$a(a-1)\equiv 0\pmod n$$

and

$$ab\equiv 0\pmod n.$$

Step 1: characterize valid $a$

Write

$$n=\prod p_i^{e_i}.$$

The congruence

$$a(a-1)\equiv 0 \pmod{p_i^{e_i}}$$

implies

$$a\equiv 0 \quad \text{or}\quad 1 \pmod{p_i^{e_i}},$$

because consecutive integers are coprime.

Thus each prime power independently chooses either $0$ or $1$, and by CRT every subset of prime powers gives exactly one idempotent $a$.

The all-zero choice gives $a\equiv 0\pmod n$, forbidden since $0<a<n$. So valid $a$'s correspond to all proper subsets.

Step 2: count valid $b$

For a fixed $a$,

$$ab\equiv 0\pmod n$$

means $b$ must be divisible by

$$\frac{n}{\gcd(a,n)}.$$

Hence the number of valid $b$ values is exactly

$$\gcd(a,n).$$

If $a\equiv 0$ on a subset $S$ of prime powers and $1$ elsewhere, then

$$\gcd(a,n)=\prod_{i\in S} p_i^{e_i}.$$

Therefore

$$R(n) = \sum_{\text{proper }S} \prod_{i\in S} p_i^{e_i}.$$

This factors nicely:

$$R(n) = \prod_i (1+p_i^{e_i})-n.$$

So if

$$n=\prod p_i^{e_i},$$

then

$$R(n)=\prod_i(1+p_i^{e_i})-n.$$

---

We need

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

The key optimization is to update the prime factorization of

$$\binom Nk = \binom N{k-1}\cdot \frac{N-k+1}{k}$$

incrementally.

Maintain:

• prime exponents of $\binom Nk$,
• the product

$$P_k=\prod_p(1+p^{e_p}),$$

so

$$R!\left(\binom Nk\right)=P_k-\binom Nk.$$

Using a smallest-prime-factor sieve up to $10^7$, we update factor exponents in $O(\log n)$ amortized time per step.

We also exploit symmetry:

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

halving the work.

The implementation reproduces the check value:

$$\sum_{k=1}^{99999} R!\left(\binom{100000}{k}\right) \equiv 628701600 \pmod{10^9+7},$$

matching the statement.

Running the optimized computation for $N=10^7$ gives:

Answer: 659104042