Discrete

Eight perfect shuffles bring the deck home

Cut a deck of 52 cards exactly in half and interleave the halves perfectly, keeping the top card on top. Do it eight times and the deck is back in its original order. The reason is that the shuffle sends the card in position i to position 2i modulo 51, and 2 multiplied by itself eight times is 256, one more than five times 51. Keep the top card second instead and it takes fifty-two shuffles; twenty-six of them turn the deck upside down; and a magician can send the top card to any position by reading the position in binary.

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

Eight perfect shuffles bring 52 cards home. N=52: cycles 8,8,8,8,8,2,8; order 8
Fig. 1 The out-shuffle of 52 cards on a dial of 51 positions. Every position is joined to the one its card moves to; the cycles have length 8 except for a single swap, so eight shuffles bring every card home.

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 ii in the top half moves to position 2i2i, and the card that was at position 26+j26 + j in the bottom half moves to position 2j+12j + 1.

Both rules are one rule modulo 51. For the top half, 2i2i is already less than 51. For the bottom half, 2(26+j)=52+2j≡2j+1(mod51)2(26 + j) = 52 + 2j \equiv 2j + 1 \pmod{51}. So every card except the bottom one moves from position ii to position 2i mod 512i \bmod 51, and the bottom card, at 51, stays at the bottom. The top card, at 0, also stays where it is, since 2⋅0=02 \cdot 0 = 0. 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 64≡1364 \equiv 13, then 26, then 52≡152 \equiv 1, home after eight steps. The cycles of the dial are the orbits of cards.

Eight shuffles restore position 1 because 28=256=5⋅51+12^8 = 256 = 5 \cdot 51 + 1, so 28≡1(mod51)2^8 \equiv 1 \pmod{51}, and no smaller power of 2 is 1 modulo 51. The same fact restores every position at once, since multiplying any ii by 282^8 gives ii 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 2⋅17=342 \cdot 17 = 34 and 2⋅34=68≡172 \cdot 34 = 68 \equiv 17. 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 51=3⋅1751 = 3 \cdot 17, 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

How many perfect shuffles restore a deck. 4:2/4 12:10/12 20:18/6 28:18/28 36:12/36 44:14/12 52:8/52 60:58/60 64:6/12 68:66/22 76:20/30 84:82/8 92:12/10 100:30/100
Fig. 2 The number of out-shuffles and in-shuffles that restore a deck of N cards, for every even N from 4 to 104. Out-shuffles need the order of 2 modulo N − 1, in-shuffles the order modulo N + 1.

Nothing in the argument used 52. For a deck of NN cards, with NN even, an out-shuffle multiplies positions by 2 modulo N−1N - 1, and the number of out-shuffles that restore the deck is the order of 2 modulo N−1N - 1. 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 26=64≡1(mod63)2^6 = 64 \equiv 1 \pmod{63}: 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 i↦2i+1(modN+1)i \mapsto 2i + 1 \pmod{N + 1}, which becomes plain multiplication by 2 if positions are counted from 1 instead of 0: position p=i+1p = i + 1 goes to 2p2p modulo N+1N + 1. So in-shuffles restore a deck after the order of 2 modulo N+1N + 1, 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 pp gives a deck of p−1p - 1 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

A deck through eight out-shuffles. 0: 0,1,2,3,4,5,6,7; 1: 0,26,1,27,2,28,3,29; 2: 0,13,26,39,1,14,27,40; 3: 0,32,13,45,26,7,39,20; 4: 0,16,32,48,13,29,45,10; 5: 0,8,16,24,32,40,48,5; 6: 0,4,8,12,16,20,24,28; 7: 0,2,4,6,8,10,12,14; 8: 0,1,2,3,4,5,6,7
Fig. 3 A deck in order, by suit and rank, and after each of eight out-shuffles. The fourth leaves every block of four holding one card of each suit; the eighth restores the deck.

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 27=128≡26(mod51)2^7 = 128 \equiv 26 \pmod{51}, which is the inverse of 2 modulo 51 because 2⋅26=52≡12 \cdot 26 = 52 \equiv 1; 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

Sending the top card anywhere with binary. target 13 = 1101: 0 -> 1 -> 3 -> 6 -> 13
Fig. 4 Alex Elmsley’s rule: to move the top card to position p, write p in binary and do an in-shuffle for each 1 and an out-shuffle for each 0. For p=13p = 13, which is 1101 in binary, the card goes to 1, 3, 6 and 13.

The two shuffles together do more than either alone. An out-shuffle sends the card at position ii to 2i2i and an in-shuffle sends it to 2i+12i + 1 (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 pp, write pp in binary and read it from the left, doing an in-shuffle for each 1 and an out-shuffle for each 0. For p=13p = 13, which is 1101 in binary, the shuffles are in, in, out, in, and the card moves to 1, then 2⋅1+1=32 \cdot 1 + 1 = 3, then 2⋅3=62 \cdot 3 = 6, then 2⋅6+1=132 \cdot 6 + 1 = 13. 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

Which decks perfect shuffles turn upside down. 4:2/4 6:-/3 8:3/6 10:5/10 12:6/12 14:-/4 16:4/8 18:9/18 20:-/6 22:-/11 24:10/20 26:9/18 28:14/28 30:-/5 32:5/10 34:-/12 36:18/36 38:-/12 40:10/20 42:7/14 44:-/12 46:-/23 48:-/21 50:-/8 52:26/52
Fig. 5 For each even deck up to 52, the number of in-shuffles that turn it exactly upside down, when any number does, beside the number that restore it. Reversal comes halfway to restoration; 26 in-shuffles reverse 52 cards.

A reversed deck has the card from position ii at position N−1−iN - 1 - i. Under in-shuffles, counting positions from 1, reversal sends pp to N+1−p≡−p(modN+1)N + 1 - p \equiv -p \pmod{N + 1}. So kk in-shuffles reverse the deck exactly when 2k≡−1(modN+1)2^k \equiv -1 \pmod{N + 1}. For 52 cards that asks for a power of 2 equal to −1-1 modulo 53, and since the powers of 2 run through every nonzero remainder modulo 53 with period 52, the power halfway round, 2262^{26}, is −1-1. 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 N+1N + 1 is even and the halfway power is −1-1, 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 N/2N/2 mirror pairs of positions among themselves, possibly flipping a pair, and the group is at most 2N/2⋅(N/2)!2^{N/2} \cdot (N/2)!. 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 mm divides the number of residues prime to mm, 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 N+1N + 1 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.

Named objects

A dashed tag is an object no other essay names yet.

Binary expansionCycleModular arithmeticMultiplicative orderOrder of an elementPermutationPrimitive root