Riffling Cards in Mathematica

Question

My friend posed this question to me; felt like sharing it here.

Given a deck of cards, we split it into 2 groups, and "interleave them"; let us call this operation a 'split-join'. And repeat the same operation on the resulting deck.

E.g., { 1, 2, 3, 4 } becomes { 1, 2 } & { 3, 4 } (split) and we get { 1, 3, 2, 4 } (join)

Also, if we have an odd number of cards i.e., { 1, 2, 3 } we can split it like { 1, 2 } & { 3 } (bigger-half first) leading to { 1, 3, 2 } (i.e., n is split up as Ceil[n/2] & n-Ceil[n/2])

The question my friend asked me was:

HOW many such split-joins are needed to get the original deck back?

And that got me wondering:

If the deck has n cards, what is the number of split-joins needed if:

• n is even ?
• n is odd ?
• n is a power of '2' ? [I found that we then need log (n) (base 2) number of split-joins...]
• (Feel free to explore different scenarios like that.)

Is there a simple pattern/formula/concept correlating n and the number of split-joins required?

I believe, this is a good thing to explore in Mathematica, especially, since it provides the Riffle[] method.

Answer 1

To quote MathWorld:

The numbers of out-shuffles needed to return a deck of n=2, 4, ... to its original order are 1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, ... (Sloane's A002326), which is simply the multiplicative order of 2 (mod n-1). For example, a deck of 52 cards therefore is returned to its original state after eight out-shuffles, since 2**8=1 (mod 51) (Golomb 1961). The smallest numbers of cards 2n that require 1, 2, 3, ... out-shuffles to return to the deck's original state are 1, 2, 4, 3, 16, 5, 64, 9, 37, 6, ... (Sloane's A114894).

The case when n is odd isn't addressed.

Note that the article also includes a Mathematica notebook with functions to explore out-shuffles.