Post History
#2: Post edited
by
celtschk
·
2024-06-09T18:49:28Z (19 days ago)
Fixed some errors
- 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 k$ is a bijection on the set $\{0,\ldots,n-1\}$.- Or stated differently: For those $n$ I tested, all numbers are triangular modulo $2^n$.
- That rises two related questions:
- 1. Does this hold for every $n$?
- 2. 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?
- 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:
- 1. Does this hold for every $n$?
- 2. 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: Initial revision
by
celtschk
·
2024-06-09T09:20:21Z (19 days ago)
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 k$ is a bijection on the set $\{0,\ldots,n-1\}$.
Or stated differently: For those $n$ I tested, all numbers are triangular modulo $2^n$.
That rises two related questions:
1. Does this hold for every $n$?
2. 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?