Triangular Numbers Modulo $k$ - Hit All Values?

Solution 1:

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.

Solution 2:

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.