A227392 Number of 2-Bottom-Card shuffles required to return a deck of size n to its original order.

1, 2, 2, 3, 5, 6, 10, 6, 9, 10, 24, 9, 13, 14, 44, 12, 17, 18, 70, 15, 21, 22, 102, 18, 25, 26, 140, 21, 29, 30, 184, 24, 33, 34, 234, 27, 37, 38, 290, 30, 41, 42, 352, 33, 45, 46, 420, 36, 49, 50

Offset: 1

Author

Hong-Chang Wang, Jul 10 2013

Keywords

• nonn

Comments

Apply the P card and the B card, the two cards on the bottom of the stack, to do shuffling a deck of cards. The T cards are on the top of cards and the M cards are between the T cards and the P card.

The shuffling steps are like this: (T)(M) P B -> B (T)(M) P -> B (T) P (M).

Let n = T + M +2, (n >= 2). New P = ceiling((n+1)/2).

Count cycles to return original order for the deck of size n.

Order (4k+1)th and (4k+2)th items, k >= 0, can get a Latin square.

Examples

			a(1) = 1
  1
  1
.
a(2) = 2
  1 2
  2 1
  1 2
.
a(3) = 2
  1 2 3
  3 2 1
  1 2 3
.
a(4) = 3
  1 2 3 4
  4 1 3 2
  2 4 3 1
  1 2 3 4
.
a(5) = 5
  1 2 3 4 5
  5 1 4 2 3
  3 5 2 1 4
  4 3 1 5 2
  2 4 5 3 1
  1 2 3 4 5
.
a(6) = 6
  1 2 3 4 5 6
  6 1 2 5 3 4
  4 6 1 3 2 5
  5 4 6 2 1 3
  3 5 4 1 6 2
  2 3 5 6 4 1
  1 2 3 4 5 6
.
a(7) = 10
  1 2 3 4 5 6 7
  7 1 2 6 3 4 5
  5 7 1 4 2 6 3
  3 5 7 6 1 4 2
  2 3 5 4 7 6 1
  1 2 3 6 5 4 7
  7 1 2 4 3 6 5
  5 7 1 6 2 4 3
  3 5 7 4 1 6 2
  2 3 5 6 7 4 1
  1 2 3 4 5 6 7
.
a(8) = 6
  1 2 3 4 5 6 7 8
  8 1 2 3 7 4 5 6
  6 8 1 2 5 3 7 4
  4 6 8 1 7 2 5 3
  3 4 6 8 5 1 7 2
  2 3 4 6 7 8 5 1
  1 2 3 4 5 6 7 8
.
a(9) = 9
  1 2 3 4 5 6 7 8 9
  9 1 2 3 8 4 5 6 7
  7 9 1 2 6 3 8 4 5
  5 7 9 1 4 2 6 3 8
  8 5 7 9 3 1 4 2 6
  6 8 5 7 2 9 3 1 4
  4 6 8 5 1 7 2 9 3
  3 4 6 8 9 5 1 7 2
  2 3 4 6 7 8 9 5 1
  1 2 3 4 5 6 7 8 9
		

Links

• Hong-Chang Wang, Table of n, a(n) for n = 1..100

Programs

C

int a(int n)
{
    int c[101];
    int i, step, B, P, m;
    for (i=1 ; i0 ; i--)  { c[i+1] = c[i]; }
    c[1] = B;
    m = (n+2)/2;
    P = c[n];
    if ( n>2 )  { for (i=n-1 ; i>=m ; i--)  c[i+1] = c[i]; }
    c[m] = P;
    step++;
    for (i=1 ; i
int main()
{
    int n;
    for (n=1; n<=100; ++n)  printf("%d, ", a(n));
    printf("\n");
    return 0;
}

Formula

a(4k+1) = 4k+1, k >= 0;

a(4k+2) = 4k+2, k >= 0;

a(4k+3) = 8k+2, k=0,1;

a(4k+3) = a(4k-1) + 6k + 2, k >= 2;

a(4k+4) = 3*(k+1), k >= 0.

From Joerg Arndt, Jul 16 2013: (Start)

G.f.: x*(2*x^9 + 3*x^8 + 3*x^7 - 4*x^6 - 2*x^4 - 3*x^3 - 2*x^2 - 2*x - 1) / ((x-1)*(x+1)*(x^2+1))^3;

a(n) = 3*a(n-4) - 3*a(n-8) + a(n-12). (End)