An interesting list ordering result based on skipping indexes by value entered

Question

This is something interesting I've found while attempting to shuffle $n$ values in a list is a deterministic way intended to look "random-ish". The idea is that you sort a number of values $r$ from $0...n-1$ into a list by starting with an index value $i=0$, then calculate the index for the new item to be inserted using the formula $i_1 = (i_0 + r)\mod n$. What I've found is that in most cases, there are several collisions where a number is placed over another except when $n = 2^k, k\in Z$.

I wrote a Python program to do this and display the output.

>>> for n in range(5,11):
    print('_____')
    num_list = ['' for i in range(n)]
    i = 0
    for r in range(n):
        i = (i + r) % n
        num_list[i] += str(r) + ','
    for x in range(n):
        print(str(x)+'|'+num_list[x])


_____
0|0,4,
1|1,3,
2|
3|2,
4|
_____
0|0,3,
1|1,
2|
3|2,5,
4|4,
5|
_____
0|0,6,
1|1,5,
2|
3|2,4,
4|
5|
6|3,
_____
0|0,
1|1,
2|4,
3|2,
4|7,
5|6,
6|3,
7|5,
_____
0|0,8,
1|1,4,7,
2|
3|2,6,
4|
5|
6|3,5,
7|
8|
_____
0|0,4,
1|1,6,
2|
3|2,
4|
5|5,9,
6|3,8,
7|
8|7,
9|
>>> 

As you can see, multiple numbers are assigned to the same value for all cases except where n is a power of 2. Can anyone explain this?

Answer 1

In other words, there are $n$ buckets $B_0, \ldots, B_{n - 1}$ and we throw $r$ into a bucket $B_{0 + 1 + \ldots + r\pmod{n}}$. The question then is for which $n$ all the buckets contain exactly one element. This is true if and only if $0 + 1 + \ldots + r\pmod{n}$, $r = 0, \ldots, n - 1$ are all different. In turn, the latter is true if and only if for all $r_1, r_2\in\{0, 1, \ldots, n - 1\}$, $r_1 < r_2$ it holds that $(0 + 1 + \ldots + r_2) - (0 + 1 + \ldots + r_1)$ is not divisible by $n$. And I will show that indeed this is true if and only if $n$ is a power of $2$.

Re-write $(0 + 1 + \ldots + r_2) - (0 + 1 + \ldots + r_1)$ as follows: $$(0 + 1 + \ldots + r_2) - (0 + 1 + \ldots + r_1) = \frac{r_2(r_2 + 1)}{2} - \frac{r_1(r_1 + 1)}{2} = \frac{(r_2 - r_1) (r_2 + r_1 + 1)}{2}.$$ First consider the case $n = 2^k$. Assume that the last expression is divisible by $n = 2^k$. This means that $(r_2 - r_1)(r_2 + r_1 + 1)$ is divisble by $2^{k + 1} = 2n$. Note that $(r_2 - r_1)$ and $(r_2 + r_1 + 1)$ have different parity. This means that one of these two numbers is divisible by $2n$. Both if these numbers are positive. Hence one number should be at least $2n$. This is impossible since $r_1, r_2 \le n - 1$.

Now consider the case $n = 2^k \cdot u$ for some $k\ge 0$ and some odd $u \ge 3$. Set \begin{align*} r_1 &= \begin{cases} \frac{2^{k + 1} - u - 1}{2} & \mbox{ if } u < 2^{k + 1}, \\ \frac{u - 2^{k + 1} - 1}{2} & \mbox{ if } u > 2^{k + 1},\end{cases} \\ r_2 &= \frac{2^{k + 1} + u - 1}{2}. \end{align*} You see that there are two subcases, $u < 2^{k + 1}$ and $u > 2^{k + 1}$ (equality is impossible because $u$ is odd). In the first case we have $r_2 - r_1 = u$ and $(r_2 + r_1 + 1) = 2^{k + 1}$. In the second case we have $r_2 - r_1 = 2^{k + 1}$ and $r_1 + r_2 + 1 = u$. In either case we obtain $$\frac{(r_2 - r_1) (r_2 + r_1 + 1)}{2} = 2^k\cdot u = n,$$ which means that $(0 + 1 + \ldots + r_1) \equiv (0 + 1 + \ldots + r_2)\pmod{n}$. We should also check that $r_1, r_2\in\{0, 1, \ldots, n - 1\}$ and $r_1 < r_2$. This all is obvious with one exception: it is not clear why $r_2 \le n - 1$. Actually, it is the only place where we use the fact that $n$ is not a power of $2$. So our goal is to verify that $$\frac{2^{k + 1} + u - 1}{2} \le n - 1 = 2^k \cdot u - 1.$$ This is equivalent to the following: $$2^{k + 1} + u \le 2^{k + 1} \cdot u - 1 = 2^k\cdot u + 2^k \cdot u - 1. $$ So why is this true? Because $u\le 2^k \cdot u$ and $2^{k + 1} = 2\cdot 2^k < u \cdot 2^k$ (the latter is due to the fact that $u\ge 3$)