Order of the "children's card shuffle"

Question

Motivation. My eldest son thinks the following procedure is a "perfect shuffle" for a deck of cards: Take the first card, put the second on top of it, put the 3rd below cards 2 and 1, put the 4th on top of the growing stack, the 5th below, etc.

General formulation. Let $S_k$ be the group of permutations $\pi:\{1,\ldots,k\} \to \{1,\ldots,k\}$ for any positive integer $k$. The shuffle described above can be viewed as an element of $S_{2n}$ (we work with an even number of cards). We define the "perfect shuffle" permutation $\newcommand{\s}{\text{sh}}\s_n:\{1,\ldots,2n\}\to\{1,\ldots,2n\}$ by

• $1\mapsto n+1$,
• $2k\mapsto n+1-k$ for $k\in\{1,\ldots,n\}$, and
• $2k+1\mapsto n+1+k$ for $k\in \{1,\ldots,n-1\}$.

For instance, for $n=4$, the cards numbered $1,2,\ldots, 8$ get mixed to $8,6,4,2,1,3,5,7$. The order of $\text{sh}_4\in S_8$ is $4$. It turns out that the order of $\s_n$, denoted by $\text{ord}(\s_n)$ behaves quite interestingly. It appears that $\text{ord}(\s_{n}) \leq 2n$ for all $n$ (I haven't proved this), and for instance we get $\text{ord}(\s_7) = 14$ and $\text{ord}(\s_8) = 5$.

I am generally interested in the behaviour of $\text{ord}(\s_{n})$, but here is a concrete question.

We define the upper density $\mu^+(A)$ for $A\subseteq \mathbb{N}$ by $$\mu^+(A) = \lim\sup_{n\to\infty}\frac{\big|A\cap \{1,\ldots,n\}\big|}{n+1}.$$

Question. Let $M = \{n\in\mathbb{N}: \text{ord}(\s_n) = 2n\}$. What is $\mu^+(M)$?

Answer 1

The alternate characterization given in OEIS that Peter Taylor linked to in the comments may be used to answer this question.

This number is the least $m$ such that $2^m$ is congruent to $\pm 1$ modulo $\mathbb Z/(4n+1)$. In other words, it is the order of the element $2$ in the group $(\mathbb Z/4n+1)^\times/ (\pm 1)$. The order of the element divides the order of this group which is $\phi(4n+1) /2 \leq 2n$, with equality obtained only if $\phi(4n+1) = 4n$, i.e. only if $4n+1$ is prime.

So the order is at most $2n$ and equals $2n$ only for $n$ with $4n+1$ primes (but not for all such $n$), which is a set of upper density zero.