**Background:** I was trying to prove something having to do with cyclic group actions on matroids and was able to show that what I want holds if a particular elementary-looking number-theoretic property holds, but upon closer inspection it holds for some primes and not others and now I am wondering if this "elementary" problem is known/studied somewhere or perhaps it is an open problem--I have no idea since I only stumbled into it entirely accidentally. Even learning what area it should be considered, what potential tools there are for studying it, and what else it might be related to (even just keywords to search for!) would be helpful.


**The problem statement:** Let $p$ be an odd prime and consider the permutation of the set $\{1,\ldots,\frac{p-1}{2}\}$ defined by sending $n$ to $\frac{n}{2}$ if $n$ is even and sending it to $\frac{p-n}{2}$ if $n$ is odd. For which primes $p$ does this permutation have a single orbit? 


Here are some examples of iterating this function:


$p=7$) $1 \mapsto 3 \mapsto 2 \mapsto 1$, so it is transitive.


$p=11$) $1 \mapsto 5 \mapsto 3 \mapsto 4 \mapsto 2 \mapsto 1$, so it is transitive.


$p=13$) $1 \mapsto 6 \mapsto 3 \mapsto 5 \mapsto 4 \mapsto 2 \mapsto 1$, so it is transitive.


$p=17$) $1 \mapsto 8 \mapsto 4 \mapsto 2 \mapsto 1$: here there are two orbits of size 4.


This reminds at least loosely in spirit of the Collatz conjecture but I presume (and hope!) it is much simpler since for each $p$ there are only finitely many numbers to consider. We tried some computer experiments and found lots of primes for which there is a single orbit and also lots for which there is not; we put the sequence of "good" primes in the OEIS and did not find any matches, which makes me suspect there is not something simple like a congruence condition on the prime, but I don't know any number theory so I really have no idea.



For which primes does this iterated function act transitively? (Sort of a finite analogue of Collatz conjecture.)
It's easier to work with the inverse permutation. Starting from $1$ and working backwards we end up with a sequence $1=2^0\to \pm 2^1\to \pm 2^2\to \cdots \to\pm 2^{\frac{p-1}{2}}=1$. Where the signs are uniquely determined so that $\pm 2^r\in \{1,2,\dots,\frac{p-1}{2}\}$. This cycle covers all numbers in $\{1,2,\dots,\frac{p-1}{2}\}$ exactly once if and only if $2^r\neq \pm 1\pmod{p}$ for any $1\le r\le \frac{p-3}{2}$. 


**Proposition:** This happens precisely when either $2$ is a primitive root for $p$, or if $p=7\pmod 8$ and $2$ has order $\frac{p-1}{2}$. 


**Proof:** In the situation that $2^{\frac{p-1}{2}}=-1\pmod{p}$ we have that $2^r$ for $r=1,2,\cdots, p-1$ forms a complete system of residues, therefore $2$ is a primitive root for $p$. We are left with the case where $2^{\frac{p-1}{2}}=1\pmod{p}$. This means that $2$ has order $\frac{p-1}{2}$ in $\mathbb Z/p\mathbb Z$ and moreover $-1$ is not of the form $2^r\pmod{p}$. In turn, this implies $2$ is the square of a primitive root, and so $2^r$ covers all quadratic residues which means $-1$ is not a quadratic residue. Since $\left(\frac{2}{p}\right)=1$ and $\left(\frac{-1}{p}\right)=-1$ we have $p=7\pmod 8$.


