Problem Summary

We have \(n\) red counters, one empty square, and \(n\) blue counters in a row of length \(2n+1\). A legal move is either:

1) a slide into the adjacent empty square, or

2) a hop over exactly one counter into an empty square.

Let \(M(n)\) be the minimum number of moves needed to swap the two color blocks completely. We want those \(n\) for which \(M(n)\) is a triangular number, and we must sum the first 40 such \(n\).

Mathematical Approach

1) The minimal move count is \(M(n)=n(n+2)\).

This is the key fact. It comes from two separate lower bounds that are both forced, and both can be achieved.

2) Why there must be exactly \(n^2\) hops.

Initially every red counter lies to the left of every blue counter. In the final arrangement every red counter lies to the right of every blue counter. So each red-blue pair must reverse its order exactly once.

There are

$$n^2$$

such pairs. A slide never changes the order of two counters, while a hop over one counter changes the order of exactly one pair. Therefore every solution needs at least

$$n^2$$

hops.

3) Why there must be exactly \(2n\) slides.

Consider total displacement. Each red counter moves from the left block to the right block, so each red moves \(n+1\) squares to the right. Each blue counter moves \(n+1\) squares to the left. Thus the total absolute displacement is

$$2n(n+1).$$

A slide contributes \(1\) unit of displacement and a hop contributes \(2\). If a solution uses \(s\) slides and \(h\) hops, then

$$s+2h=2n(n+1).$$

Since we already know \(h\ge n^2\), we get

$$s\le 2n(n+1)-2n^2=2n.$$

But we also need at least one slide every time the empty square changes side in the alternating optimal pattern, and the classical construction reaches the target with exactly \(2n\) slides. Hence the minimum is achieved at

$$h=n^2,\qquad s=2n,$$

so

$$M(n)=h+s=n^2+2n=n(n+2).$$

4) Triangular-number condition.

Now impose that \(M(n)\) is triangular. So for some integer \(m\),

$$\frac{m(m+1)}{2}=n(n+2).$$

This is the exact Diophantine equation solved by the program.

5) Convert to a Pell-type equation.

Introduce

$$x=2m+1,\qquad y=n+1.$$

Then

$$m=\frac{x-1}{2},\qquad n=y-1.$$

Substituting into

$$\frac{m(m+1)}{2}=n(n+2)$$

gives

$$\frac{x^2-1}{8}=y^2-1,$$

hence

$$x^2-8y^2=-7.$$

So the problem becomes: find positive integer solutions \((x,y)\) of

$$x^2-8y^2=-7,$$

then recover

$$n=y-1.$$

6) Pell recurrence.

If

$$x+y\sqrt8$$

solves \(x^2-8y^2=-7\), then multiplying by the fundamental unit

$$3+\sqrt8$$

preserves the norm. Therefore another solution is

$$(x+y\sqrt8)(3+\sqrt8)=x'+y'\sqrt8,$$

with

$$x'=3x+8y,\qquad y'=x+3y.$$

7) The two relevant positive branches.

The solutions needed for the problem come from the two smallest positive seeds

$$(x,y)=(5,2),\qquad (x,y)=(11,4).$$

These produce the two increasing \(n\)-streams:

From \((5,2)\):

$$n=1,10,63,372,\dots$$

From \((11,4)\):

$$n=3,22,133,780,\dots$$

Merging them gives the full increasing sequence

$$1,3,10,22,63,\dots$$

which matches the statement.

8) Worked checkpoint.

The first five terms are

$$1,\ 3,\ 10,\ 22,\ 63,$$

and their sum is

$$1+3+10+22+63=99.$$

This is exactly the checkpoint used in the C++ code.

Algorithm

1) Start two Pell states at \((5,2)\) and \((11,4)\).

2) Convert each state to \(n=y-1\).

3) Repeatedly take the smaller of the two current \(n\)-values.

4) Advance the branch you used via

$$x'=3x+8y,\qquad y'=x+3y.$$

5) Stop after 40 terms and sum them.

Complexity Analysis

To obtain the first \(K\) valid values, we perform only \(K\) recurrence steps and constant-time merging work. So the complexity is

$$O(K)$$

time and

$$O(1)$$

extra memory.

Checks And Final Result

The code verifies

$$1+3+10+22+63=99.$$

For the first 40 terms, the final answer is

$$2470433131948040.$$

Further Reading

1. Problem page: https://projecteuler.net/problem=321
2. Pell equations: https://en.wikipedia.org/wiki/Pell's_equation
3. Triangular numbers: https://en.wikipedia.org/wiki/Triangular_number