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.

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

Author

David Lovler, Jan 24 2019

Keywords

• nonn

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.

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1024

Crossrefs

Cf. A024222, A022998, A163776, A373416 (fixed points).

Programs

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

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

Formula

a(2^m) = m if m is odd, a(2^m) = 2m if m is even. - Alois P. Heinz, Feb 15 2019