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.
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$.
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.
3 comment threads