Number-theoretical considerations for your next card game
The deal
♠ 8 riffle shuffles
Here’s the deal: if you perfectly riffle shuffle a standard deck of 52 playing cards 8 times, it will return to its original order. After three or four shuffles, the cards appear hopelessly messed up, and then after a few more riffles, the original deck tumbles straight out of the chaos.
(Click here for a video of this being done).
There are of course some important caveats. These shuffles need to be perfect – after you’ve split the deck precisely in half, the two piles need to be recombined one card at a time, like you’re weaving the two books together page by page. In the vocabulary of cardistry, shuffles like these are called “faro shuffles”.
The other important condition is that when you recombine the cards from the two halves, the bottom card needs to be the first card you place down, otherwise you’ll need a full 52 shuffles to restore it to its original order. These are called “out” shuffles, and the alternative technique is called an “in” shuffle.
At least for me, demanding the “shuffles” be this precise definitely takes away a little bit of the mystery. Is calling this “shuffling” really suitable? In some ways, it would be more surprising if such a careful procedure really did lead to chaos. But being this precise means that we can ask lots of questions about what is going on:
- Why is the cycle exactly 8 shuffles long? There’s an eye-watering $52! \approx 8\times 10^{67}$ possible permutations of a standard deck of playing cards, why doesn’t it go through each one?
- Can you predict the number of shuffles to restore other-sized decks to their original order? What if there were 54 cards instead of 52?
- What happens if you shuffle a different number packs together? How many shuffles are needed for $3n$ or $4n$ cards?
- Why has everyone stopped playing cards with me?
These questions motivate a very interesting use of modular arithmetic and have a surprising connection with the expansions of fractions in base 2.
Mental division by 7 ♦
The fact 8 shuffles restore a deck to its original order is a kind of cycle. If you were to do 16 shuffles, you’d also end up at the same place.
One of the places that cycles first show up when learning mathematics in school is in the decimal expansions of fractions. Here’s all the fractions with 1 as their numerator, up to twelfths:
\[\begin{aligned} &1/2 = 0.5 \\ &1/3 = 0.\overline{333} \\ &1/4 = 0.25 \\ &1/5 = 0.2 \\ &1/6 = 0.1\overline{666} \\ &1/7 = 0.\overline{142857} \\ &1/8 = 0.125 \\ &1/9 = 0.\overline{111} \\ &1/10 = 0.1 \\ &1/11 = 0.\overline{0909} \\ &1/12 = 0.08\overline{333} \end{aligned}\](here, a vertical bar over a section of the number indicates that it repeats forever from that point). The ugliest-looking and most difficult to remember of these is definitely $1/7 = 0.\overline{142857}$. As you might expect, the situation isn’t any better for any of the other sevenths:
\[\begin{aligned} 1/7 = 0.\overline{142857} \\ 2/7 = 0.\overline{285714} \\ 3/7 = 0.\overline{428571} \\ 4/7 = 0.\overline{571428} \\ 5/7 = 0.\overline{714285} \\ 6/7 = 0.\overline{857142} \\ \end{aligned}\]If you look for a moment, you might be able to spot the structure here. It helps if you reorder from the numerators being $1,2,3,4,5,6$ to the numerators being $1,3,2,6,4,5$:
\[\begin{aligned} 1/7 = 0.\overline{142857} \\ 3/7 = 0.\overline{428571} \\ 2/7 = 0.\overline{285714} \\ 6/7 = 0.\overline{857142} \\ 4/7 = 0.\overline{571428} \\ 5/7 = 0.\overline{714285} \\ \end{aligned}\]Now it’s the same cycle every time, but successively shifted one decimal place. This observation forms the basis of a mental calculation trick called “magic sevenths”, which allows you to work out the decimal expansion of any division by seven, almost instantly. Here’s how you can do it:
First, memorise the “cycle list” $1,4,2,8,5,7$ and the “offset list” $1,3,2,6,4,5$. Suppose you need to calculate the decimal expansion for something like $65/7$. First you, reduce it from a “top heavy” fraction into a mixed fraction:
\[\frac{65}{7} = \frac{7\times 9 + 2}{7} = 9 + \frac 2 7\]In other words, find the quotient and remainder. In this case, the quotient is $9$, and the remainder is $2$.
Then the cycle and offset list give you a recipe for the expansion of $2/7$: $2$ is in the 3rd place of the offset list, so you begin the cycle three places along the cycle to obtain: $2,8,5,7,1,4$. This means that $2/7 = 0.285714$. Then to get the final result for $65/7$, you stick together the $9$ and $2/7$:
\[65/7 = 9.285714\]This is equivalent to a program like:
cycle = "142857"
offsets = "132645"
# The inputs
numerator = 65
denominator = 7
# Here "//" is integer division
quotient = numerator // denominator
remainder = numerator % denominator
start_pos = offsets.index(str(remainder))
# Modify the cycle to start at
new_cycle = cycle[start_pos:] + cycle[:start_pos]
print(remainder)
print(".")
while True:
print(new_cycle)
There are spades of questions you could ask about this:
- Why is the cycle six numbers long?
- What happens in fractions other than sevenths?
- What happens if instead of decimal you use some other base, like binary?
- Where do the offset list and cycle list come from?
It turns out that these questions are intimately related to the questions raised about perfect riffle shuffling.
♠ Shuffling and modular arithmetic
Let’s see if we can formalise what is going on in a perfect riffle shuffle. To simplify, rather than a full deck of 52 cards, it will help to consider just 8 cards. We’ll also forget about suits, and instead label all the cards from 0 to 7:
When you perform a riffle shuffle, you first split this into the top half and the bottom half:
And then recombine one card at a time (remembering to make sure the card originally at the bottom is still at the bottom):
Note that forcing the last card to stay the same also forces the top card to stay the same, but all of the cards in-between get mixed up – for example, the card labelled 4 ends up in the position originally held by the card labelled 1.
This table summarises what happens: card $k$ ends up in the position originally held by card $k’$.
Initial position ($k$) | New position ($k’$) |
---|---|
0 | 0 |
1 | 2 |
2 | 4 |
3 | 6 |
4 | 1 |
5 | 3 |
6 | 5 |
7 | 7 |
The general rule is this:
\[\text{card }k \mapsto \text{card } 2k \pmod{7}\]The positions for the top 4 cards are quite intuitive: every card in position $k$ will get sent to position $2k$ (and here, $0 \le k \le 3$). This is because card $k$ is exactly $k$ cards from the top of the deck (including card 0, which is 0 cards from the top). Once you weave in the bottom half of the pack, for every one of the cards initially between the card 0 and card $k$, there are now instead two cards.
For the bottom 4 cards, these fill in the slots. Every card in position $k$ (where now $4 \le k \le 7$) will be sent to position $2(k - 4) + 1$, or simplifying, position $2k - 7$.
This is because $(k - 4)$ counts the number of cards from the first card in that section. Multiplying it by two adds spaces for the cards in the top half, and adding $1$ means that these can nestle nice and securely in the spaces created by doubling the positions of the other cards.
So the formula is that card $k$ gets mapped to:
- Card $2k$, if $0 \le k \le 3$
- Card $2k - 7$, if $4 \le k \le 7$ (after simplifying)
But these are actually the same formula, modulo $7$! So we can write the rule more simply as:
\[\text{card }k \mapsto \text{card } 2k \pmod{7}\]This is supposing that there are just 8 cards, but it’s not too difficult to generalise: if there are 52 cards, the card $k$ in the top 26 cards get sent to card $2k$, and card $k$ in the bottom 26 will get sent to card $2(k - 26) + 1$, or equivalently $2k - 51$.
In general, if there are $N$ cards in a deck (where $N$ is even, otherwise the piles won’t be equal), the rule is:
\[\text{card }k \mapsto \text{card } 2k \pmod{N-1}\]Or, if you were writing a program to do this:
def post_shuffle_position(orig_pos, deck_size):
return 2*orig_pos % (deck_size - 1)
Division by other numbers and in other bases ♦
A few moments ago we were considering the “magic sevenths”:
\[\begin{aligned} 1/7 = 0.\overline{142857} \\ 3/7 = 0.\overline{428571} \\ 2/7 = 0.\overline{285714} \\ 6/7 = 0.\overline{857142} \\ 4/7 = 0.\overline{571428} \\ 5/7 = 0.\overline{714285} \\ \end{aligned}\]This raised the following questions:
- Why is the cycle six numbers long?
- What happens in fractions other than sevenths?
- What happens if instead of decimal you use some other base, like binary?
- Where do the offset list and cycle list come from?
The answer to the first question is not just that because 6 is one less than 7. This is evident looking at fractions with other denominators. For example, thirteenths have more complex behaviour:
\[\begin{aligned} &1/13 = 0.\overline{076923} \\ &2/13 = 0.\overline{153846} \\ &3/13 = 0.\overline{230769} \\ &4/13 = 0.\overline{307692} \\ &5/13 = 0.\overline{384615} \\ &6/13 = 0.\overline{461538} \\ &7/13 = 0.\overline{538461} \\ &8/13 = 0.\overline{615384} \\ &9/13 = 0.\overline{692307} \\ &10/13 = 0.\overline{769230} \\ &11/13 = 0.\overline{846153} \\ &12/13 = 0.\overline{923076} \end{aligned}\]Here there are in fact there are two cycles: one for fractions with numerator $1, 3, 4, 9, 10, 12$ and one for the others: $2, 5, 6, 7, 8, 11$. You could use this to come up with a “magic thirteenths” trick based on this for calculating divisions by thirteen exactly, and it would only be marginally more useless than the trick for sevenths.
But why do these cycles in the first place? Going back to sevenths, things are clearer if you probe the digits in the expansion by multiplying by 10 to shift the decimal point one place across:
\[10 \times 0.\overline{1427857} = 1.\overline{428571}\]Or, using fractions:
\[\begin{aligned} 10 \times \frac 1 7 &= \frac{10}{7} = 1 + \frac 3 7 \end{aligned}\]Equating the right hand sides of both of these equations says that:
\[1.\overline{428571} = 1 + \frac 3 7\]So after subtracting 1 from both sides, this explains why $3/7 = 0.\overline{428571}$. To verify that the cycle continues on, multiplying by 10 again shows that:
\[\begin{aligned} 10 \times 0.\overline{428571} &= 4.\overline{285714} \\ &= 10 \times \frac 3 7 \\ &= \frac{30}{7} \\ &= 4 + \frac 2 7 \end{aligned}\]and so similarly $2/7 = 0.\overline{428571}$. This process explains the numbers in the original “offset list”: $1, 3, 2, 6, 4, 5$.
The reason it repeats after 6 digits is that if you multiply $1/7$ by $10^6 = 1,000,000$ to shift the decimal place along 6 times, you get:
\[\begin{aligned} 10^6 \times 0.\overline{142857} &= 142,857.\overline{142857} \\ &= 10^6 \times \frac 1 7 \\ &= \frac{10^6}{7} \\ &= 142,857 + \frac 1 7 \end{aligned}\]Since $142,857.\overline{142857} = 142,857 + 1/7$, this cycle must repeat after six decimal digits.
Similarly, this also explains the two cycles of length 6 for thirteenths. Since the cycle also appears to be 6 digits long, multiplying again by $10^6$ shows:
\[\frac{1,000,000}{13} = 76,923 + \frac{1}{13}\]Furthermore, the other cycle starting with $2/13$ also repeats after 6 digits:
\[\frac{1,000,000 \times2}{13} = 153,846 + \frac{2}{13}\]You also need to be careful to check that the cycle doesn’t repeat after three digits, which can be checked by multiplying by $10^3$; this doesn’t lead you back to the fraction you started with.
You can explore fractions like this in other bases. Consider the binary expansion of $1/3$:
\[\frac 1 3_{10} = 0.\overline{01}_2\](here the subscripts indicate the base that should be used to interpret the expression). To shift the “binary point”, you multiply by two. So to shift two places, you multiply by $2^2$:
\[4_{10} \times \frac 1 3_{10} = 1_2 + 0.\overline{01}_2\]If you can spot the modular arithmetic lurking behind the scenes here, then maybe connection between repeating fractions and perfect riffle shuffling should be becoming clear. But first, the initial question: why exactly 8 riffle shuffles?
♠ Why exactly 8 riffle shuffles?
Previously it was justified that the general rule for $N$ cards is:
\[\text{card }k \mapsto \text{card } 2k \pmod{N-1}\]What about two shuffles in a row? Using the function from earlier, this could be written as:
post_shuffle_position(post_shuffle_position(k, N), N)
This will double $k$ twice, so for two perfect riffle shuffles:
\[\text{card }k \xmapsto[]{2 \text{ shuff.}} \text{card } 4k \pmod{N-1}\](repeatedly taking the modulus has no effect, we only need to take it once). For $s$ shuffles, the general rule is then that:
\[\text{card }k \xmapsto[]{s \text{ shuff.}} \text{card }2^s k \pmod {N -1}\]Determining the number of shuffles $s$ which will restore the original order is then equivalent to solving the following stack of equations:
\[\begin{aligned} &2^s \times 0 \equiv 0 \pmod {N-1} \\ &2^s \times 1 \equiv 1 \pmod {N-1} \\ &2^s \times 2 \equiv 2 \pmod {N-1} \\ &\quad\quad\vdots \\ \end{aligned}\]In other words, for which value of $s$ will $s$ shuffles send card 0 back to card 0, card 1 back to card 1, and so on?
If the “mod $N-1$” wasn’t there, then the only solution would be when $2^s = 1$, since multiplying by 1 wouldn’t affect any of the positions of the cards. Solving this gives the solution that $s = 0$, which is technically correct (shuffling $0$ times does keep the cards the same) but not what we’re looking for.
So the equation to solve becomes:
\[2^s \equiv 1 \pmod {N-1}, \quad s > 0\]This is it! For a deck of $N = 52$ cards, the smallest $s$ solving this equation is $8$:
\[2^8 \equiv 1 \pmod{51}\]So $8$ shuffles will restore the deck to the original order!
Why exactly does this fraction cycle like it does? ♦
For the final piece of the puzzle, let’s link this to the behaviour of cycling fractions in base 2. A moment ago, we saw that the reason that $1/3$ has a 2-bit cycling binary expansion is because:
\[4_{10} \times \frac 1 3_{10} = 1_2 + 0.\overline{01}_2\]In the general case, a fraction $1/m$ will cycle with period $s$ in binary if shifting the binary point $s$ places gives you a whole part $w$ plus the original fraction back:
\[2^s \times \frac 1 m = w + \frac 1 m\]This is equivalent to saying that dividing $2^s$ by $m$ has quotient $w$ and remainder $1$. For example in the case of $2^2/3$, has whole part $1$ and remainder $1$.
But the condition that “dividing $2^s$ by $m$ has quotient $w$ and remainder $1$” is exactly the following condition in modular arithmetic:
\[2^s \equiv 1 \pmod m\]Which is almost exactly the condition we had for perfect riffle shuffling! If $m = 51$, then the first non-zero $s$ for which the equation
\[2^s \equiv 1 \pmod{51}\]holds is $s = 8$ – this corresponds exactly with the fact that the binary expansion of $1/51$ repeats with period 8!
\[1/51 = 0.\overline{00000101}\]The twist
Snap! So the surprising connection is this:
Investigating the behaviour of perfectly riffle shuffling cards is precisely the same as investigating the behaviour of repeating fractions in base 2.
The fact that 8 perfect riffle shuffles are required to restore a deck of cards to its original order is because $2^8$ modulo 51 is 1, which is exactly the same reason that $1/51$ has a binary expansion with period $8$.
Is this correspondence practically useful? It’s your call. But I find it a very pretty number-theoretical sleight of hand: a surprising bridge between shuffling cards and calculating fractions in base 2.
Expert at the card table
Here’s a useless-but-fun consequence: pick your favourite odd number $3 \le N \le 51$. You can use the relationship above to “effortlessly” calculate all binary expansions of $k/N$ using just a deck of cards, where “effortless” means being mentally effortless but definitely requiring some physical effort.
For example, let’s suppose we want to simultaneously calculate the binary expansions of:
\[\frac{0}{13}, \frac{1}{13}, \frac{2}{13}, \cdots, \frac{11}{13}, \frac{12}{13}, \frac{13}{13}\]Get started by preparing a table with 14 entries:
Fraction | Expansion |
---|---|
$0/13$ | $0. _ 2$ |
$1/13$ | $0. _ 2$ |
$2/13$ | $0. _ 2$ |
$3/13$ | $0. _ 2$ |
$4/13$ | $0. _ 2$ |
$5/13$ | $0. _ 2$ |
$6/13$ | $0. _ 2$ |
$7/13$ | $0. _ 2$ |
$8/13$ | $0. _ 2$ |
$9/13$ | $0. _ 2$ |
$10/13$ | $0. _ 2$ |
$11/13$ | $0. _ 2$ |
$12/13$ | $0. _ 2$ |
$13/13$ | $0. _ 2$ |
(notice that $13/13$ also begins $0. _ 2$, the reason for this will become clear shortly). Also prepare a corresponding pile of 14 cards, and label these from 0 to 13:
Looking at the initial pile, for each of the cards in the first half, write a 0 in the expansion column. For each of the cards in the second half, write a 1:
Fraction | Expansion |
---|---|
$0/13$ | $0.0 _ 2$ |
$1/13$ | $0.0 _ 2$ |
$2/13$ | $0.0 _ 2$ |
$3/13$ | $0.0 _ 2$ |
$4/13$ | $0.0 _ 2$ |
$5/13$ | $0.0 _ 2$ |
$6/13$ | $0.0 _ 2$ |
$7/13$ | $0.1 _ 2$ |
$8/13$ | $0.1 _ 2$ |
$9/13$ | $0.1 _ 2$ |
$10/13$ | $0.1 _ 2$ |
$11/13$ | $0.1 _ 2$ |
$12/13$ | $0.1 _ 2$ |
$13/13$ | $0.1 _ 2$ |
Now riffle shuffle the cards (in the same way as before, one card at a time and making sure that the bottom card remains at the bottom). This will give a new arrangement of the cards:
Repeat the same process in the “expansion” column: for each of the cards now in the first half of this deck, write a $0$, and for each of the cards now in the second half, write a $1$.
Now if you repeat this process enough cards, you’ll eventually loop back around to the start, as predicted. This is what happens:
0 shuffles: | 0| 1| 2| 3| 4| 5| 6| * | 7| 8| 9|10|11|12|13|
1 shuffles: | 0| 2| 4| 6| 8|10|12| * | 1| 3| 5| 7| 9|11|13|
2 shuffles: | 0| 4| 8|12| 3| 7|11| * | 2| 6|10| 1| 5| 9|13|
3 shuffles: | 0| 8| 3|11| 6| 1| 9| * | 4|12| 7| 2|10| 5|13|
4 shuffles: | 0| 3| 6| 9|12| 2| 5| * | 8|11| 1| 4| 7|10|13|
5 shuffles: | 0| 6|12| 5|11| 4|10| * | 3| 9| 2| 8| 1| 7|13|
6 shuffles: | 0|12|11|10| 9| 8| 7| * | 6| 5| 4| 3| 2| 1|13|
7 shuffles: | 0|11| 9| 7| 5| 3| 1| * |12|10| 8| 6| 4| 2|13|
8 shuffles: | 0| 9| 5| 1|10| 6| 2| * |11| 7| 3|12| 8| 4|13|
9 shuffles: | 0| 5|10| 2| 7|12| 4| * | 9| 1| 6|11| 3| 8|13|
10 shuffles: | 0|10| 7| 4| 1|11| 8| * | 5| 2|12| 9| 6| 3|13|
11 shuffles: | 0| 7| 1| 8| 2| 9| 3| * |10| 4|11| 5|12| 6|13|
12 shuffles: | 0| 1| 2| 3| 4| 5| 6| * | 7| 8| 9|10|11|12|13|
(here *
is the midpoint of the pack). But doing so also simultaneously completely fills out the “expansion” column:
Fraction | Expansion |
---|---|
$0/13$ | $0.000000000000 _ 2$ |
$1/13$ | $0.000100111011 _ 2$ |
$2/13$ | $0.001001110110 _ 2$ |
$3/13$ | $0.001110110001 _ 2$ |
$4/13$ | $0.010011101100 _ 2$ |
$5/13$ | $0.011000100111 _ 2$ |
$6/13$ | $0.011101100010 _ 2$ |
$7/13$ | $0.100010011101 _ 2$ |
$8/13$ | $0.100111011000 _ 2$ |
$9/13$ | $0.101100010011 _ 2$ |
$10/13$ | $0.110001001110 _ 2$ |
$11/13$ | $0.110110001001 _ 2$ |
$12/13$ | $0.111011000100 _ 2$ |
$13/13$ | $0.111111111111 _ 2$ |
These are the first 12 digits of each of the binary expansions of the fractions. Even $13/13$ is right, this is the same as how $0.9999\ldots = 1$ in decimal. If you keep on going, you’ll see that these digits repeat with period 12 – and this fact is predicted by everything above, since $2^{12} \equiv 1 \pmod{13}$. You can check an example:
- $0$: $6/13$ is initially in the first half
- $1$: Then it is second half
- $1$: Then it’s in the second half again
- $1$: Then it’s in the second half again
- $0$: Then it’s back to the first half
- …and so on
This creates precisely the binary expansion of $6/13 = 0.011101100010 _ 2$. How fun!
References
- Came across this in [[The Book of Numbers, Conway]]N, specifically Chapter 6, “Further Fruitfulness of Fractions”.
- https://en.wikipedia.org/wiki/Faro_shuffle