Eight perfect shuffles bring the deck home
Worth reading first: Numbers that wrap · Multiplying every number on the dial at once.
A card magician’s perfect shuffle is a feat of dexterity: the deck is cut into two halves of exactly 26 cards, and the halves are pushed together so that the cards interleave one by one, alternating perfectly from top to bottom. It is called a faro shuffle, after the card game whose dealers practised it, and a skilled performer can do it reliably. The remarkable thing about it is that it is not random at all. A perfect shuffle is a fixed rearrangement of the deck, and doing it repeatedly cycles the deck through a fixed sequence of orders. Eight perfect shuffles of a 52-card deck, with the top card kept on top each time, return every card to its starting position.
This essay explains why eight, and why the answer is really a fact about the number 51. It is the same arithmetic that numbers that wrap introduced — a dial of finitely many positions, with multiplication going round it — applied to a deck of cards.
The shuffle is multiplication by two
Number the positions in the deck from 0 at the top to 51 at the bottom. After the cut, the top half holds positions 0 to 25 and the bottom half 26 to 51. An out-shuffle interleaves them with the top half’s card first: positions 0, 1, 2, … of the new deck hold the old cards 0, 26, 1, 27, 2, 28, and so on. So the card that was at position in the top half moves to position , and the card that was at position in the bottom half moves to position .
Both rules are one rule modulo 51. For the top half, is already less than 51. For the bottom half, . So every card except the bottom one moves from position to position , and the bottom card, at 51, stays at the bottom. The top card, at 0, also stays where it is, since . An out-shuffle is multiplication by 2 on a dial of 51 positions, with the two ends of the deck fixed.
Multiplying every number on the dial at once drew exactly this picture for other dials: join each residue to twice itself, and the chords trace a heart-shaped curve. The hero draws it for the dial of 51, but now the chords are the paths of cards. Follow a card through repeated shuffles and it walks around a cycle: the card at position 1 goes to 2, then 4, 8, 16, 32, then , then 26, then , home after eight steps. The cycles of the dial are the orbits of cards.
Eight shuffles restore position 1 because , so , and no smaller power of 2 is 1 modulo 51. The same fact restores every position at once, since multiplying any by gives back. Eight is the multiplicative order of 2 modulo 51. The hero’s legend lists the cycles: six of length 8, and one of length 2, the pair 17 and 34, which simply swap at each shuffle because and . Those two cards return after two shuffles, and all the others after eight, so the whole deck returns after eight.
The pair 17 and 34 is no accident either. Since , the positions that are multiples of 17 form a smaller dial of their own — multiplication by 2 cannot leave them — and on that dial of three the order of 2 is 2. Two dials at once explained how a dial of 51 splits into a dial of 3 and a dial of 17 by the Chinese remainder theorem, and the order of 2 modulo 51 is the least common multiple of its orders modulo 3 and 17, which are 2 and 8.
Every deck size, by its order
Nothing in the argument used 52. For a deck of cards, with even, an out-shuffle multiplies positions by 2 modulo , and the number of out-shuffles that restore the deck is the order of 2 modulo . The figure plots it for every even deck up to 104 cards, and the result is erratic, because orders are erratic. A deck of 50 cards needs 21 out-shuffles, a deck of 52 needs 8, and a deck of 54 needs 52. A deck of 64 needs only 6, since : when the deck size is a power of two, the out-shuffle is its base-two logarithm in steps. The figure’s checks shuffle every deck up to 60 cards until it comes home and confirm the count against the order.
The other perfect shuffle, the in-shuffle, puts the bottom half’s card first, so the top card goes to position 1. Its rule is , which becomes plain multiplication by 2 if positions are counted from 1 instead of 0: position goes to modulo . So in-shuffles restore a deck after the order of 2 modulo , and for 52 cards that is the order of 2 modulo 53. Since 53 is prime, the order divides 52, and it turns out to be 52 itself: 2 generates every nonzero remainder modulo 53. Fifty-two in-shuffles are needed to bring a 52-card deck home, against eight out-shuffles — a difference made entirely by whether the top card goes first or second.
Whether 2 generates every remainder modulo a prime is a question with a long history. How often two generates every remainder measured it: among primes, 2 is a primitive root about 37.4% of the time, as Artin conjectured, and whether it is a primitive root for infinitely many primes is still unproved. Every such prime gives a deck of cards that needs as many in-shuffles as it has cards, and those are exactly the points where the figure’s blue in-shuffle dots touch the dashed line. So the question whether there are infinitely many decks that need the maximum number of perfect in-shuffles is a disguised form of Artin’s conjecture for the base 2, which nobody has proved.
What the deck looks like in between
The deck does not merely return; it passes through recognisable states on the way. After one out-shuffle the first suit is interleaved with the third and the second with the fourth. After two, the deck reads first card of each suit, second card of each suit, and so on for the first half — the positions are multiplied by 4 modulo 51, and the cards 0, 13, 26 and 39 that start each suit now sit together at the top.
After four shuffles the positions are multiplied by 16, and the figure shows a striking regularity: every block of four consecutive cards, counted from the top, contains exactly one card of each suit. The suits within a block rotate — the first block runs through the suits in their original order, the next starts one suit later — so the deck looks thoroughly mixed while every four consecutive cards are guaranteed to be one of each. That is the kind of hidden structure magicians exploit: a deck that looks shuffled, but which has been shuffled perfectly a known number of times, deals out in a controlled way.
The later states mirror the early ones. After seven shuffles the positions are multiplied by , which is the inverse of 2 modulo 51 because ; the seventh state is what one inverse shuffle would produce, so the deck after seven shuffles reads 0, 2, 4, 6, … down its first half. The eighth state is the identity. The whole sequence is the powers of 2 modulo 51, each one a permutation of the deck, and the states repeat with period eight forever.
Sending the top card anywhere
The two shuffles together do more than either alone. An out-shuffle sends the card at position to and an in-shuffle sends it to (as long as it is in the top half, which a card starting from the top stays in during this process). So starting from the top, position 0, a sequence of shuffles builds up the card’s position one binary digit at a time: an out-shuffle appends a 0 to the binary expansion, an in-shuffle appends a 1.
That is Alex Elmsley’s rule, published in the 1950s and still a staple of card magic: to move the top card to position , write in binary and read it from the left, doing an in-shuffle for each 1 and an out-shuffle for each 0. For , which is 1101 in binary, the shuffles are in, in, out, in, and the card moves to 1, then , then , then . The figure’s checks run the rule for all 51 possible targets and confirm it each time. It uses at most six shuffles, since every position up to 51 has at most six binary digits.
The rule rests on one identification: perfect shuffles act on positions the way doubling acts on binary expansions, an out-shuffle appending a 0 and an in-shuffle a 1. The last place in the circle found the same arithmetic in the Josephus problem, where with every second person removed the survivor’s place is found by moving the leading binary digit of the number of people to the end — doubling on a circle of people rather than a deck of cards.
Turning the deck upside down
A reversed deck has the card from position at position . Under in-shuffles, counting positions from 1, reversal sends to . So in-shuffles reverse the deck exactly when . For 52 cards that asks for a power of 2 equal to modulo 53, and since the powers of 2 run through every nonzero remainder modulo 53 with period 52, the power halfway round, , is . Twenty-six in-shuffles turn a 52-card deck upside down, and twenty-six more turn it back.
The figure tabulates every even deck up to 52. When the order of 2 modulo is even and the halfway power is , the deck can be reversed, at exactly half the restoring count; when it is not, no number of in-shuffles ever reverses it — for 6, 14, 20 and 22 cards, among others. And no number of out-shuffles ever reverses any deck at all, for a reason that needs no arithmetic: an out-shuffle never moves the top card, and a reversed deck needs the top card at the bottom. The figure’s checks confirm both statements by shuffling every deck until it returns.
Reversal halfway is the structure of a cyclic group made visible. The in-shuffles of a 52-card deck generate a cyclic group of 52 rearrangements, which is the group of powers of 2 modulo 53; the reversal is the unique element of order 2 in it, and a cyclic group of even order has exactly one such element, sitting at the halfway point.
The group two shuffles generate
Elmsley’s rule uses the two shuffles together, and it is natural to ask which rearrangements of the deck the two can produce between them. Every product of in-shuffles and out-shuffles is a rearrangement, and together they form a group — the shuffle group of the deck. Two random shuffles reach every shuffle found that two rearrangements chosen at random almost always generate every possible order of the deck. The two perfect shuffles are not random, and they generate very little.
The first reason is a symmetry they share. Both shuffles keep mirror positions mirrored: two cards equally far from the top and from the bottom of the deck are still equally far from the top and the bottom after either shuffle. So the shuffles can only permute the mirror pairs of positions among themselves, possibly flipping a pair, and the group is at most . A breadth-first search over everything the two shuffles reach measures how much of that they fill. For 4 cards they fill all 8 rearrangements; for 10 cards half of the 3,840; for 14 cards half of the 645,120. But for decks whose size is a power of two the group collapses: 24 rearrangements for 8 cards and just 64 for 16, because doubling on a power-of-two dial only shifts binary digits around, and the reachable orders are rotations of the digits combined with flips.
The deck of 12 cards is the strangest. The two shuffles reach 7,680 rearrangements, and the search shows how: they permute the six mirror pairs in exactly 120 ways, and for any three pairs and any three destinations exactly one of the 120 sends the first to the second in order. That is the sharply three-transitive group on six points that is a copy of the permutations of five things — the same group that every position of the pocket cube found arranging the six corners that two faces of the cube can reach. A deck of twelve cards and a two-by-two cube turned on two faces share an unexpected symmetry group, because both happen to generate the projective line over the field of five elements acting on its six points.
Persi Diaconis, Ronald Graham and William Kantor determined the shuffle group for every deck size in 1983. Outside the powers of two and a few exceptional sizes, including 12 and 24, the group is as large as the mirror symmetry allows or a small fixed fraction of it. For 52 cards it is large, and the out-shuffles alone, of order eight, are a tiny cyclic subgroup inside it.
What the dial cannot show
The dial picture explains perfect shuffles completely and says nothing about real ones. A riffle shuffle by an ordinary person cuts the deck roughly in half and drops cards from the two halves in clumps of random sizes, and the result is a random rearrangement. How long until it forgets measured how quickly such shuffles mix a deck: about seven are needed before the deck is close to random, and the perfect shuffles of this essay are the opposite extreme — never random, however often they are repeated. A deck that has had eight perfect out-shuffles is not well mixed; it is in exactly the order it started.
The dial also hides the difficulty of the physical act. A faro shuffle that slips by one card — two cards from the same half falling together — is no longer multiplication by two, and the arithmetic of this essay stops applying from that moment. Magicians who use the effects described here practise for years to make the interleaving exact, and the mathematics is only as reliable as their hands.
Nor does the picture predict the orders. Knowing that 52 cards need eight out-shuffles requires computing the order of 2 modulo 51, and there is no shortcut known for computing multiplicative orders in general beyond factoring: the order of 2 modulo divides the number of residues prime to , and finding which divisor needs that number’s prime factors. For a deck of a few dozen cards this is instant, and for a deck the size of a large prime it is as hard as the hardest arithmetic questions used in cryptography.
Still open: which decks need every shuffle
Which deck sizes need the maximum possible number of in-shuffles — as many as there are cards? Exactly those where is a prime for which 2 is a primitive root, as the orders figure shows. Whether there are infinitely many such primes is Artin’s conjecture for the base 2, proved by Christopher Hooley in 1967 under the generalised Riemann hypothesis and open without it. The perfect shuffle turns this into a question about cards: are there infinitely many deck sizes for which a perfect in-shuffle, repeated, passes through every possible arrangement of positions that doubling can reach before returning home? Nobody knows. A number that is its own square found an endless pattern hiding in the digits of 625 and 9376; the pattern behind the shuffle counts is a pattern among the primes, and it has resisted proof for a century.
Shares its objects with
Essays that name at least two of the same things, and that neither author linked.
- A hundred prisoners and one shuffle — both name cycle, permutation
- A perfect coin and a biased shuffle — both name cycle, permutation
- A ring that no pairing can break — both name cycle, permutation
- An order that proves a prime — both name order of an element, primitive root
- Dots that never repeat a step — both name permutation, primitive root
- Every function is a tree with two marks — both name cycle, permutation
Named objects
A dashed tag is an object no other essay names yet.
Binary expansionCycleModular arithmeticMultiplicative orderOrder of an elementPermutationPrimitive root