How to interpret this comment from OEIS A050229?

Question

I've been wracking my brain trying to gleam some insight into this comment from 2007:

Numbers n for which there is a permutation of 0..n-1 such that each number is the sum of all the previous, plus 1, mod n. - R. H. Hardin, Dec 28 2007

The sequence OEIS:A050229 (which is related to OEIS:A001122 "Primes with primitive root 2") begins with:

• 1
• 2
• 3
• 5
• 11
• 13
• 19
• 29

Can someone provide an example of how the permutation definition in the comment would play out?

---

Background:

I was playing around with Lucas' primality test:

• for a number $n$
• $x=n-1$
• let $q$ be the set of factors of $x$
• The test passes if a number $a$ can be found such that:
  • $a^{x}=1 (mod.n)$
  • for each $q$:
    • $a^{x/q}\neq1 (mod.n)$

In my results, $2$ was a valid $a$ such that the sequence A001122 was generated. However, $a^x$ grows unwieldy quite rapidly, and there are many primes with which $a\neq2$ ($a=3$ for 7, 17; $a=5$ for 23). It seems that "primes with primitive root 2" result in $a=2$, which simplifies things down the road. Naturally, I tossed the sequence into OEIS and up came A001122 and upon further reading: A050229.

Now, to give you insight into my level of understanding: I don't fully understand primitive roots, even after reading the Wikipedia page on them and playing around with numbers over the past several days, so maybe I'm missing something obvious. Ultimately this question is just focused on grokking R.H. Hardin's 2007 comment.

Answer 1

Example permutation for $n=5$: $$0,1,2,4,3$$ Zero goes first, because why not? The sum of all numbers so far is $0$, so the next number has to be one bigger, which is $1$.

After putting the $1$ as the next element, the sum of all numbers so far is $1$, so the next number has to be $2$.

Now the sum of all numbers so far is $3$, so the next number must be $4$.

The sum of all numbers so far is $7$, which is congruent to $2$ modulo $5$. Therefore the next number must be $3$.

Answer 2

The fact that $2$ is a primitive root $\bmod p$ says that $2^0,2^1,2^2,\ldots 2^{p-1}$ are all distinct. The comment comes from the fact that the sum of all the powers of $2$ up to $2^n$ plus one is $2^{n+1}$. The permutation he refers to is then $0,1,2,4,8,16, \ldots \bmod p$. The fact that $2$ is a primitive root $\bmod p$ guarantees that the statement is true when starting with $0$. I would be worried that it might be true for other numbers with some other starting value, while the statement seems to imply that it is not.