[jdunford]

Well, I've worked out the following:

n - bin - shuffles - bin
1 - 0001 - 1 - 0001
2 - 0010 - 2 - 0010
3 - 0011 - 4 - 0100
4 - 0100 - 3 - 0011
5 - 0101 - 6 - 0110
6 - 0110 - 10 - 1010
7 - 0111 - 12 - 1100
8 - 1000 - 4 - 0100
9 - 1001 - 8 - 1000
10 - 1010 - 18 - 10100

(bin just means the binary form of the previous number... 'cause it's really a binary problem)
I'm certain that stacks of size 2^m require m+1 shuffles to return to their original state. As for 2^m + k, I'm not certain I've got it yet.
The only patterns I see beyond that are:
- for 2^m+1, it takes 2*(m+1)
- for everything else, it takes 2*(n-1)
but I'm not sure how long it obeys that trend.