Detailed mathematical approach

Problem Summary

Let \(S(m,n)\) be the minimum number of moves needed to move the red counter from the top-left corner of an \(m\times n\) board to the bottom-right corner, with the empty cell initially at the bottom-right corner.

The problem asks for the number of grids such that

$S(m,n)=p^2,\qquad p<10^6,\ p\text{ prime}.$

The key fact is that the sliding game has an affine move formula, so the problem becomes a pure lattice-point count for each prime square.

Mathematical Approach

1) Symmetry and small data.

Because rotating the board swaps \(m\) and \(n\) without changing the puzzle,

$S(m,n)=S(n,m).$

A brute-force BFS on small boards gives

$S(2,2)=5,\quad S(3,2)=9,\quad S(4,2)=15,\quad S(5,2)=21,$

$S(4,3)=17,\quad S(5,4)=25,\quad S(6,5)=33.$

The pattern is clear:

$S(m,2)=6m-9\qquad (m\ge 3),$

and every extra row beyond \(2\) adds exactly two more moves.

2) Closed form for non-square boards.

Assume \(m>n\ge 2\). Starting from the \(m\times 2\) strip, each extra row gives two extra blank-cell shuffles, so

$S(m,n)=S(m,2)+2(n-2)=6m+2n-13.$

This formula matches the sample from the statement:

$S(5,4)=6\cdot 5+2\cdot 4-13=25.$

3) What about square boards?

For \(m=n\ge 3\), brute force gives

$S(3,3)=13,\quad S(4,4)=21,\quad S(5,5)=29,$

so the square case follows

$S(n,n)=8n-11.$

But for an odd prime \(p\),

$p^2\equiv 1\pmod 8,$

whereas

$8n-11\equiv 5\pmod 8.$

So no square board can satisfy \(S(n,n)=p^2\). The case \(p=2\) also fails. Therefore only the non-square formula matters for prime squares.

4) Convert the move equation into an integer interval.

Set

$q=p^2.$

We must count integer pairs \((m,n)\) with \(m>n\ge2\) such that

$6m+2n-13=q.$

Divide by \(2\):

$3m+n=\frac{q+13}{2}=:h.$

Now solve for \(n\):

$n=h-3m.$

The conditions become:

From \(n\ge 2\),

$m\le \left\lfloor\frac{h-2}{3}\right\rfloor.$

From \(m>n\),

$m>h-3m\iff 4m>h\iff m\ge \left\lfloor\frac{h}{4}\right\rfloor+1.$

So the valid values of \(m\) lie in the interval

$m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$

5) Why the final count is multiplied by \(2\).

The interval above counts only boards with \(m>n\). But each such board has a transposed partner \(n\times m\), and both are distinct grids in the problem statement. Therefore the contribution of \(q=p^2\) is

$f(q)=2\cdot \max\bigl(0,\ m_{\max}-m_{\min}+1\bigr).$

This is exactly the formula implemented in the C++ solver.

6) Simplify the formula for odd primes \(p>3\).

Every odd prime larger than \(3\) satisfies

$p^2\equiv 1\pmod{24},$

so write

$p^2=24k+1.$

Then

$h=\frac{p^2+13}{2}=12k+7,$

and therefore

$m_{\min}=\left\lfloor\frac{12k+7}{4}\right\rfloor+1=3k+2,$

$m_{\max}=\left\lfloor\frac{12k+5}{3}\right\rfloor=4k+1.$

The number of admissible \(m\) values is

$m_{\max}-m_{\min}+1=(4k+1)-(3k+2)+1=k,$

so

$f(p^2)=2k=\frac{p^2-1}{12}\qquad (p>3).$

The exceptional prime \(p=3\) gives

$q=9,\quad h=11,\quad m_{\min}=3,\quad m_{\max}=3,\quad f(9)=2.$

And \(p=2\) contributes \(0\).

7) Final counting formula.

Hence

$\#\{(m,n):S(m,n)=p^2,\ p<P\} = 2+\sum_{\substack{3<p<P\\ p\text{ prime}}}\frac{p^2-1}{12},$

with the leading \(2\) coming from \(p=3\).

Worked Examples

The sample \(p<10\). The primes are \(2,3,5,7\).

\(p=2\) contributes \(0\), \(p=3\) contributes \(2\), \(p=5\) contributes \(2\), and \(p=7\) contributes \(4\). So the total is

$0+2+2+4=8,$

which matches the checkpoint in the code.

The sample \(p<100\). Summing the same formula over all primes below \(100\) gives

$5482,$

exactly as stated in the problem.

Algorithm

1) Generate all primes \(p<10^6\) with the sieve of Eratosthenes.

2) For each prime, compute \(q=p^2\).

3) Evaluate

$h=\frac{q+13}{2},\qquad m_{\min}=\left\lfloor\frac{h}{4}\right\rfloor+1,\qquad m_{\max}=\left\lfloor\frac{h-2}{3}\right\rfloor.$

4) Add

$2\cdot \max(0,m_{\max}-m_{\min}+1).$

This is \(O(1)\) work per prime.

Complexity Analysis

The sieve costs \(O(P\log\log P)\) time and \(O(P)\) memory. After that, the summation is linear in the number of primes, with constant-time arithmetic for each one.

Checks And Final Result

The implementation verifies

$\text{solve}(10)=8,\qquad \text{solve}(100)=5482.$

The full answer is

$2057774861813004.$

Further Reading

1. Problem page: https://projecteuler.net/problem=313
2. Sieve of Eratosthenes: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
3. Diophantine equations: https://en.wikipedia.org/wiki/Diophantine_equation