How many time do we need to shuffle two decks red and blue to get back to initial colors?

Question

Question

Let's say:

• I have two decks of $n$ cards each (a blue and a red decks), I am not interested in card faces, just in colors of card backs;
• Each time I shuffle perfectly ($n$ cards in each hand, 1 card from right, 1 card from left, and so on);
• Then I split the $2n$ cards deck into two $n$ decks and I reshuffle again.

How many time do I have to shuffle the deck in order to get the two single colored decks again?

For $n=5$, it takes 6 shuffles:

Left hand                                  Right hand
['B', 'B', 'B', 'B', 'B',    'R', 'R', 'R', 'R', 'R']
['B', 'R', 'B', 'R', 'B',    'R', 'B', 'R', 'B', 'R']
['B', 'R', 'R', 'B', 'B',    'R', 'R', 'B', 'B', 'R']
['B', 'R', 'R', 'R', 'R',    'B', 'B', 'B', 'B', 'R']
['B', 'B', 'R', 'B', 'R',    'B', 'R', 'B', 'R', 'R']
['B', 'B', 'B', 'R', 'R',    'B', 'B', 'R', 'R', 'R']
['B', 'B', 'B', 'B', 'B',    'R', 'R', 'R', 'R', 'R']

Context

Not related, but fun fact: this question arose with my daughter when we did shuffled two bicycles decks when we learned to play to Eleusis last week.

To answer it, we tried experimentally for small decks of sizes ($n<10$) and it looks not so simple as we tough. On the same time we had the feeling that for some specific values the number of shuffle simply is the number of cards minus 1 (4, 9, 12, 21, 24, 36, 40, 49, 52).

Doing some representations by hand I also have the feeling that solving this problem is somehow related to combinatorics, permutations and binary strings. But I lack some insights to formalize it thus I resorted to numerical modeling.

Numerical results

Then I modeled the process with the following Python program:

class Shuffler:
    
    @staticmethod
    def new(n):
        return np.array(["B"]*n + ["R"]*n)
    
    @staticmethod
    def shuffle(x):
        return x.reshape((2, -1)).T.reshape((2, -1)).flatten()
    
    @staticmethod
    def identity(n):
        return np.arange(2*n) + 1
    
    @staticmethod
    def permutation(n):
        return Shuffler.shuffle(Shuffler.identity(2*n))
    
    @staticmethod
    def generate(x=None, n=1):
        
        if x is None:
            x = Shuffler.new(n)
        else:
            n = x.size // 2
        assert x.size == 2*n
            
        x0 = x.copy()
        yield x0
        
        while True:
            x = Shuffler.shuffle(x)
            yield x
            
            if np.all(x == x0):
                break
    
    @staticmethod
    def length(x):
        n = 0
        for x in Shuffler.generate(x):
            n += 1
        return n - 1
    
    @staticmethod
    def screen(n):
        t = np.arange(n) + 1
        c = np.full(t.shape, 0)
        for i, m in enumerate(t):
            x = Shuffler.new(m)
            c[i] = Shuffler.length(x)
        return t, c

The result for the first thousand deck sizes looks like:

First 100 values are:

     1,   2,   4,   3,   6,  10,  12,   4,   8,  18,   6,  11,  20,
    18,  28,   5,  10,  12,  36,  12,  20,  14,  12,  23,  21,   8,
    52,  20,  18,  58,  60,   6,  12,  66,  22,  35,   9,  20,  30,
    39,  54,  82,   8,  28,  11,  12,  10,  36,  48,  30, 100,  51,
    12, 106,  36,  36,  28,  44,  12,  24, 110,  20, 100,   7,  14,
   130,  18,  36,  68, 138,  46,  60,  28,  42, 148,  15,  24,  20,
    52,  52,  33, 162,  20,  83, 156,  18, 172,  60,  58, 178, 180,
    60,  36,  40,  18,  95,  96,  12, 196,  99, ...

The first 73 of this series exactly match the series A002326 in OEIS: Multiplicative order of 2 mod 2n+1.

t, c = Shuffler.screen(100)
# From https://oeis.org/A002326/list
check = np.array([
    1, 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 28, 5, 10,
    12, 36, 12, 20, 14, 12, 23, 21, 8, 52, 20, 18, 58, 60, 6,
    12, 66, 22, 35, 9, 20, 30, 39, 54, 82, 8, 28, 11, 12, 10, 36,
    48, 30, 100, 51, 12, 106, 36, 36, 28, 44, 12, 24, 110, 20, 100,
    7, 14, 130, 18, 36, 68, 138, 46, 60, 28
])
np.all(c[0:check.size] == check)  # True

It's tenting to think from it that there is always a finite number of shuffles that reset the two decks:

• The process seems not get trapped in a cycle (infinite number of shuffles);
• The number of shuffles seems to be bounded by some dominating function (looking like a line of slope 2);
• When testing for coincidence, resetting colors seems to always happen when the card orders also reset, maybe resetting the colors is always achieved by resetting the initial setup.

