Triangular numbers ($\text{mod } 2^n$) as a permutation of $\{0,1,2,\dots,2^n-1\}$

Solution 1:

I'll be using $\equiv$ between non-integers to denote that the two sides differ by a multiple of the modulus $b^k$.

The map is a permutation, that is, bijective, exactly if $\frac12m(m+1)\equiv\frac12n(n+1)$ implies $m=n$ for $0\le m,n\lt b^k$. So assume $\frac12m(m+1)\equiv\frac12n(n+1)$. Adding $\frac18$ yields $\frac12\left(m+\frac12\right)^2\equiv\frac12\left(n+\frac12\right)^2$. Bringing both terms to one side and factoring the difference yields $\frac12\left(m+\frac12+n+\frac12\right)\left(m+\frac12-n-\frac12\right)\equiv0$, that is, $\frac12\left(m+n+1\right)\left(m-n\right)=rb^k$.

Now if $b=2$, since $m+n+1$ and $m-n$ have different parity, at most one of them can contribute factors of $2$. Moreover, since $m,n\lt 2^k$, either factor can contain at most $k$ factors of $2$ unless $m=n$. One factor is divided out by the factor $\frac12$, so the equation cannot be fulfilled unless $m=n$.

This argument doesn't work for $b\ne2$; indeed we can always choose $m=b^k-1$ and $n=0$ to get $k$ factors of $b$ in $n+k+1$, and none of them are divided out.