login
A323712
Number of the following described shuffles required to return a deck of n cards to its original state. Create two piles by alternating a card from the top of the deck left-right-left-right until the deck is exhausted. Then, placing the left pile on top of the right pile constitutes one shuffle.
3
1, 1, 3, 4, 4, 6, 6, 3, 9, 5, 5, 12, 12, 4, 12, 8, 8, 9, 9, 6, 6, 22, 22, 20, 20, 9, 27, 28, 28, 10, 10, 5, 15, 12, 12, 36, 36, 12, 12, 20, 20, 7, 7, 12, 36, 46, 46, 42, 42, 8, 24, 52, 52, 20, 20, 9, 9, 29, 29, 60, 60, 6, 18, 12, 12, 33, 33, 22, 66, 70, 70, 18
OFFSET
1,3
COMMENTS
The card shuffling procedure is the same for even n and odd n.
Here are a few conjectures.
a(n) <= n for all n.
a(p)=a(p-1) and a(p)|p-1 when p is a prime >= 5.
a(n)=a(n-1) and a(n)|n-1 for nonprimes 341=31*11 and 22369621=8191*2731 and probably other pseudoprimes of the form p*((p+2)/3) where p is a Mersenne prime and (p+2)/3 is prime.
n cards are returned to their original state after n shuffles when n=1, 3, 4, 6, 9, 12, 22, 27, 28, 36, 46, 52, 60, 70, 78, 81, ... (A373461) . These values of n are either of the form p-1 where p is an odd prime number or 3^i, i >= 0.
a(c) is relatively small (compared with nearby values) when c is a Catalan number.
a(2n+1)=3*a(2n) or a(2n+1)=a(2n) for all n.
LINKS
FORMULA
a(2^m) = m if m is odd, a(2^m) = 2m if m is even. - Alois P. Heinz, Feb 15 2019
EXAMPLE
For n=4, {a1,a2,a3,a4}-->{a3,a1,a4,a2}-->{a4,a3,a2,a1}-->{a2,a4,a1,a3}-->{a1,a2,a3,a4}, so a(4)=4.
For n=5, {a1,a2,a3,a4,a5}-->{a5,a3,a1,a4,a2}-->{a2,a1,a5,a4,a3}-->{a3,a5,a2,a4,a1}-->{a1,a2,a3,a4,a5}, so a(5)=4.
MAPLE
pileShuf := proc(L::list)
local i, n, shf ;
shf := [] ;
n := nops(L) ;
if type(n, 'odd') then
for i from n to 1 by -2 do
shf := [op(shf), op(i, L)] ;
end do:
for i from n-1 to 2 by -2 do
shf := [op(shf), op(i, L)] ;
end do:
else
for i from n-1 to 1 by -2 do
shf := [op(shf), op(i, L)] ;
end do:
for i from n to 2 by -2 do
shf := [op(shf), op(i, L)] ;
end do:
end if;
shf ;
end proc:
A323712 := proc(n)
local L, itr, isord, i;
L := [seq(i, i=1..n)] ;
for itr from 1 to n! do
L := pileShuf(L) ;
isord := true ;
for i from 1 to nops(L) do
if op(i, L) <> i then
isord := false ;
break ;
end if;
end do:
if isord then
return itr ;
end if;
end do:
-1 ;
end proc:
seq(A323712(n), n=1..50) ; # R. J. Mathar, Aug 02 2024
PROG
(PARI) perm(n, vn) = {my(va = List(), vb = List()); for (k=1, n, if (k % 2, listput(va, vn[k]), listput(vb, vn[k])); ); Vec(concat(Vecrev(va), Vecrev(vb))); }
a(n) = {my(vn = vector(n, k, k), vs = perm(n, vn), nb = 1); while (vs != vn, vs = perm(n, vs); nb++); nb; } \\ Michel Marcus, Feb 06 2019
CROSSREFS
Cf. A024222, A022998, A163776, A373416 (fixed points).
Sequence in context: A341933 A061117 A255171 * A215250 A354154 A229022
KEYWORD
nonn
AUTHOR
David Lovler, Jan 24 2019
STATUS
approved