How long does it take for shuffled poker chips to return to their original state?

I like to shuffle poker chips while I work. It gives me something to do while pages are loading or while I'm thinking that doesn't involve checking Twitter or Hacker News.

I got curious Shuffling poker chipshow long it took for chip stacks of various heights to return to their shuffled state. However right now I can only shuffle stacks of 18 chips (9 red, 9 blue) before they come tumbling back to the floor, out of my hand. So I wrote a short program to simulate chip shuffles and determine how long it would take to get the stacks back to their shuffled state.

Here are the results:

Number of Red Chips    Total Shuffles
1                      2
2                      4
3                      3
4                      6
5                      10                     
6                      12
7                      4
8                      8
9                      18
10                     6
11                     11
12                     20
13                     18
14                     28
15                     5
16                     10
17                     12
18                     36
19                     12
20                     20

That's a pretty interesting pattern. I'm sure there's a bunch of cool math behind it; I'll look it up soon and then update this post if I find any. Note that if the number of shuffles is divisible by two, the chips reverse order in the stack (ex. go from all red on the bottom to all red on the top) before returning to their original state.

Update: I found the pattern behind the poker chip shuffle sequence, on a site that lets you plug in any integer sequence and try to find the pattern that matches. You can find the pattern here. Glad I found that page, because I'm not sure I would have guessed the pattern. Here is more detail:

In other words, least m such that 2n+1 divides 2^m-1. Number of riffle shuffles of 2n+2 cards required to return a deck to initial state. A riffle shuffle replaces a list s(1), s(2), ..., s(m) by s(1), s((i/2)+1), s(2), s((i/2)+2), ... a(1) = 2 because a riffle shuffle of [1, 2, 3, 4] requires 2 iterations [1, 2, 3, 4] -> [1, 3, 2, 4] -> [1, 2, 3, 4] to restore the original order.

Here's the example code, in Haskell:

To output numbers, save that code as a file called
chips.hs
and run:
$ ghci
GHCi, version 6.10.4: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> :l chips.hs
[1 of 1] Compiling Main             ( chips.hs, interpreted )
Ok, modules loaded: Main.
*Main> zip [1..20] (map getNumberOfShuffles [1..20])

Liked what you read? I am looking for work.

Leave a Reply

Your email address will not be published. Required fields are marked *

Comments are heavily moderated.