Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
In case anyone else is wondering: The question appears to be using the term "perfect shuffle" to refer to a shuffle similar to the Faro shuffle, but with the even-numbered cards preceding the odd-numbered cards. @Ben: It would have been a good idea to explain what you mean by "perfect shuffle" in the question. –  joriki Jun 21 '12 at 11:32
    
@joriki Especially since the answer is different if the shuffle results in the odd-numbered cards preceding the odd-numbered ones. –  Rick Decker Jun 21 '12 at 12:59

1 Answer 1

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.

share|improve this answer
    
Just to clarify: The first of these sequences gives the number $a_n$ of out shuffles for a deck of $n$ cards; the second gives the number $b_n$ of in shuffles 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}$. –  joriki Jun 22 '12 at 13:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.