Comments on All numbers are triangular modulo $N$ iff $N$ is a power of $2$?
Parent
All numbers are triangular modulo $N$ iff $N$ is a power of $2$?
When thinking about binary representations of triangular numbers, I noticed an interesting property:
In the cases I've tested, for the numbers from $0$ to $2^n-1$, each combination of the last $n$ bits occurs exactly once, that is, $k\mapsto k(k+1)/2 \bmod 2^n$ is a bijection on the set $\{0,\ldots,2^n-1\}$.
Or stated differently: For those $n$ I tested, all numbers are triangular modulo $2^n$.
That rises two related questions:
- Does this hold for every $n$?
- What happens modulo a number $N$ that's not of the form $N=2^n$?
Or short: For which $N$ are all numbers triangular modulo $N$?
Now it is easily checked that this cannot hold for odd $N$ other than $N=1$, since in that case $(N-1)N/2 \equiv 0 \pmod N$ because the denominator does not cancel out any factor in $N$.
I've checked with Python code for $N<10000$, and found that for those, it's exactly the powers of $2$ that fulfil the condition.
Therefore my conjecture is:
All numbers are triangular modulo $N$ iff $N$ is a power of $2$.
However I have no idea how I could proof (or disproof, other than by a counterexample, which I've obviously not found) this conjecture.
Can you shed some light on it?
Post
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$.1 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 bijection2. 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.)
1This is because the $n$th triangular number is just $\frac12 n(n+1) = \frac12 ((n+\frac12)^2-\frac14)$, which means there are as many triangular numbers mod $p$ as there are quadratic residues mod $p$.
2That is, more precisely, that, for any $0 ≤ i,j < 2^{m-1}$, $T(i) \cong T(j) \pmod{2^{m-1}} \Rightarrow i=j$.
3 comment threads