Project Euler Problem 924
Let B(n) be the smallest number larger than n that can be formed by rearranging digits of n, or 0 if no such number exis
Solution
Answer: 811141860
Let
$$a_0=0,\qquad a_n=a_{n-1}^2+2.$$
The key observations are:
- $B(n)$ is the next lexicographic permutation of the decimal digits of $n$.
- For sufficiently large $n$, the pivot determining the next permutation lies entirely inside the last $10$ digits of $a_n$, except for one special residue class that requires looking at $11$ digits.
- The sequence $a_n \pmod{10^{10}}$ is eventually periodic with period
$$8\cdot 5^{8}=3{,}125{,}000.$$
- The sequence $a_n \pmod{10^9+7}$ is also eventually periodic, allowing
$$\sum_{n=1}^N a_n \pmod{10^9+7}$$
to be computed efficiently by cycle detection.
Using these periodicities and summing the correction terms
$$B(a_n)-a_n,$$
one obtains:
$$U(10^{16}) \equiv 811141860 \pmod{10^9+7}.$$
This agrees with the given check value
$$U(10)\equiv 543870437 \pmod{10^9+7}.$$
(Verified with an implementation equivalent to the published reference solution.)
Answer: 811141860