|
|
A294673
|
|
Order of the "inside-out" permutation on 2n+1 letters.
|
|
6
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
This is the odd bisection of A238371 and also the odd bisection of A003558 (see Joseph L. Wetherell's comment below).
|
|
LINKS
|
|
|
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(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)
|
|
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:
|
|
MATHEMATICA
|
a[n_] := MultiplicativeOrder[-2(-1)^n, 4n+3];
|
|
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
(Magma)
f:=func<n| Order(Sym(2*n+1)![n+1+(-1)^i*Ceiling((i-1)/2): i in [1..2*n+1]]) >;
(Magma)
[Order(Integers(4*n+3)!-2*(-1)^n): n in [0..100]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|