1
$\begingroup$

How many times do we need to perfectly shuffle a deck of 2n cards for them to return to their original order.

for $n=3$ we have the permutation $(142)(356)$

I am interested when 2n+1 is prime. Here is how far I have got:

let $a$ denote the position of a card. then what we are trying to find is the minimum x such that: $2^xa=a ($mod$2n+1)$

as we are only interested in when 2n+1 is prime we are looking for the multiplicative order of 2 mod $2n+1$

Case 1:

$p=2n+1$ where $n$ is prime and $n=3($mod$4)$

if we have the prime $p=2n+1$ where $n$ is prime and $n=3($mod$4)$ -> $p|2^n-1$

proof of above theorem http://en.wikipedia.org/wiki/Mersenne_prime

so the order of such a deck of 2n cards is $n$ eg $23=2*11+1$ then $2^{11}=1 ($mod$23)$

Case 2: $p=2^q-1$ then order is $q$

case 3: $p=2^q+1$ then order is $2q$

After this i thought that all other orders of 2 would just be $2n$ by fermats little theorem but this is not the case as take $2n = 102$

i would of expected $2^{102}$ to be the minimum power of 2 as 103 doesn't fit into any of the above cases but $2^{51}$ is the actual order.

  • 0
    @joriki Especially since the answer is different if the shuffle results in the odd-numbered cards preceding the odd-numbered ones.2012-06-21

1 Answers 1

3

You'll find data and links at the Online Encyclopedia of Integer Sequences.

Shuffles (perfect faro shuffles with cut) required to return a deck of size n to original order.

Multiplicative order of 2 mod 2n+1.

There are probably some others there.

  • 0
    Just to clarify: The first of these sequences gives the number $a_n$ of [out shuffles](http://en.wikipedia.org/wiki/Out_shuffle) for a deck of $n$ cards; the second gives the number $b_n$ of [in shuffles](http://en.wikipedia.org/wiki/In_shuffle) for a deck of $2n$ cards, which is what the question asked for; this is also the number of out shuffles for a deck of $2n+2$ cards. The two are related by $a_n=b_{\lfloor (n-1)/2\rfloor}$.2012-06-22