OFFSET
1,2
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.
LINKS
Hong-Chang Wang, Table of n, a(n) for n = 1..100
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)
EXAMPLE
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
PROG
(C)
int a(int n)
{
int c[101];
int i, step, B, P, m;
for (i=1 ; i<n+1 ; i++) { c[i] = i; }
step = 0;
next:
B = c[n];
for (i=n-1 ; i>0 ; 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<n ; i++) { if ( c[i] != i ) goto next; }
return step;
}
#include <stdio.h>
int main()
{
int n;
for (n=1; n<=100; ++n) printf("%d, ", a(n));
printf("\n");
return 0;
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Hong-Chang Wang, Jul 10 2013
STATUS
approved