Problem 321: Swapping Counters

Project Euler Problem 321 Solution

EulerSolve provides an optimized solution for Project Euler Problem 321, Swapping Counters, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

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,$$

$$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.

$$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.$$

Problem 321 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;
using i128 = __int128_t;

struct Options {
    int terms = 40;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--terms=", options.terms)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.terms >= 1;
}

struct PellState {
    i128 x;
    i128 y;
};

u64 sum_first_terms(const int count) {
    PellState a{5, 2};    // Gives n=1
    PellState b{11, 4};   // Gives n=3

    auto next_state = [](PellState s) {
        // Multiply x + y*sqrt(8) by 3 + sqrt(8).
        const i128 nx = 3 * s.x + 8 * s.y;
        const i128 ny = s.x + 3 * s.y;
        return PellState{nx, ny};
    };

    u64 sum = 0ULL;
    int taken = 0;
    while (taken < count) {
        const u64 na = static_cast<u64>(a.y - 1);
        const u64 nb = static_cast<u64>(b.y - 1);
        if (na < nb) {
            sum += na;
            a = next_state(a);
        } else {
            sum += nb;
            b = next_state(b);
        }
        ++taken;
    }
    return sum;
}

bool run_checkpoints() {
    if (sum_first_terms(5) != 99ULL) {
        std::cerr << "Checkpoint failed for first five-term sample sum" << '\n';
        return false;
    }
    if (sum_first_terms(1) != 1ULL) {
        std::cerr << "Checkpoint failed for first term" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << sum_first_terms(options.terms) << '\n';
    return 0;
}

Python

def solve(terms=40):
    a_x, a_y = 5, 2
    b_x, b_y = 11, 4
    
    total = 0
    taken = 0
    while taken < terms:
        na = a_y - 1
        nb = b_y - 1
        if na < nb:
            total += na
            nx = 3 * a_x + 8 * a_y
            ny = a_x + 3 * a_y
            a_x, a_y = nx, ny
        else:
            total += nb
            nx = 3 * b_x + 8 * b_y
            ny = b_x + 3 * b_y
            b_x, b_y = nx, ny
        taken += 1
        
    return str(total)

if __name__ == '__main__':
    print(solve())

Java

public class Euler321 {
    static class PellState {
        long x, y;

        PellState(long x, long y) {
            this.x = x;
            this.y = y;
        }
    }

    public static String solve() {
        int terms = 40;
        PellState a = new PellState(5, 2);
        PellState b = new PellState(11, 4);

        long sum = 0;
        int taken = 0;
        while (taken < terms) {
            long na = a.y - 1;
            long nb = b.y - 1;
            if (na < nb) {
                sum += na;
                long nx = 3 * a.x + 8 * a.y;
                long ny = a.x + 3 * a.y;
                a.x = nx;
                a.y = ny;
            } else {
                sum += nb;
                long nx = 3 * b.x + 8 * b.y;
                long ny = b.x + 3 * b.y;
                b.x = nx;
                b.y = ny;
            }
            taken++;
        }
        return String.valueOf(sum);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}