Eight Perfect Shuffles and the Deck Comes Home

The club regular who’s been humbling me all week did something quiet on Thursday: he split the deck exactly in half, riffled the two halves into each other so they alternated one-for-one, and did it eight times. On the eighth weave he fanned the cards and every one sat exactly where it had started. No control, no palm — just arithmetic wearing a tuxedo.

That weave is the faro, and it’s a genuine sleight (interleaving 26 and 26 perfectly is harder than any double lift I fumbled this week). Keep the original top card on top — an out-faro — and the whole deck is a permutation. Card at position i moves to 2i mod 51, with the bottom card pinned. Apply it enough times and you’re guaranteed to return home, because a permutation of a finite set always cycles. The only question is when.

So I let the machine weave instead of my clumsy thumbs:

fun outFaro(d: IntArray): IntArray {
    val n = d.size / 2
    val out = IntArray(d.size)
    for (i in 0 until n) {
        out[2 * i] = d[i]            // top half
        out[2 * i + 1] = d[n + i]    // bottom half woven in
    }
    return out
}

fun main() {
    val orig = IntArray(52) { it }
    var deck = orig.copyOf()
    var shuffles = 0
    do { deck = outFaro(deck); shuffles++ } while (!deck.contentEquals(orig))
    println("Out-faros to restore 52 cards: $shuffles")
}

It prints 8. You don’t even have to move the cards to know that — the cycle length is just the smallest k where 2^k ≡ 1 (mod 51). Forth, all stack and no ceremony, computes it directly:

variable m
: faro-order ( n -- k )   \ perfect out-shuffle order, even deck n
  1- m !                  \ modulus = n-1
  1 0                     \ acc count
  begin
    swap 2* m @ mod       \ acc = acc*2 mod (n-1)
    swap 1+               \ count++
    over 1 =
  until
  nip ;
52 faro-order . cr        \ prints 8

What delighted me: this exact 2i mod (n−1) map is the perfect-shuffle interconnection network that Harold Stone wired into parallel machines in the ’70s, and that Diaconis, Graham and Kantor pinned down mathematically in 1983 — the same decade Forth was living on every embedded board in sight. FFT butterflies ride this permutation; so does a card cheat at a green baize table. The magician isn’t hiding the order. He’s counting on you not knowing it’s exactly eight.