Problem 2521

Answer. $n = 2^k - 1$ for any $k \in \mathbb{N}$.

We begin by noting that the sequence is given by the formula
$$a_{rn+s} = r \cdot \binom{n+1}{2} + \binom{s+1}{2}$$
for all $\ge 0$ and $s = 1, 2, \dots, n$. This is easy to confirm by mathematical induction: $a_0 = 0$ is true, and for fixed $r$, inducting on $s$ gives
$$a_{rn+s} = a_{rn+s-1} + s = r \cdot \binom{n+1}{2} + \binom{(s-1)+1}{2} + s = r \cdot \binom{n+1}{2} + \binom{s+1}{2},$$
proving this induction step. Finally, $a_{(r+1)n} = (r+1)\binom{n+1}{2} = r \cdot \binom{n+1}{2} + \binom{n+1}{2} = a_{rn+n}$, confirming the induction argument on $r$ as well, proving the claim.

Now suppose $n+1$ has an odd prime factor $p$. Then $p \mid \binom{n+1}{2}$, so if all residues mod $(n+1)^2$ are present, then $\binom{s+1}{2} \equiv \frac{s^2+s}{2} \pmod{p}$ covers all possible residues mod $p$. However, the map $x \mapsto x^2+x \pmod{p}$ sends $x$ and $-(1+x)$ to the same element mod $p$ and the two are distinct unless $x \equiv \frac{-1}{2} \pmod{p}$, hence the set of residues represented by $s^2+s \pmod{p}$ has $\frac{p+1}{2} < p$ elements, a contradiction! So every $n$ that satisfies this condition must be one less than a power of 2.

Now we prove that all $n$ one less than powers of 2 satisfy the condition. Let $n = 2^k - 1$. Then $\binom{n+1}{2} = 2^{k-1}(2^k - 1) = 2^{2k-1} - 2^{k-1} \pmod{2^{2k}}$. Then, if for $0 \le r$ and $1 \le s \le n$, and $r = 2j + e$, where $e \in \{0, 1\}$, then
$$a_{rn+s} = -j \cdot (n+1) + e \cdot \binom{n+1}{2} + \binom{s+1}{2} \pmod{(n+1)^2}.$$
Notice that for $s = 1, 2, \dots, n$, the numbers $\binom{s+1}{2}$ are all distinct mod $n+1$. Indeed, if $1 \le s < t \le n$ and $\binom{s+1}{2} = \binom{t+1}{2} \pmod{n+1}$, then $(2n+2) \mid (s-t)(s+t+1)$, and since $s, t$ have opposite parities and $2n+2 > 2n+1 \ge s+t+1 > |s-t| > 0$, we arrive at a contradiction as $2n+2$ is a power of 2, proving that the residues are distinct mod $n+1$. Also, note that none of these residues are 0 (mod $n+1$). Thus, $-j(n+1) + \binom{s+1}{2}$ (where $e=0$) covers all $n^2+n$ residues which are not of the form $l(n+1) \pmod{(n+1)^2}$.

Finally, for the remaining residues, take $s = n$ and $e = 1$, we get $-j(n+1)+2\binom{n+1}{2} = -(j+1)(n+1) \pmod{(n+1)^2}$, so that which covers the remaining residues as $j$ varies. $\square$