Calculating how many decks of given size can be perfectly shuffled $k$ times and return to their original ordering.

Question

This question originates from Riffle Shuffles, Problem 622 on projecteuler.net

I´m just trying to wrap my head around something I just found. I understand how to use the equation but not why it works.

So what i worked out so far is that the position of the $j$th card after a perfect shuffle is: $2j \ (\mathrm{mod} \ 2n-1)$ where $2n$ is the size of the deck.

I also got how to calculate the sum of all deck sizes that satisfy a particular minimum shuffles.

In line with the problem proposed on projecteuler, here's an example determining the sum of all deck sizes that can be returned to their original ordering using 8 shuffles:

In this case the sum will be 412

You can calculate this by:

1. Get all divisors of $2^8 - 1$
2. Remove all divisors that are also divisors of $2^i - 1$ for $i = 1, \ldots, 7$.
3. Add all the remaining divisors together with the number(how many there are left) of all divisors

The question for me is: Why does this work? Or more specific, why can we just sum together the divisors that aren't also divisors of the same function with all real numbers greater than 0 but less then 8 to get the number of deck sizes that satisfy $k = 8$ shuffles?

EDIT: Dumb question, we´re talking about the SUM of the solutions... Next time I´ll read the question twice but maybe this post is useful to someone.

Answer 1

This result is taken from The Book of Numbers. John H. Conway, Richard Guy. pp. 163-165, 1996.

If you have a deck of $2n$ cards, and you preform an out-shuffle. After the first shuffle, the card in the $j$th position in the deck is moved to the $2j \ (\textrm{mod} \ 2n - 1)$th position, and $k$ consecutive shuffles moves the $j$th card to the $2^kj \ (\textrm{mod} \ 2n - 1)$th position in the deck.

It follows that if the number of shuffles $k$ is a number such that $2^k \equiv 1 \ (\textrm{mod} \ 2n - 1)$ you would get the deck back in its original order. In your case $k= 8,$ so the problem becomes finding all deck sizes $2n$ such that $2^8 \equiv 1 \ (\textrm{mod} \ 2n - 1)$.

Consider the following python code:

>>> for i in range(1, 9):
print([2*n for n in range(1, 256) if 2**i % (2*n - 1) == 1])

Output:
[]
[4]
[8]
[4, 6, 16]
[32]
[4, 8, 10, 22, 64]
[128]
[4, 6, 16, 18, 52, 86, 256]

The output shows all decks of given size that can be put in their original ordering by $1$ to $8$ shuffles respectively. I didn't understand your calculation, but I suspect you are removing duplicates in the last list? That is, removing the decks of given size that can be shuffled into their original ordering by 2 and 4 shuffles, as 2 and 4 are divisors of 8.

Edit:

Here is a purely mathematical proof. The equation $2^8 \equiv 1 \ (\textrm{mod} \ 2n - 1)$ is equivalent to $2^8 - 1\equiv 0 \ (\textrm{mod} \ 2n - 1)$, meaning $2n - 1$ divides $2^8 - 1$. This gives you a concrete way of checking whether a deck of size $2n$ can return to its original order after 8 shuffles.

In general this can be extended to say a deck of size $2n$ can be shuffled $k$ and return to its original order if $2n - 1$ is a divisor of $2^k - 1$. Note, this only tells you that it is possible to shuffle it $k$ times and have it return to its original order, but not that $k$ is the smallest such number. This explains how your calculation is valid, you are simply removing duplicates.