Now all we have to do is figure out the least common multiple of the lengths of the cycles! I wrote a C program to calculate the cycles for deck with indices from 3 to 201. The program displays the actual cycles for decks up to index 51 and then just lists the lengths of the cycles thereafter. The data generated shows an interesting fact: the length of the first cycle (the one containing card number `1`, the bottom card) is ALWAYS the least common multiple of the lengths of all the cycles.

Claim 3: We only need to find the length of the first cycle.

Claim 3.1: No other cycle can will ever be longer than the first cycle. Suppose the first cycle has length `m+1`. That cycle will
therefore be: `( 1 2 4 8 ... 2 ^{m} )`, all mod

Now let's look at the cycle beginning with with some number `k`, not in the cycle starting with 1. The first `m+1` elements in this second cycle will be `( k 2k 4k 8k ... 2 ^{m}k )` all mod

We know that `2 ^{m+1} mod i = 1`, so there exists some number

Claim 3.2: The length of every other cycle must divide the first cycle. Suppose the length of the cycle for `k` does NOT divide the length of the cycle for `1`. Then the `k` cycle will not produce `k` when the shuffling is repeated for the length of the `1` cycle. This contradicts our observation that any cycle for `k` will repeat at the length of the cycle for `1`.

Finally, we can observe that for a deck with index `i = 2n + 1`, the cycle containing card number `1` will have
length `x` where `x` is the smallest number such that `2 ^{x} mod i = 1`.

We have made a lot of progress; we have reduced the problem to what seems like a relatively straightforward calculation. Nevertheless, I want to see if we can find something a bit more elegant.

Home |

Shuffle Problem |

Initial Ideas |

Permutation |

Cycle Length |

Groups |

Last modified: |

© 2006 |

Peter C. Scott |