Problem 120: Square Remainders

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Answer

Mathematical Analysis

Binomial Expansion Modulo $a^2$

Using the binomial theorem:

When we add these and reduce modulo $a^2$, only terms with $k = 0$ and $k = 1$ survive (terms with $k \ge 2$ are divisible by $a^2$):

Case Analysis

When $n$ is even:

When $n$ is odd:

Maximizing $r$ for Odd $n$

For odd $n$, $r = 2na \bmod a^2$. We want to maximize $2na \bmod a^2$.

Let $m = n \bmod a$ (since $2na \bmod a^2$ depends only on $n \bmod a$, as $2na \bmod a^2 = a(2n \bmod a)$… let me be more precise).

Actually: $2na \bmod a^2 = a \cdot (2n \bmod a)$. So we want to maximize $2n \bmod a$ where $n$ is odd.

If $a$ is odd: As $n$ ranges over odd values, $2n \bmod a$ takes all values in $\{0, 1, \ldots, a-1\}$ (since $\gcd(2, a) = 1$). The maximum of $2n \bmod a$ is $a - 1$, giving $r_{\max} = a(a-1)$.

If $a$ is even: As $n$ ranges over odd values, $2n$ ranges over $\{2, 6, 10, \ldots\}$, i.e., $2n \equiv 2 \pmod{4}$. Then $2n \bmod a$ can reach at most $a - 2$ (when $a$ is even). So $r_{\max} = a(a-2)$.

Closed-Form Formula

Summation

Computing this sum yields 333082500.

Proof of the Formula

For odd $a$: Since $\gcd(2, a) = 1$, as $n$ ranges over all odd positive integers, the residues $2n \bmod a$ cycle through all residues $\{0, 1, \ldots, a-1\}$. The maximum residue is $a - 1$, achieved when $2n \equiv a - 1 \pmod{a}$, i.e., $n \equiv (a-1)/2 \cdot 1 \pmod{a}$ (using the inverse of 2 mod $a$). Since $(a-1)/2$ is an integer and we can always find an odd $n$ achieving this, $r_{\max} = a(a-1)$.

For even $a$: Write $a = 2m$. Then $2n \bmod a = 2n \bmod 2m = 2(n \bmod m)$. For odd $n$, $n \bmod m$ ranges over values achievable by odd $n$, and the maximum of $2(n \bmod m)$ is $2(m - 1) = a - 2$. Thus $r_{\max} = a(a - 2)$.

Complexity

• Time: $O(N)$ where $N = 1000$.
• Space: $O(1)$.

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

int main() {
    long long total = 0;
    for (int a = 3; a <= 1000; a++) {
        if (a % 2 == 1) {
            total += (long long)a * (a - 1);
        } else {
            total += (long long)a * (a - 2);
        }
    }
    cout << total << endl;
    return 0;
}

"""
Problem 120: Square Remainders

For 3 <= a <= 1000, find the sum of r_max where r_max is the maximum
remainder when (a-1)^n + (a+1)^n is divided by a^2.

Key insight: r_max = a*(a-1) for odd a, a*(a-2) for even a.
"""

def r_max(a):
    if a % 2 == 1:
        return a * (a - 1)
    else:
        return a * (a - 2)

answer = sum(r_max(a) for a in range(3, 1001))
print(answer)