A289386 Number of rounds of 'deal one, skip one' shuffling required to return a deck of n cards to its original order.

1, 2, 3, 2, 5, 6, 5, 4, 6, 6, 15, 12, 12, 30, 15, 4, 17, 18, 10, 20, 21, 14, 24, 90, 63, 26, 27, 18, 66, 12, 210, 12, 33, 90, 35, 30, 110, 120, 120, 26, 41, 42, 105, 30, 45, 30, 60, 48, 120, 50, 42, 510, 53, 1680, 120, 1584, 57, 336, 276, 60, 2665, 720, 8415

Offset: 1

Author

Andrew Warren, Jul 04 2017

Keywords

• nonn
• look
• changed

Comments

Origin unknown. First encountered by this author as part of an employment-interview question at Apple Inc, in early 2016.

While holding a deck of n cards:

1. Deal the top card from the deck onto the table ('deal one').

2. Move the next card from the top of the deck to the bottom of the deck ('skip one').

3. Repeat steps 1 and 2 until all cards are on the table. This is a round.

4. Pick up the deck from the table and repeat steps 1 through 3 until the deck is in its original order.

From Robert Israel, Jul 06 2017: (Start)

a(n) <= A000793(n).

a(n) divides n!.

Conjecture: a(n) < n for infinitely many n.

Conjecture: the set of n for which the permutation is a single n-cycle, and thus a(n) = n, has nonzero density. (End)

It appears that for n = 2^k and all m > n, a(n) <= a(m). - Andrew Warren, Jul 15 2017

a(2^(k+1)) / a(2^k) = A020513(k+2) at least for 1 <= k <= 30, according to the values computed by Andrew Warren. - Andrey Zabolotskiy, Apr 02 2018

Examples

			Cards are labeled 'A', 'B', 'C', etc. 'ABCD' is a deck with 'A' on top, 'D' on the bottom.
For n = 4:
Round 1:
Hand: ABCD    Table: [empty] - initial state of Round 1
Hand: BCD     Table: A       - Deal one
Hand: CDB     Table: A       - Skip one
Hand: DB      Table: CA      - Deal one
Hand: BD      Table: CA      - Skip one
Hand: D       Table: BCA     - Deal one
Hand: D       Table: BCA     - Skip one
Hand: [empty] Table: DBCA    - Deal one, end of Round 1
Round 2:
Hand: DBCA    Table: [empty] - Initial state of Round 2
Hand: BCA     Table: D       - Deal one
Hand: CAB     Table: D       - Skip one
Hand: AB      Table: CD      - Deal one
Hand: BA      Table: CD      - Skip one
Hand: A       Table: BCD     - Deal one
Hand: A       Table: BCD     - Skip one
Hand [empty]  Table: ABCD    - Deal one, end of Round 2
The deck of 4 cards is in its original order ('ABCD') after 2 rounds, so a(4) = 2.
		

Links

• Robert Israel, Table of n, a(n) for n = 1..4000
• Andrew Warren, C program to generate a(n)

Crossrefs

Cf. A000793, A051732 (variation with cards dealt face up), A020513, A051168.

Programs

C

// see link

Maple

F:= proc(n)
local deck, table, i;
deck:= [$1..n];
table:= NULL;
for i from 1 to n-1 do
  table:= deck[1],table;
  deck:= deck[[$3..nops(deck),2]];
od:
ilcm(op(map(nops,convert([deck[1],table],'disjcyc'))));
end proc:
map(F, [$1..100]); # Robert Israel, Jul 06 2017

Mathematica

P[n_, i_] := Module[{d = 2i - 1}, While[d < n, d *= 2]; 2n - d];
Follow[s_, f_] := Module[{t = f[s], k = 1}, While[t > s, k++; t = f[t]]; If[s == t, k, 0]];
CyclePoly[n_, x_] := Module[{q = 0}, For[i = 1, i <= n, i++, l = Follow[i, P[n, #]&]; If[l != 0, q += x^l]]; q];
a[n_] := Module[{q = CyclePoly[n, x], m = 1}, For[i = 1, i <= Exponent[q, x], i++, If[Coefficient[q, x, i] != 0, m = LCM[m, i]]]; m];
Array[a, 60] (* Jean-François Alcover, Apr 09 2020, after Andrew Howroyd *)

PARI

deal(v)=my(deck=List(v),new=List(),cutoff=4000+#v,i=1); while(#deck>=i, listput(new,deck[i]); if(i++>#deck, break); listput(deck, deck[i]); if(#deck>cutoff, deck=List(deck[i+1..#deck]); i=0); i++); Vecrev(new)
ordered(v)=for(i=1,#v, if(v[i]!=i, return(0))); 1
a(n)=my(v=[1..n],t=1); while(!ordered(v=deal(v)), t++); t \\ Charles R Greathouse IV, Jul 06 2017

PARI

\\ alternative for larger n such as 2^n.
P(n,i)=my(d=2*i-1); while(ds, k++; t=f(t)); if(s==t, k, 0)}
CyclePoly(n, x)={my(q=0); for(i=1, n, my(l=Follow(i, j->P(n, j))); if(l, q+=x^l)); q}
a(n)={my(q=CyclePoly(n, x), m=1); for(i=1, poldegree(q), if(polcoeff(q, i), m=lcm(m, i))); m} \\ Andrew Howroyd, Nov 11 2017