Project Euler Problem 913
The numbers from 1 to 12 can be arranged into a 3 times 4 matrix in either row-major or column-major order: By swapping
Solution
Answer: 2101925115560555020
Let $N=nm$, and index the matrix positions from $0$ to $N-1$.
For a position $p$, write
$$p = an+b \qquad (0\le b<n).$$
In row-major order, the entry $p+1$ is at that position.
In column-major order, that same entry moves to position
$$f(p)=bm+a.$$
Now observe:
$$mp = m(an+b)=amn+bm \equiv a+bm \pmod{nm-1}.$$
Hence for all $0\le p < nm-1$,
$$f(p)\equiv mp \pmod{nm-1}.$$
Also, $0$ and $nm-1$ are fixed points.
So the permutation is:
- two fixed points;
- multiplication by $m$ modulo $nm-1$ on the remaining elements.
For any permutation,
$$\text{minimal swaps} = N-(\text{number of cycles}).$$
The number of cycles of multiplication by $m$ modulo $M=nm-1$ is
$$2+\sum_{d\mid M,\ d>1}\frac{\varphi(d)}{\operatorname{ord}_d(m)},$$
where $\operatorname{ord}_d(m)$ is the multiplicative order of $m$ mod $d$.
Thus
$$S(n,m)=nm-\left(2+\sum_{d\mid (nm-1),,d>1} \frac{\varphi(d)}{\operatorname{ord}_d(m)}\right).$$
Checking the given example:
$$S(3,4)=12-\left(2+\frac{\varphi(11)}{\operatorname{ord}_{11}(4)}\right) =12-(2+10/5)=8.$$
Evaluating
$$\sum_{2\le n\le m\le 100} S(n^4,m^4)$$
with this formula gives:
Answer: 2101925115560555020