OFFSET
0,2
COMMENTS
The "inside-out" permutation (closely related to the Mongean shuffle, see A019567) sends (t_1, t_2, ..., t_{2n+1}) to (t_{n+1}, t_{n+2}, t_{n}, t_{n+3}, t_{n-1}, ..., t_1). For n = 0, 1, 2, 3, this is (1), (2,3,1), (3,4,2,5,1), (4,5,3,6,2,7,1), whose orders are respectively 1,3,5,4.
LINKS
Robert Israel, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Table of n, a(n) for n = 0..32683 (computed using Robert Israel's Maple program)
FORMULA
The permutation sends i (1 <= i <= 2n+1) to p(i) = n + 1 + f(i), where f(i) = (-1)^i*ceiling((i-1)/2).
a(n) = minimal k>0 such that p^k() = p^0().
From Joseph L. Wetherell, Nov 14 2017: (Start)
a(n) is equal to the order of multiplication-by-2 acting on the set of nonzero elements in (Z/(4n+3)Z), modulo the action of +-1. To be precise, identify i=1,2,...,2*n+1 with the odd representatives J=1,3,...,4*n+1 of this set, via the map J = 2*i-1. It is not hard to show that the induced permutation on the set of J values is given on integer representatives by J -> (4*n+3+J)/2 if i=(J+1)/2 is even and J -> (4*n+3-J)/2 if i=(J+1)/2 is odd. It follows that this induces the permutation J -> +-J/2 (mod 4*n+3), from which we immediately see that the order is as stated.
Note that the order of 2 acting on (Z/(4n+3)Z)/{+-1} is the same as the order of either 2 or -2 acting on (Z/(4n+3)Z), depending on which of these is a quadratic residue modulo 4n+3. Thus an equivalent (and often easier) way to compute a(n) is as the order of -2*(-1)^n acting on (Z/(4n+3)Z).
Among other things, the lower and upper bounds log_2(n) + 2 < a(n) <= 2*n+1 follow immediately.
(End)
It appears that the upper bound a(n) = 2n+1 occurs iff 2n+1 belongs to A163778 or equivalently iff n belongs to A294434. This almost (but not quite) follows from the above comments by Andrew Howroyd and Joseph L. Wetherell. - N. J. A. Sloane, Nov 16 2017
EXAMPLE
For n=2: Iterating the "inside-out" permutation of a string of length 2n+1=5:
12345
34251
25413
41532
53124
12345
...
which has order a(2) = 5.
MAPLE
f:= proc(n)
ilcm(op(map(nops, convert(map(op, [[n+1], seq([n+1+i, n+1-i], i=1..n)]), disjcyc))))
end proc:
map(f, [$0..100]); # Robert Israel, Nov 09 2017
MATHEMATICA
a[n_] := MultiplicativeOrder[-2(-1)^n, 4n+3];
a /@ Range[0, 100] (* Jean-François Alcover, Apr 07 2020 *)
PROG
(PARI)
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(p=0); for(i=1, 2*n+1, my(l=Follow(i, j->n+1+(-1)^j*ceil((j-1)/2) )); if(l, p+=x^l)); p}
a(n)={my(p=CyclePoly(n, x), m=1); for(i=1, poldegree(p), if(polcoeff(p, i), m=lcm(m, i))); m} \\ Andrew Howroyd, Nov 08 2017
(PARI) a(n)=znorder(Mod(if(n%2, 2, -2), 4*n+3)) \\ See Wetherell formula; Charles R Greathouse IV, Nov 15 2017
(Magma)
f:=func<n| Order(Sym(2*n+1)![n+1+(-1)^i*Ceiling((i-1)/2): i in [1..2*n+1]]) >;
[f(n): n in [0..100]]; \\ Joseph L. Wetherell, Nov 12 2017
(Magma)
[Order(Integers(4*n+3)!-2*(-1)^n): n in [0..100]];
\\ Joseph L. Wetherell, Nov 15 2017
CROSSREFS
KEYWORD
nonn,look
AUTHOR
P. Michael Hutchins, Nov 06 2017
STATUS
approved