A294673 Order of the "inside-out" permutation on 2n+1 letters.

1, 3, 5, 4, 9, 11, 9, 5, 12, 12, 7, 23, 8, 20, 29, 6, 33, 35, 20, 39, 41, 28, 12, 36, 15, 51, 53, 36, 44, 24, 20, 7, 65, 36, 69, 60, 42, 15, 20, 52, 81, 83, 9, 60, 89, 60, 40, 95, 12, 99, 84, 66, 105, 28, 18, 37, 113, 30, 92, 119, 81, 36, 25, 8, 36, 131, 22, 135, 20, 30, 47, 60, 48, 116, 132, 100, 51, 155

Offset: 0

Author

P. Michael Hutchins, Nov 06 2017

Keywords

• nonn
• look

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.

This is the odd bisection of A238371 and also the odd bisection of A003558 (see Joseph L. Wetherell's comment below).

Examples

			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.
		

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)

Crossrefs

Cf. A003558, A019567, A163778, A238371, A294434.

Programs

Magma

f:=func;
[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

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

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

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().

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

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