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?
1 answer
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 check... |
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