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{|A\cap \{1,\ldots,n\}|}{n+1}$.

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