Project Euler Problem 321

Solution

Answer: 2470433131948040

Let $M(n)$ be the minimum number of moves required to swap the red and blue counters.

1. Mathematical analysis

This is the classic “swapping counters” (or frogs and toads) puzzle.

For $n$ counters on each side, the minimum number of moves is:

$$M(n)=n(n+2)$$

We can verify this with the example:

$$M(3)=3(3+2)=15$$

which matches the problem statement.

We seek those $n$ such that $M(n)$ is a triangular number.

A triangular number has the form

$$T_k=\frac{k(k+1)}{2}$$

So we require

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

Multiplying by 2:

$$2n(n+2)=k(k+1)$$

Expand:

$$2n^2+4n=k^2+k$$

Convert to a Pell equation

Let

$$x=2k+1,\qquad y=n+1$$

Then

$$x^2=(2k+1)^2=4k^2+4k+1$$

and

$$8y^2=8(n+1)^2=8n^2+16n+8$$

Subtract:

$$x^2-8y^2 = (4k^2+4k+1)-(8n^2+16n+8)$$

Using

$$k^2+k=2n^2+4n$$

we get

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

Thus we need positive integer solutions to

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

with

$$n=y-1.$$

The first relevant solutions are:

$$(5,2)\Rightarrow n=1$$

$$(11,4)\Rightarrow n=3$$

All further solutions are generated by multiplying by the fundamental Pell unit

$$3+\sqrt 8.$$

$$x+y\sqrt8$$

is a solution, the next one is

$$(3+\sqrt8)(x+y\sqrt8)$$

which gives the recurrence:

$$x' = 3x+8y$$

$$y' = x+3y$$

Using the two starting branches $(5,2)$ and $(11,4)$, merge and sort the resulting $n=y-1$ values.

The sequence begins:

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

matching the problem statement.

2. Python implementation

def generate_branch(x, y, count):
    """Generate n-values from one Pell branch."""
    values = []

    for _ in range(count):
        values.append(y - 1)  # n = y - 1

        # Pell recurrence
        x, y = 3 * x + 8 * y, x + 3 * y

    return values

# Generate sufficiently many terms from both branches
branch1 = generate_branch(5, 2, 50)
branch2 = generate_branch(11, 4, 50)

# Merge, deduplicate, and sort
sequence = sorted(set(branch1 + branch2))

# Sum first 40 terms
answer = sum(sequence[:40])

print(answer)

3. Code walkthrough

`generate_branch(x, y, count)`

This generates solutions of

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

starting from an initial solution.

values.append(y - 1) converts the Pell variable back to

$$n=y-1$$

The recurrence

x, y = 3*x + 8*y, x + 3*y

applies multiplication by $3+\sqrt8$, producing the next solution.

Two branches

The valid sequence comes from two starting points:

(5, 2)  -> n = 1
(11, 4) -> n = 3

We generate many terms from each branch, merge them, remove duplicates, and sort.

Verification

The first five generated values are:

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

whose sum is

$$99$$

exactly as given.

4. Final verification

The recurrence produces strictly increasing positive integers.
The first five terms match the problem statement.
Computing the first 40 terms gives a large positive integer, consistent with Pell-type exponential growth.

Answer: 2470433131948040