Minimum number of out-shuffles required to get back to the start in a pack of $2n$ cards?

Question

So I'm stuck on this problem. If you perform a faro out-shuffle (i.e. a perfect "riffle shuffle" where the top and bottom cards stays in place) on a pack of 52 cards ($n=26$), you can get back the original order in 8 shuffles. Call $8$ the order for $n=26$. That's easily seen if you write the permutation in cycle notation. I checked the order for $n=1$ all the way to $n=26$. I looked for some pattern, but I found none. So my question is, is there a general formula to determine order for any arbitrary $n$? I'd be much obliged if someone could point me in the right direction. Thanks.

Answer 1

As Arthur noted in the comments below, the out-shuffle is identical to an in-shuffle on two fewer cards. Since the first and last cards are fixed, I will simply rename the deck to exclude those cards and focus on in-shuffling instead. To be perfectly clear, my $1$ is really the second card and so forth.

The in-shuffle on $2n$ cards (which is an out-shuffling on $2n+2$ cards) can be represented as a permutation $\pi \in S_{2n}$ in two-line notation as follows:

$$\pi = \begin{pmatrix} 1 & 2 & 3 & \cdots & n && n+1 && n+2 && n+3 && \cdots &&2n\\ 2 & 4 & 6 & \cdots & 2n && 1 && 3 && 5 && \cdots && 2n-1\end{pmatrix}$$

The first thing you want to do is confirm to yourself that $\pi(x) \equiv 2x \pmod{2n+1}$ for any $x \in \{1, 2, ..., 2n\}$.

From here, imagine you rewrite the two-line notation into disjoint cycle notation. Denote $m$ as the length of the cycle to which $1$ belongs. Can you show that $m$ is also the order of $2$ in the multiplicative group $\mathbb{Z}_{2n+1}^\times$? You don't need anything fancy to show this -- simply consider the previous paragraph.

Next, you'll want to show that, for any arbitrary $x \in \{1, 2, ..., 2n\}$, the length of the cycle to which $x$ belongs divides $m$. Again, there's nothing too difficult going on here. To get you started, we know that $\pi(x) \equiv 2x$, then $\pi(2x) \equiv 2\cdot 2x \equiv 4x$, then $\pi(4x) \equiv 2 \cdot 4x \equiv 8x$, and so forth working $\pmod{2n+1}$. How many times must we continue until we're guaranteed to wrap around to $x$? What can we conclude?

From here, we can simply apply the fact that the order of a composition of disjoint cycles is the least common multiple of their respective lengths. Since all cycle lengths divide $m$, then the order of the entire permutation $\pi$ is $m$. That is, the number of in-shuffles required to return a deck of $2n$ cards to its original position is equal to the order of $2$ in the multiplicative group $\mathbb{Z}_{2n+1}^\times$. As discussed in the first paragraph, this will be equal to the number of out-shuffles required to return a deck of $2n+2$ cards to their original position.

Unfortunately, no known closed-form exists for finding this value. Solving $2^x = 1 \pmod{2n+1}$ is a discrete log problem for which polynomial-time algorithms have not been discovered (though one can apply brute-force or any of a few slight improvements on brute-forcing).