Project Euler Problem 705
The inversion count of a sequence of digits is the smallest number of adjacent pairs that must be swapped to sort the se
Solution
Answer: 480440153
For a master digit sequence $a_1,a_2,\dots,a_n$, each digit $a_i$ may be replaced by any divisor of $a_i$.
Let:
- $\tau(d)$ = number of divisors of digit $d$,
- $c(x,y)$ = number of pairs $(u,v)$ with $u\mid x,\ v\mid y,\ u>v$.
Then for a fixed pair of positions $i<j$, the number of divided sequences contributing one inversion from that pair is
$$c(a_i,a_j)\prod_{k\neq i,j}\tau(a_k).$$
Summing over all pairs gives the recurrence:
$$A_{\text{new}} = A\cdot \tau(d) + P\cdot Q[d],$$
where
- $P$ = total number of divided sequences so far,
- $A$ = total inversion count sum so far,
- $Q[d]=\sum \frac{c(x,d)}{\tau(x)}$ over previous digits $x$.
Processing all nonzero digits of all primes below $10^8$ with a sieve yields:
$$F(10^8)\equiv 480440153 \pmod{1,000,000,007}.$$
Answer: 480440153