Riffle Shuffles

A riffle shuffle is executed as follows: a deck of cards is split into two equal halves, with the top half taken in the left hand and the bottom half taken in the right hand. Next, the cards are interleaved exactly, with the top card in the right half inserted just after the top card in the left half, the 2nd card in the right half just after the 2nd card in the left half, etc. (Note that this process preserves the location of the top and bottom card of the deck)

Let $s(n)$ be the minimum number of consecutive riffle shuffles needed to restore a deck of size $n$ to its original configuration, where $n$ is a positive even number.

Amazingly, a standard deck of $52$ cards will first return to its original configuration after only $8$ perfect shuffles, so $s(52) = 8$. It can be verified that a deck of $86$ cards will also return to its original configuration after exactly $8$ shuffles, and the sum of all values of $n$ that satisfy $s(n) = 8$ is $412$.

Find the sum of all values of n that satisfy $s(n) = 60$.

Mathematically, for a deck of $n$ cards, we can apply this process of shuffling as an operation on numbers from $1$ to $n$. Consider number $1$ as the top card, and $n$ as the bottom card, each number in the top half will be mapped to their $2i$ modulo $n$, where $i$ is the initial position of the number before shuffling.

In essence, we can formulate it as follows: a riffle shuffle is equivalent to multiplying an integer’s position by $2$ modulo ($n$), where $n$ is the deck size.

Since $s(n)$ represents the minimum number of these operations needed before each number in the deck returns to its initial position, we are looking for the order of $2$ modulo $n$, or the minimum positive integer $k$ such that $2^k \equiv 1$ mod $n$, i.e., $n$ divides $2^k – 1$.

The number $60 = 2^2 \cdot 3 \cdot 5$ has $16$ distinct divisors, i.e., $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$.

So, we are looking for distinct even $n$ such that the only divisors of $2^k – 1$ are from this list.

The solution is obtained by finding such $n$ for each divisor and then adding them up.

We only consider divisors greater than $2$ because $s(n)$ for $n = 2$ is $1$.

Furthermore, if one divisor divides $n$, all of its divisors also divide $n$. Therefore, we have:
1. If $2^k – 1$ is divisible by $60$, it must be divisible by all divisors of $60$. Thus, $2^4 – 1, 2^{12} – 1, 2^{20} – 1, $ and $2^{60} – 1$ all are divisible by $60$, $33$, $129$, and $189$ respectively.
2. If it’s divisible by $30$, remove every multiple of $4, 5$, and $60$. We get $2^2 – 1, 2^6 – 1, 2^{10} – 1,$ and $2^{30} – 1$ all are divisible by $30$, $5$, $21$, and $85$ respectively.
3. Divisible by $20$ will remove multiples of $2, 4, 5$, and $60$. So only $2^{12} – 1, 2^{36} – 1, 2^{60} – 1$ are divisible by $20$, $37$, $109$, and $205$ respectively.
4. $2^3 – 1, 2^9 – 1, 2^{15} – 1, 2^{45} – 1$ are divisible by $15$, $7$, $23$, and $103$ respectively.
5. $2^2 – 1, 2^6 – 1, 2^{10} – 1,$ and $2^{30} – 1$ all are divisible by $12$, $5$, $21$, and $85$ respectively.
6. $2^1 – 1, 2^3 – 1, 2^9 – 1, 2^{27} – 1$ are divisible by $10$, $3$, $11$, and $59$ respectively.
7. $2^2 – 1, 2^6 – 1, 2^{10} – 1,$ and $2^{30} – 1$ all are divisible by $6$, $5$, $21$, and $85$ respectively.
8. $2^1 – 1, 2^3 – 1, 2^9 – 1, 2^{27} – 1$ are divisible by $5$, $3$, $11$, and $59$ respectively.
9. $2^1 – 1, 2^3 – 1, 2^9 – 1, 2^{27} – 1$ are divisible by $4$, $3$, $11$, and $59$ respectively.
10. $2^1 – 1$ is divisible by $3$, which does not count.
11. No need to consider $2$.

Summing up all $n$, we find that the sum of all $n$ such that $s(n) = 60$ is $1 + 33 + 129 + 189 + 5 + 21 + 85 + 37 + 109 + 205 + 7 + 23 + 103 + 5 + 21 + 85 + 3 + 11 + 59 + 5 + 21 + 85 + 3 + 11 + 59 + 3 + 11 + 59 = 1820$

More Answers: