Detailed mathematical approach

Problem Summary

For each modulus \(m \gt 1\), consider linear maps

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

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

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

Let \(R(m)\) be the number of such maps. Problem 446 asks for

$F(N)=\sum_{n=1}^{N}R(n^4+4),$

with the checkpoint \(F(1024)=77532377300600\). The challenge is to evaluate \(F(10^7)\bmod(10^9+7)\) without factoring each number \(n^4+4\) independently.

Mathematical Approach

Step 1: Convert the retraction condition into arithmetic conditions

Composing the map once more gives

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

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

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

Write

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

Because \(\gcd(a,a-1)=1\), each prime power \(p_i^{e_i}\) must divide exactly one of \(a\) or \(a-1\). Hence for every \(p_i^{e_i}\parallel m\),

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

These independent choices correspond to the unitary divisors of \(m\). If we define

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

then \(d\mid m\) and \(\gcd(d,m/d)=1\), so \(d\) is unitary. Conversely, every unitary divisor \(d \lt m\) determines one admissible residue class for \(a\).

Now fix such an \(a\), and write

$a=d\,a_1,\qquad m=d\,m_1,\qquad \gcd(a_1,m_1)=1.$

The condition \(m\mid ab\) becomes

$d\,m_1\mid d\,a_1b \iff m_1\mid a_1b \iff m_1\mid b,$

because \(a_1\) is invertible modulo \(m_1\). Among the residues \(0\le b\lt m=d\,m_1\), exactly \(d\) are multiples of \(m_1\). Therefore each admissible \(a\) contributes exactly \(d\) values of \(b\).

Summing over all unitary divisors gives

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

Thus

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

where \(\sigma^*(m)\) is the sum of unitary divisors. If \(m=\prod p^e\), then

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

Step 2: Factor \(n^4+4\) in a useful way

The key algebraic identity is the Sophie Germain factorization

$n^4+4=(n^2-2n+2)(n^2+2n+2).$

It is convenient to write

$A_n=(n-1)^2+1,\qquad B_n=(n+1)^2+1,$

so that

$n^4+4=A_nB_n.$

Define also

$Q(m)=\sigma^*(m^2+1).$

Then \(A_n\) and \(B_n\) are exactly the values \(m^2+1\) at \(m=n-1\) and \(m=n+1\). The whole problem reduces to precomputing \(Q(m)\) for \(0\le m\le N+1\).

Step 3: Determine the gcd of the two factors

Any common divisor \(g\) of \(A_n\) and \(B_n\) must divide their difference:

$g\mid (B_n-A_n)=4n.$

Also

$A_n\equiv B_n\equiv 2 \pmod{n}.$

If an odd prime \(p\) divided both \(A_n\) and \(B_n\), then from \(p\mid 4n\) we would get \(p\mid n\), but then \(A_n\equiv 2\pmod p\), which is impossible. So the gcd can only be a power of \(2\).

If \(n\) is odd, then \(n-1\) and \(n+1\) are even, hence \(A_n\) and \(B_n\) are odd, so

$\gcd(A_n,B_n)=1.$

If \(n\) is even, then \(n-1\) and \(n+1\) are odd, so

$A_n\equiv B_n\equiv 2 \pmod{8}.$

Therefore each factor contains exactly one power of \(2\), and

$\gcd(A_n,B_n)=2.$

Step 4: Derive the odd/even formulas for \(\sigma^*(n^4+4)\)

When \(n\) is odd, the factors \(A_n\) and \(B_n\) are coprime, and \(\sigma^*\) is multiplicative on coprime inputs. Hence

$\sigma^*(n^4+4)=\sigma^*(A_n)\sigma^*(B_n)=Q(n-1)Q(n+1).$

When \(n\) is even, write

$A_n=2u,\qquad B_n=2v,$

with \(u\) and \(v\) odd and coprime. Then

$Q(n-1)=\sigma^*(2u)=(1+2)\sigma^*(u)=3\sigma^*(u),$

$Q(n+1)=\sigma^*(2v)=3\sigma^*(v).$

But now

$n^4+4=A_nB_n=4uv,$

and since \(4\), \(u\), and \(v\) are pairwise coprime,

$\sigma^*(n^4+4)=\sigma^*(4)\sigma^*(u)\sigma^*(v)=5\sigma^*(u)\sigma^*(v).$

Comparing the two expressions yields the constant correction

$\sigma^*(n^4+4)=\frac{5}{9}Q(n-1)Q(n+1)\qquad(n\text{ even}).$

