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,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

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

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

Adjacent sequences: A323709 A323710 A323711 * A323713 A323714 A323715

Keyword

nonn

Author

David Lovler, Jan 24 2019

Status

approved