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
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)
Programs
-
Magma
f:=func
-
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().
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
Comments