# Order of the "children's card shuffle"

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)$$?

• oeis.org/A019567 May 15 at 7:32
• That answers question 2, because we have $2^{\operatorname{ord}(\text{sh}_n)} + 1 \ge 4n + 1$, so $\operatorname{ord}(\text{sh}_n) \ge 2 + \lg n$. May 15 at 7:40
• Thanks @PeterTaylor, will remove question 2 May 15 at 8:21
• Congratulations to your son's rediscovery of a shuffle that Monge wrote a paper about in 1773 according to p 107 in W.W. Rouse Ball's book May 15 at 9:31
• Thanks @ChrisWuthrich -- my son just found an inconsistency in ${\sf (ZF)}$ and will publish it before going back to afternoon school May 15 at 13:04

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.