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?
2 answers
You are accessing this answer with a direct link, so it's being shown above all other answers regardless of its score. You can return to the normal view.
The following users marked this post as Works for me:
| User | Comment | Date |
|---|---|---|
| celtschk |
Thread: Works for me Thank you. That's a quite elegant proof (I actually never considered that the odd numbers form a group modulo a power of two, though it's easy to c... |
Jun 10, 2024 at 17:42 |
Only if: suppose $N = 2^a m$ with $m$ odd and greater than $1$.
Because the odd numbers form a multiplicative group modulo $2^{a+1}$, there are $j_0$, $j_1$ such that $j_0 m \equiv 1 \pmod{2^{a+1}}$ and $j_1 m \equiv -1 \pmod{2^{a+1}}$. We have $(j_0 + j_1)m \equiv 0 \pmod{2^{a+1}}$ and since $m$ is odd, $j_0 + j_1 \equiv 0 \pmod{2^{a+1}}$. They're both odd, so identifying the equivalence classes with their representatives in the range $(0, 2^{a+1})$ we get $j_0 + j_1 = 2^{a+1}$, whence $\min(j_0, j_1) < 2^a$.
If $j_0 < 2^a$, consider $(j_0 m - 1)(j_0 m)$. It is divisible by $2^{a+1}$ and $m$, so $\Delta_{j_0 m - 1} \equiv 0 \pmod N$, but $j_0 m - 1 \not\equiv 0 \pmod N$.
If $j_1 < 2^a$, consider $(j_1 m)(j_1 m + 1)$. It is divisible by $2^{a+1}$ and $m$, so $\Delta_{j_1 m} \equiv 0 \pmod N$, but $j_1 m \not\equiv 0 \pmod N$.
Either way, a counting argument shows that some equivalence class modulo $N$ is not covered.
The assumption that $m$ is greater than $1$ is relevant because otherwise $j_0 = 1$ and we don't show that the equivalence class of $0$ is covered by multiple triangle numbers.
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