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

Offset

1,2

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

Links

Robert Israel, Table of n, a(n) for n = 1..4000

Andrew Warren, C program to generate a(n)

Example

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.

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 *)

Prog

(C) // see link
(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(d<n, d*=2); 2*n-d;
Follow(s, f)={my(t=f(s), k=1); while(t>s, 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

Crossrefs

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

Sequence in context: A070669 A218613 A164912 * A088861 A088631 A086184

Adjacent sequences: A289383 A289384 A289385 * A289387 A289388 A289389

Keyword

nonn,look

Author

Andrew Warren, Jul 04 2017

Status

approved