Triangular Numbers Modulo $k$ - Hit All Values? The sequence of triangular numbers is well known. Consider now the triangular numbers modulo some positive natural number $k$. That is, let $T_{n,k}$ be the remainder of dividing $T_n$ by $k$. For the regular sequence of triangular numbers, we can take as convention $T_n = T_{n, \infty}$.
Question: For all values of $k, i < k$, does there exists some $n$ such that $T_{n, k} = i$
 A: It is easy to see that this is False if $k$ is not a power of $2$:
To do it we just need to see that it is false $\pmod p$ for odd primes $p$.  But for odd primes $p$ we simply remark that, $\pmod p$, $T_n=\frac {n (n+1)}2$ only depends on $n\pmod p$ and both $T_0$ and $ T_{p-1}$ are $0\pmod p$.
Now, for $k=2^m$ it appears that it might be true.  I have checked $k=2,4,8,16,32$ and it works for each.  It would be interesting to resolve this for general powers of $2$.
EDIT:  unsurprisingly, this appears to be known (if not exactly well known).  Most authors credit Knuth, as in this reference.
EDIT (Based on comments):
To expand on paragraph 2, consider the function $i \mapsto T_i \mod(p)$ for $i$ in $\{0, 1, \dots, p-1\}$. Since $T_0 \equiv T_{p-1} \equiv 0$, then , by the pigeon hole principle, there must be some $j$ in $\{0, 1, \dots, p-1\}$ not mapped by the function. Now, it remains to show that $T_{n} \equiv T_{n\bmod{p}}$ for all $n$, because then there can't be any $T_n$ such that $T_n \equiv j$.
Lemma: The triangle number at $n$ is congruent to the triangle number at the residue of $n$.
$$T_{n} \equiv T_{n\bmod{p}}$$
Proof: Let $k$ be the residue of $n$ with respect to $p$. We know that
$$n(n + 1) \equiv k(k + 1)$$
We also know that both sides of the equation must be even, so let $n(n + 1) = 2N$ and let $k(k + 1) = 2K$, then:
$$2N \equiv 2K$$
and so, because we're working mod a prime $p > 2$, and all numbers less than a prime are coprime to it, we can divide the $2$ from both sides, giving the desired result.
A: With Lulu's argument, and permission (thanks Lulu) I will answer this. The answer to the question is no. The counterexample is $k=3, i=2$.
We want to prove that for all $n$, $T_{n, 3} \neq 2$, noting that $T_{n+1} = T_n + n + 1$. Rather than prove this, we prove a theorem that implies this:


*

*$T_{n, 3} = 1$ whenever $n \equiv 1$ (mod $3$)

*$T_{n, 3} = 0$ otherwise.


We proceed by induction on $n$, noting that $T_{n,k} = r$ is the same thing as saying $T_n \equiv r$ (mod $k$).
Base case: $n = 0$, $T_n = 0$, $T_{n, 3}=0$ and we're done.
Inductive case: There are three sub-cases to consider:


*

*If $n \equiv 1$ (mod $3$), then $n+1 \equiv 2$ (mod $3$), and by I.H. $T_n\equiv 1$ (mod $3$). By triangle number definition, $T_{n+1} = T_n + n + 1 \equiv 0$ (mod $3$), as required.

*If $n \equiv 0$ (mod $3$), then $n+1 \equiv 1$ (mod $3$), and by I.H. $T_n\equiv 0$ (mod $3$). By triangle number definition, $T_{n+1} = T_n + n + 1 \equiv 1$ (mod $3$), as required.

*If $n \equiv 2$ (mod $3$), then $n+1 \equiv 0$ (mod $3$), and by I.H. $T_n\equiv 0$ (mod $3$). By triangle number definition, $T_{n+1} = T_n + n + 1 \equiv 0$ (mod $3$), as required.