So the final closed form is

$\boxed{\sigma^*(n^4+4)= \begin{cases} Q(n-1)Q(n+1), & n\text{ odd},\\[4pt] \dfrac{5}{9}Q(n-1)Q(n+1), & n\text{ even}. \end{cases}}$

Step 5: Sieve all values of \(Q(m)=\sigma^*(m^2+1)\) at once

For an odd prime \(p\) to divide \(m^2+1\), we must have

$m^2\equiv -1 \pmod{p}.$

That means \(-1\) is a quadratic residue modulo \(p\), which happens only for

$p\equiv 1 \pmod{4}.$

The prime \(2\) is special: \(2\mid m^2+1\) exactly when \(m\) is odd, and then \(m^2+1\equiv 2\pmod 8\), so the exponent of \(2\) is exactly \(1\).

This leads to a quadratic-congruence sieve:

For \(p=2\), update all odd \(m\).

For each odd prime \(p\equiv 1\pmod 4\), find one square root \(r\) of \(-1\) modulo \(p\). Then the only possible indices are the two residue classes

$m\equiv r \pmod p,\qquad m\equiv -r \pmod p.$

For every such \(m\), divide \(m^2+1\) by \(p\) repeatedly to recover the exact exponent \(p^e\parallel (m^2+1)\), and multiply the running value of \(Q(m)\) by \(1+p^e\).

After all relevant primes up to \(N+1\) have been processed, any remaining factor larger than \(1\) must itself be prime. Indeed, two unfactored primes both exceeding \(N+1\) would have product larger than \((N+1)^2+1\), but \(m^2+1\le (N+1)^2+1\). So one final factor \(1+\text{leftover}\) completes \(Q(m)\).

Step 6: Worked examples

For \(n=2\), we have

$n^4+4=20,\qquad A_2=2,\qquad B_2=10.$

Thus

$Q(1)=\sigma^*(2)=3,\qquad Q(3)=\sigma^*(10)=(1+2)(1+5)=18.$

Since \(n\) is even,

$\sigma^*(20)=\frac{5}{9}\cdot 3\cdot 18=30,$

and therefore

$R(20)=30-20=10.$

For \(n=3\), the factors are coprime:

$n^4+4=85,\qquad A_3=5,\qquad B_3=17.$

Hence

$\sigma^*(85)=Q(2)Q(4)=\sigma^*(5)\sigma^*(17)=6\cdot 18=108,$

so

$R(85)=108-85=23.$

How the Code Works

The C++, Python, and Java implementations allocate arrays for the unfactored remainder of \(m^2+1\) and for the running value of \(Q(m)\) modulo \(10^9+7\), for every \(0\le m\le N+1\). Including \(m=0\) makes the first summand \(n=1\) work without a special case, since \(0^2+1=1\) and \(Q(0)=1\).

They next build a prime table up to \(N+1\). The prime \(2\) is handled by scanning odd indices. For each odd prime \(p\equiv 1\pmod 4\), the implementation computes a square root of \(-1\) modulo \(p\) with the Tonelli-Shanks algorithm, then walks both arithmetic progressions \(r,r+p,r+2p,\dots\) and \(-r,-r+p,-r+2p,\dots\).

Whenever an index is hit, the implementation strips the full \(p\)-adic exponent from the current remainder and multiplies the running unitary-divisor product by \(1+p^e\). After the sieve phase, any leftover prime factor is inserted once more. Finally, for each \(n\), the code combines the two precomputed values at \(n-1\) and \(n+1\), applies the \(5/9\) adjustment when \(n\) is even, subtracts \(n^4+4\) modulo \(10^9+7\), and accumulates the result.

Complexity Analysis

The prime preprocessing and the arrays over \(0,\dots,N+1\) use \(O(N)\) memory. The residue-class sweeps visit about \(2N/p\) indices for each prime \(p\equiv 1\pmod 4\), so the total work is near

$\sum_{p\le N+1,\ p\equiv 1\!\!\!\pmod 4}\frac{N}{p}=O(N\log\log N)$

in practice. The remaining arithmetic per visited index is constant apart from stripping a prime power, so the overall method runs in near \(O(N\log\log N)\) time and \(O(N)\) memory.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=446
2. Unitary divisor: Wikipedia - Unitary divisor
3. Sophie Germain identity: Wikipedia - Sophie Germain's identity
4. Quadratic residue of \(-1\): Wikipedia - Quadratic residue
5. Tonelli-Shanks algorithm: Wikipedia - Tonelli-Shanks algorithm