Problem 321: Swapping Counters

Solution

Reduction to a Pell-type equation

Proposition 1. The positive integer $n$ satisfies the requirement that $n(n+2)$ is triangular if and only if there exists a positive integer $k$ such that

Theorem 1. The equation $n(n+2) = \frac{k(k+1)}{2}$ with $n,k \geq 1$ is equivalent to the generalised Pell equation

under the substitution $x = 2k+1$, $y = n+1$.

Proof. Multiplying both sides of $n(n+2) = \frac{k(k+1)}{2}$ by 8 yields

Completing the square on each side:

Setting $x = 2k+1$ and $y = n+1$ gives $x^2 - 8y^2 = -7$. Since $n \geq 1$ forces $y \geq 2$ and $k \geq 1$ forces $x \geq 3$ (with $x$ odd), the correspondence is bijective: every admissible pair $(n,k)$ yields a solution $(x,y)$ with $y \geq 2$ and $x \geq 3$ odd, and conversely every such solution yields $n = y - 1 \geq 1$ and $k = (x-1)/2 \geq 1$. $\square$

Enumeration of solutions

Lemma 1 (Fundamental solutions). The equation $x^2 - 8y^2 = -7$ has exactly two classes of solutions, with fundamental representatives $(x,y) = (1,1)$ and $(x,y) = (5,2)$.

Proof. Checking $y = 1$: $x^2 = 8 - 7 = 1$, so $(1,1)$ is a solution. Checking $y = 2$: $x^2 = 32 - 7 = 25$, so $(5,2)$ is a solution. For $y \geq 3$ we have $x^2 = 8y^2 - 7 \geq 65$, and one verifies that the next solutions in each class (generated by the recurrence below) have $y = 4$ and $y = 7$ respectively, confirming no intermediate solutions exist. $\square$

Theorem 2 (Recurrence for solutions). If $(x_i, y_i)$ is a solution of $x^2 - 8y^2 = -7$, then so is

Moreover, within each family the $y$-values satisfy the linear recurrence $y_{i+2} = 6y_{i+1} - y_i$, and consequently the $n$-values satisfy

Proof. The fundamental solution of the associated Pell equation $u^2 - 8v^2 = 1$ is $(u,v) = (3,1)$. In the ring $\mathbb{Z}[\sqrt{8}]$, multiplication by the unit $3 + \sqrt{8}$ maps solutions of $x^2 - 8y^2 = -7$ to solutions, since the norm is multiplicative:

Explicitly, $(x_i + y_i\sqrt{8})(3 + \sqrt{8}) = (3x_i + 8y_i) + (x_i + 3y_i)\sqrt{8}$, giving the stated formulas.

For the second-order recurrence, applying the map twice yields $y_{i+2} = (x_{i+1} + 3y_{i+1})$. Substituting $x_{i+1} = 3x_i + 8y_i$ and $x_i = y_{i+1} - 3y_i$ (from $y_{i+1} = x_i + 3y_i$), we obtain

Since $n_i = y_i - 1$, substituting gives $(n_{i+2}+1) = 6(n_{i+1}+1) - (n_i+1)$, whence $n_{i+2} = 6n_{i+1} - n_i + 4$. $\square$

Two families of valid $n$-values

Applying the recurrence $n_{i+2} = 6n_{i+1} - n_i + 4$:

• Family A (from $(x,y)=(1,1)$, i.e., $n_0 = 0, n_1 = 3$): $\;0, 3, 22, 133, 798, 4785, \ldots$
• Family B (from $(x,y)=(5,2)$, i.e., $n_0 = 1, n_1 = 10$): $\;1, 10, 55, 322, 1929, 11566, \ldots$

Discarding $n = 0$ from Family A and merging both families in sorted order, the first 40 positive values are collected and summed.

Editorial

We seek positive integers n such that M(n) = n(n+2) is a triangular number. The substitution x = 2k+1, y = n+1 transforms n(n+2) = k(k+1)/2 into the generalised Pell equation x^2 - 8y^2 = -7, whose solutions fall into two families, each satisfying n_{i+2} = 6 n_{i+1} - n_i + 4.

Pseudocode

    A = [0, 3]
    B = [1, 10]
    For i from 2 to 24:
        A.append(6 * A[i-1] - A[i-2] + 4)
        B.append(6 * B[i-1] - B[i-2] + 4)
    values = sorted(A[1:] + B)
    Return sum(values[:40])

Complexity

• Time: $O(N)$ where $N = 40$. Each family requires $\lceil N/2 \rceil$ terms, each computed in $O(1)$ arithmetic operations.
• Space: $O(N)$.

Answer

#include <bits/stdc++.h>
using namespace std;

/*
 * Problem 321: Swapping Counters
 *
 * n(n+2) = k(k+1)/2  <==>  x^2 - 8y^2 = -7  (x = 2k+1, y = n+1).
 * Two families of solutions with recurrence n_{i+2} = 6 n_{i+1} - n_i + 4.
 * Family A seeds: n = 0, 3.   Family B seeds: n = 1, 10.
 */

int main() {
    vector<long long> vals;

    // Family A (skip n = 0)
    long long a0 = 0, a1 = 3;
    vals.push_back(a1);
    for (int i = 2; i < 25; i++) {
        long long a2 = 6 * a1 - a0 + 4;
        vals.push_back(a2);
        a0 = a1;
        a1 = a2;
    }

    // Family B
    long long b0 = 1, b1 = 10;
    vals.push_back(b0);
    vals.push_back(b1);
    for (int i = 2; i < 25; i++) {
        long long b2 = 6 * b1 - b0 + 4;
        vals.push_back(b2);
        b0 = b1;
        b1 = b2;
    }

    sort(vals.begin(), vals.end());

    long long ans = 0;
    for (int i = 0; i < 40; i++)
        ans += vals[i];

    cout << ans << endl;
    return 0;
}

"""
Problem 321: Swapping Counters

We seek positive integers n such that M(n) = n(n+2) is a triangular number.
The substitution x = 2k+1, y = n+1 transforms n(n+2) = k(k+1)/2 into the
generalised Pell equation x^2 - 8y^2 = -7, whose solutions fall into two
families, each satisfying n_{i+2} = 6 n_{i+1} - n_i + 4.
"""


def solve():
    # Family A seeds: n = 0, 3 (from fundamental solution (1,1))
    # Family B seeds: n = 1, 10 (from fundamental solution (5,2))
    a_prev, a_cur = 0, 3
    b_prev, b_cur = 1, 10

    vals = [a_cur, b_prev, b_cur]  # skip a_prev = 0
    for _ in range(23):
        a_prev, a_cur = a_cur, 6 * a_cur - a_prev + 4
        b_prev, b_cur = b_cur, 6 * b_cur - b_prev + 4
        vals.append(a_cur)
        vals.append(b_cur)

    vals.sort()
    print(sum(vals[:40]))


if __name__ == "__main__":
    solve()