Cycle lengths for Perfect shuffles of decks of any size

Question

Challenge

In the shortest amount of code:

1. Compute the length of the permutation cycle of a perfect shuffle on a deck of cards of any size n (where n ≥ 2 and n is even).
2. Output a table of all cycle lengths for 2 ≤ n ≤ 1000 (n even).

Note that there are two basic ways of defining a perfect shuffle. There is the out-shuffle, which keeps the first card on top and the last card on bottom, and there is the in-shuffle, which moves the first and last cards one position toward the center. You may choose whether you are doing an out-shuffle or an in-shuffle; the algorithm is almost identical between the two.

• out-shuffle of 10-card deck: [1,2,3,4,5,6,7,8,9,10] ↦ [1,6,2,7,3,8,4,9,5,10].
• in-shuffle of 10-card deck: [1,2,3,4,5,6,7,8,9,10] ↦ [6,1,7,2,8,3,9,4,10,5].

Graphical example

Here, we see that an out-shuffle on a 20-card deck has a cycle length of 18 steps. (This is for illustration only; your solution is not required to output cycles graphically.) The classic 52-card deck, on the other hand, has an out-shuffle cycle length of only 8 steps (not shown).

An in-shuffle on a 20-card deck has a cycle length of only 6 steps.

Tabular example of output

Your program should output something similar to this, although you may choose any tabular format that you like best. This is for an out-shuffle:

2 1
4 2
6 4
8 3
10 6
12 10
14 12
16 4
18 8
20 18
22 6
24 11
26 20
28 18
30 28
32 5
34 10
36 12
38 36
40 12
...many lines omitted...
1000 36

Questions

1. Does there seem to be any connection between the number input n and its cycle count, when n is a power of 2?
2. How about when n is not a power of 2?
3. Curiously, a 1000-card deck has an out-shuffle cycle count of only 36, while a 500-card deck has an out-shuffle cycle count of 166. Why might this be?
4. What is the largest number you can find whose cycle count c is vastly smaller than n, meaning that ratio n/c is maximized?

Answer 1

Haskell, 47 46 44 (in shuffle)

[[i|i<-[1..],mod(2^i)n<2]!!0|n<-[3,5..1001]]

the basic realization is that this is the order of 2 in the multiplicative group of modulus n+1.

Answer 2

Pyth, 16 bytes

mfq1%^2T+3yd)500

In-shuffle using A002326.

Answer 3

Pyth, 22 bytes

V500,JyhNl{.u.iFc2NJUJ

Try it online: Demonstration. Replace 500 with a smaller number, if it is too slow.

Explanation:

V500                     for N in [0, 1, ..., 499]:
      yhN                   (N + 1) * 2
     J                      assign to J
           .u      JUJ      apply the following expression J times
                            to N, starting with N = [0, 1, ..., J - 1],
                            and return all intermediate results:
                c2N            split N into 2 halfs
             .iF               and interleave them
         l{                 remove duplicates and give length
    ,                       make a pair and print

Answer 4

Mathematica, 53 (in-shuffle)

Grid[{2#,MultiplicativeOrder[2,2#+1]}&/@Range[1,500]]

or, not antagonistically spaced

Grid[{2 #, MultiplicativeOrder[2, 2 # + 1]} & /@ Range[1, 501]]

Output:

   2    2
   4    4
   6    3
   8    6
  10   10
  12   12
  14    4
  16    8
  18   18
  20    6
 (* digits, digits, bo bidgits, banana fana, ... *)
  498  166
  500  166
 (* skip a bit, brother ...  *)
  998   36
 1000   60

Every entry in both columns is horizontally centered in their columns, but I don't have the fractional spaces   ...   here to replicate that.

Observations:

• Out-shuffle is in-shuffle on a deck two cards smaller. (Note that the first and last cards are in fixed position throughout the out-shuffle demonstration.) Consequently, the two choices will lead to similar output lists -- the second column will be shifted by one row. Regarding the "powers of two" hint, the in-shuffle of power of two decks has the pattern {2^n - 2, n}, {2^n, 2n}. (Out-shuffle pairs 2^n with n.)
• Observe in the in-shuffle example that the distance of 2 from the closest end of the deck doubles at each step. {2, 4, 8, 15 = -5, -10, -20}. In fact, this is true for every card. We therefore only need to know which power of 2 is congruent to 1 mod n+1 where n is the number of cards. (Note that in the example, the cards in the last column, column -1, are doubled to the penultimate column, -2, meaning that 0 is congruent to one more card than is in the deck, thus "mod n+1".) Therefore, the MultiplicativeOrder[] function is the way to go (in Mathematica).
• By default, one would try TableForm[] instead of Grid[], but the output is similar.

Answer 5

C,86 (or 84)

Score excludes unnecessary whitespace, included for clarity.

i,j,n;
main(){
  for(;n<1002;printf("%d %d\n",n,j),n+=2)
    for(i=n,j=1;i=i*2%(n+1),i-n;)j++;
}

This is an in-shuffle, which as pointed out by others, is just the out shuffle with the stationary cards at both ends removed.

As pointed out by others, in the in-shuffle, the position of each card doubles each time, but this must be taken modulo n+1. I like to think of the extra card position being position zero to the left of the table (you can think of this as holding both the stationary cards from the out-shuffle too). Obviously the position of the card must always be positive, hence the zero position always remains empty for the in-shuffle case.

The code initialises i to the value of n. Then it multiplies by 2, takes the result mod (n+1) and checks to see if i has returned to its initial value (i-n is zero.) It increments j for each iteration, except the last one (hence the need initialise j to 1.)

In principle, i could be with any value in the range 1..n, so long as the comparison at the end checked if it was intialised to the same number. The reason for picking n was to make sure the program works for the case n==0. the problem was that any number modulo (0+1) is zero, so the loop never terminated in this case if i was initialised to a constant such as 1.

The question examples includes the equivalent case n==2 for the out shuffle, so it was interpreted that this case is required. If it isn't, two bytes n, could be saved by initializing i to 1, the same value as j.