Post History

A shorter proof that not all numbers are triangular mod non-powers of 2 is that non-powers of two have odd prime factors, and clearly there are exactly $\frac{p+1}2$ triangular numbers mod any odd prime $p$.<sup>1</sup> The Chinese Remainder theorem lets us generalize the result for odd primes to any non-power of 2.

To prove that all numbers are triangular mod a power of 2, one uses an inductive argument that, given a number $n$, lets us compute (bit by bit, literally) a number $m$ such that $n$ is the $m$th triangular number!

Thus, let $T(n)$ be the $n$th triangular number and assume as our inductive hypothesis that the "restriction" of $T$ to the residues mod $2^{m-1}$ is a bijection<sup>2</sup>. Then we must prove that the "restriction" of $T$ to the residues mod $2^m$ is a bijection. Clearly $T(0…2^{m-1})$ will give us half the numbers mod $2^m$ that we need; we just need to find the other half, which will differ from this half by $2^{m-1}$. Fortunately, for any $i$ such that $0 ≤ i < 2^{m-1}$, $T(2^m - 1 - i) \cong T(i) + 2^{m-1}$, exactly as desired!

This gives us a constructive algorithm for computing $T^{-1}(i)$ mod $2^n$ for any $n$: define $m$ such that $0 ≤ m < 2^{n-1}$ and $T(m) \cong i$ mod $2^{n-1}$ (we can do this by recursion); then if $T(m) \cong i \pmod{2^n}$ we are done, and otherwise $T(m) \cong i+2^{n-1} \pmod{2^n}$ and so $T(2^n - 1 - m) \cong T(m)+2^{n-1} \cong i+2^{n-1}+2^{n-1} \cong i \pmod{2^n}$ and we return $2^n-1-m$.

In Scheme:

```
(define ‰ remainder)
(define (trinum x) (apply + (iota (+ x 1))))
(define (inverse-trinum-mod-p2 exp n) (define 2^e (expt 2 exp)) (if (= exp 1) (if (even? n) 0 1) (let ((m (inverse-trinum-mod-p2 (- exp 1) n))) (if (= (‰ n 2^e) (‰ (trinum m) 2^e)) m (- 2^e 1 m)))))
(let ((testnum 19573)) (= (‰ (trinum (inverse-trinum-mod-p2 20 testnum)) 1048576) testnum)
```

(I think this is the same as Knuth's argument, but I haven't gotten to see it yet.) 

---
<sup>1</sup>This is because the $n$th triangular number is just $\frac12 n(n+1) = \frac12 (n^2+\frac12 n-\frac14)$, which means there are as many triangular numbers mod $p$ as there are quadratic residues mod $p$.

<sup>2</sup>That is, more precisely, that, for any $0 ≤ i,j < 2^{m-1}$, $T(i) \cong T(j) \pmod{2^{m-1}} \Rightarrow i=j$.