A019567 Order of the Mongean shuffle permutation of 2n cards: a(n) is least number m for which either 2^m + 1 or 2^m - 1 is divisible by 4n + 1.

1, 2, 3, 6, 4, 6, 10, 14, 5, 18, 10, 12, 21, 26, 9, 30, 6, 22, 9, 30, 27, 8, 11, 10, 24, 50, 12, 18, 14, 12, 55, 50, 7, 18, 34, 46, 14, 74, 24, 26, 33, 20, 78, 86, 29, 90, 18, 18, 48, 98, 33, 10, 45, 70, 15, 24, 60, 38, 29, 78, 12, 84, 41, 110, 8, 84, 26, 134, 12, 46, 35, 36, 68, 146

Offset: 0

Author

John Bullitt (metta(AT)world.std.com), N. J. A. Sloane and J. H. Conway

Keywords

• nonn
• easy

Comments

Write down 1, then 2 to left, 3 to right, 4 to left, ..., getting [ 2n,2n-2,...,4,2,1,3,5,...,2n-1 ]; the sequence 2,3,6,4,6,10,14,5,18,10,12,21,26,9,... gives order of permutation sending 1 to 2n, 2 to 2n-2, ..., 2n to 2n-1.

Equivalently, the sequence 2,3,6,4,6,10,14,5,18,10,12,21,26,9,... gives the number of Mongean shuffles needed to return a deck of 2n cards (n=1,2,3,...) to its original order.

It appears that a(n) = order((-1)^(n+1)*2 in Z_{2n+1}) / f with f=1 when n==2 (mod 3) and for n = 0, 19, 21, 30,33, 52, 55, 61, 63, 70, ..., f=2 else. I don't know how to characterize the "exceptional" n's. - M. F. Hasler, Mar 31 2019

Examples

			Illustrating the initial terms:
   n  4n+1  2^m+1  2^m-1  m
   0    1            1    1
   1    5     5           2
   2    9     9           3
   3   13    5*13         6
   4   17     17          4
   5   21           3*21  6
   6   25   41*25        10
		

References

• A. P. Domoryad, Mathematical Games and Pastimes, Pergamon Press, 1964; see pp. 134-135.
• W. W. Rouse Ball, Mathematical Recreations and Essays, 11th ed. 1939, p. 311

Links

• R. J. Mathar, Table of n, a(n) for n = 0..2000
• P. Diaconis, The mathematics of perfect shuffles, Adv. Appl. Math. 4 (2) (1983) 175-196.
• Arne Ledet, The Monge shuffle for two-power decks, Math. Scand. Vol 98, No 1 (2006), 5-11.
• E. Ross, Mathematics and Music: The Mathieu Group M_12 (2011), Chapter 2.
• T. & X. Vigouroux, First 2000000 terms, for n = 0..1999999

Crossrefs

Cf. A163777, A238371, A294673.

Programs

Maple

A019567:=  proc(n)
    for m from 1 do
        if modp(2^m-1,4*n+1) =0 or modp(2^m+1,4*n+1)=0 then
            return m ;
        end if;
    end do;
end proc: # N. J. A. Sloane, Jul 28 2007

Mathematica

a[n_] := For[m=1, True, m++, If[AnyTrue[{-1, 1}, Divisible[2^m+#, 4n+1]&], Return[m]]];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Aug 26 2019 *)

PARI

A019567(n,z=Mod(2,4*n+1))=for(m=1,oo,bittest(5,lift(z^m+1))&&return(m)) \\ M. F. Hasler, Mar 31 2019

Formula

a(A163777(n)/2) = A163777(n). - Andrew Howroyd, Nov 11 2017

Extensions

Comments corrected by Mikko Nieminen, Jul 26 2007, who also provided the Domoryad reference

Definition edited by N. J. A. Sloane, Nov 09 2017