Solution

Answer: 2057774861813004

Let the grid be $m \times n$, with the empty square initially at the bottom-right and the red counter initially at the top-left.

We seek all grids such that

$$S(m,n)=p^2$$

for a prime $p<10^6$.

1. Mathematical analysis

Step 1: Deriving the formula for $S(m,n)$

By analyzing optimal move patterns of the sliding process, one finds:

If $m=n$,

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

If $m\neq n$,

$$S(m,n)=6\max(m,n)+2\min(m,n)-13$$

The problem statement confirms one example:

$$S(5,4)=6\cdot5+2\cdot4-13=30+8-13=25$$

which matches the given value.

Because the formula is symmetric in $m,n$, we may assume

$$m>n.$$

Then

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

We therefore need integer solutions of

$$6m+2n-13=p^2.$$

Rearrange:

$$3m+n=\frac{p^2+13}{2}.$$

Step 2: Congruence restrictions on primes

For primes $p>3$,

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

Write

$$p^2=24k+1.$$

Then

$$\frac{p^2+13}{2} =\frac{24k+14}{2} =12k+7.$$

Hence we solve

$$3m+n=12k+7$$

with integers satisfying

$$m>n\ge2.$$

Substitute

$$n=12k+7-3m.$$

The constraints become:

Condition 1: $n\ge2$

$$12k+7-3m\ge2$$

$$m\le4k+1.$$

Condition 2: $m>n$

$$m>12k+7-3m$$

$$4m>12k+7$$

$$m\ge3k+2.$$

Thus

$$3k+2\le m\le4k+1.$$

The number of integer values of $m$ is

$$(4k+1)-(3k+2)+1=k.$$

Since

$$k=\frac{p^2-1}{24},$$

the number of solutions with $m>n$ is

$$\frac{p^2-1}{24}.$$

Because swapping dimensions gives another valid grid, the total number of ordered grids is

$$2\cdot\frac{p^2-1}{24} = \frac{p^2-1}{12}.$$

Step 3: Special case $p=3$

For $p=3$,

$$p^2=9.$$

The equation becomes

$$6m+2n-13=9$$

$$3m+n=11.$$

With $m>n\ge2$, the only solution is

$$(m,n)=(3,2),$$

and by symmetry also $(2,3)$.

So $p=3$ contributes exactly $2$ grids.

Step 4: Final summation

Therefore the required total is

$$2+\sum_{\substack{5\le p<10^6\ p\text{ prime}}}\frac{p^2-1}{12}.$$

2. Python implementation

from sympy import primerange

LIMIT = 10**6

# p = 3 contributes exactly 2 grids
total = 2

# For every prime p > 3:
# contribution = (p^2 - 1) / 12
for p in primerange(5, LIMIT):
    total += (p * p - 1) // 12

print(total)

3. Code walkthrough

from sympy import primerange

Imports a prime generator.

LIMIT = 10**6

We need all primes below one million.

total = 2

Accounts for the special case $p=3$.

for p in primerange(5, LIMIT):

Iterates through all primes $5 \le p < 10^6$.

total += (p * p - 1) // 12

Adds the number of valid grids contributed by that prime.

For primes $p>3$,

$$\text{count}(p)=\frac{p^2-1}{12}.$$

print(total)

Outputs the final answer.

4. Verification

The problem states that for primes below $100$, the answer is $5482$.

Using the same formula:

total = 2
for p in primerange(5, 100):
    total += (p*p - 1)//12
print(total)

produces:

$$5482$$

which exactly matches the statement.

So the derivation is consistent.

Answer: 2057774861813004

Project Euler Problem 313