So here I am, kindly asking the community a bit of help to get more grasp on this question:

• Can we express the number of shuffles in term of deck size?
• Or is it something more like the Collatz Conjecture.

Answer 1

Not a complete answer. The relationship to A002326 is the following. Think of the blue vs. red cards as the odd vs. the even numbers from $1$ to $2n$. We begin with the odd numbers $1, 3, 5, 7, \dots$ in one hand in that order and $2, 4, 6, 8, \dots$ in the other hand in that order. After one shuffle, we have the numbers $1, 2, 3, 4, \dots$ in one hand in that order, and the numbers $n+1, n+2, \dots 2n$ in the other hand in that order. Note in particular that $1$ and $2n$ don't move.

This operation can be interpreted using modular arithmetic: it is exactly $x \mapsto \frac{x+1}{2} \bmod (2n-1)$, where we take the remainder in $\{ 1, 2, \dots 2n-1 \}$. It's not hard to see this for the odd numbers; for the even numbers we have $\frac{x+1}{2} \equiv \frac{x + 2n}{2} \equiv \frac{x}{2} + n \bmod (2n-1)$. (Note that $2n \equiv 1 \bmod (2n-1)$ is fixed by this transformation so it doesn't move anywhere anyway and we can ignore it.)

So now we want to understand the order of this map; that is, we want to know how long we have to iterate it until we get back the identity (actually we don't quite want this but I'll get back to this later). It turns out to have the same order as the operation $x \mapsto 2x$; this is because we can rewrite it as $x \mapsto \frac{x-1}{2} + 1$, which tells us that it's doing the same operation as division by $2$ ($\bmod 2n-1$), except centered at $x = 1$ instead of at $x = 0$. And division and multiplication by $2$ have the same order.

This tells us that your sequence divides A002326 which is the exact order of $2 \bmod (2n-1)$. It may be strictly smaller because you are only asking to get the colors back, not the exact numbers. However, looking at A002326 all of the terms you give (if I'm not mistaken) agree. What that suggests is that the first time we get the colors back, we in fact get the exact numbers back. This happens when $n = 5$ if you use the number labels instead of just the color labels to do the calculation. Since you say the two sequences eventually disagree I guess it doesn't happen forever, but I don't see how to either prove or disprove this at the moment.

So, let me just tell you some more stuff about A002326 instead. It can be written $\text{ord}_{2n-1}(2)$. The order of a number $\bmod (2n-1)$ always divides the Carmichael function $\lambda(2n-1)$ (A002322), which has a somewhat complicated definition but is easy to compute given the prime factorization of $2n-1$; this sequence begins (with disagreements with the given sequence highlighted)

$$1, 2, 4, \color{red}{6}, 6, 10, 12, \color{red}{8}, \color{red}{16}, 18, \dots .$$

The Carmichael function in turn always divides the totient function $\varphi(2n-1)$ (A000010) which is more well-known but gives a worse bound on $\text{ord}_{2n-1}(2)$.

The simplest values of the Carmichael function occur on the primes, where if $2n-1 = p$ is prime then $\lambda(p) = p-1$. If a prime $p$ satisfies $\text{ord}_p(2) = p - 1$ then $2$ is called a primitive root $\bmod p$; this sequence of primes is A001122 and corresponds to values of $n$ such that $\text{ord}_{2n-1}(2) = 2n-2$ is as large as possible. Famously, it's not known if there are infinitely many such primes (although it is widely expected); this is a special case of Artin's conjecture. This is related to one of your observations:

On the same time we had the feeling that for some specific values the number of shuffle simply is the number of cards minus 1 (4, 9, 12, 21, 24, 36, 40, 49, 52).

Note that all of these values of $n$ have the property that $2n-1$ is prime. This is explained by our comments above: $\text{ord}_{2n-1}(2)$ always divides $\lambda(2n-1)$, and if $2n-1$ is prime then $\lambda(2n-1) = 2n-2$ so $n-1$ can divide it, which means it is a possible value of $\text{ord}_{2n-1}(2)$. If $p$ is prime and $\text{ord}_p(2) = \frac{p-1}{2}$ then $2$ is a quadratic residue $\bmod p$ (but this necessary condition is not sufficient). By one of the supplements to quadratic reciprocity this implies that $p \equiv 1, 7 \bmod 8$, so $n \equiv \frac{p+1}{2} \equiv 0, 1 \bmod 4$ which we see in your sequence.

The sequence of primes $p$ satisfying $\text{ord}_p(2) = \frac{p-1}{2}$ is A115591. I don't know that I've ever seen it stated anywhere but it's likely also an open problem whether there are infinitely many such primes; this should be about as hard as Artin's conjecture.

This is not the only way we could have $\text{ord}_{2n-1}(2) = n-1$; it could also be the case that $\lambda(2n-1) = n-1$. I don't know when if ever this happens, though. $2n-1$ would have to be a Fermat pseudoprime to base $2$. This sequence is A001567.

So as you can see this question leads pretty directly to some open problems in number theory!