The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A289386 Number of rounds of 'deal one, skip one' shuffling required to return a deck of n cards to its original order. 3
 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 (list; graph; refs; listen; history; text; internal format)
 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(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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 15 15:16 EDT 2021. Contains 345049 sequences. (Running on oeis4.)