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