# Cycle Structure of a Permutation Based on the Binary Representation

This is a question I posted on math.stackexchange.com before but never got an answer. I am cross-posting it here.

Define a permutation $\sigma$ on the set $X=\{1,2,...,n\}$, $n$ is a natural number as follows. Given a non-negative integer $k$, let $s(k)=\frac{b+1}{2}$, where $b=\max\limits_c\big(c2^k\le n, c\text{ is an odd natural number}\big)$. For each $x\in X$, $x=a2^k$, where $a$ is an odd natural number and $k$ a non-negative integer. Define $$f(x) = \sum_{i=0}^{k-1}s(i)+\frac{a+1}{2},$$ and $$\sigma(x)=n+1-f(x).$$

This permutation is equivalent to the following playing card shuffling process. Given a stack of cards, counting from the top first card, take all the odd numbered cards, one by one put them with the latter one on top of the previous one and form another stack. Repeat the previous procedure on the leftover first stack with the current withdrawn cards placed on top of the second stack. Repeat this procedure until the first stack is exhausted. The final second stack is the original first stack permuted described in the first paragraph.

What can we say about the cycle structure of this permutation? What is the least common multiplier of all the cycle lengths? Is the least common multiplier of all the cycle length the maximal cycle length?

Perhaps we may start with $n=2^j$ for any natural number $j$ and recurs on $j$.

As an example, for $n=16$, the inverse of $f$ or $f^{-1}(X)$ \begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ 1&3&5&7&9&11&13&15&2&6&10&14&4&12&8&16 \end{pmatrix}

and the permutation $\sigma(X)$ is

\begin{pmatrix} 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ 16&8&15&4&14&7&13&2&12&6&11&3&10&5&9&1 \end{pmatrix}

The cycle structure is $$(4)(11)(1\ 16)(2\ 8)(5\ 14)(3\ 15\ 9\ 12)(6\ 7\ 13\ 10).$$ Here the maximal cycle length is $4$ and is the least common multiplier of all the cycle lengths.

• I think it would really help if you gave a couple of explicit examples of this permutation for small $n$. The formula is not very transparent, and your narrative description is not so easy to follow. For example, I’m not sure what “one by one put them with the latter one on top of the previous one” means. Would it be possible to walk the reader through the shuffling process for a couple of $n=a2^k$ where $a$ and $k$ are at least 2 or 3? I assume you have computed this permutation for some $n$-values. Can you share the results? – Steve Kass Jun 29 '18 at 23:24
• Maybe this is more explicit: $\sigma(2^k(2\ell+1))=\left[\frac n{2^k}\right]-\ell$, (where "[]" is floor, i. e. integer part) – მამუკა ჯიბლაძე Jun 30 '18 at 19:26
• @SteveKass: Have you seen the example I added as you have requested? – Hans Jul 2 '18 at 8:22
• I posted a Mathematica calculation of your values as an answer so it would have better formatting. I haven’t thought much about whether these numbers can be figured out non-computationally. – Steve Kass Jul 2 '18 at 21:26

This isn’t quite an answer, but I think this Mathematica calculation gives the values of the permutation orders you want. You can investigate other properties (if you have access to Mathematica or there’s still an on-line Wolfram cloud access site) by changing PermutationOrder[p] to something else.

o[n_] :=
Module[{t = Table[i, {i, 1, n}]},
p = PermutationProduct[
FindPermutation[
Sort[t, (IntegerExponent[#1, 2] <
IntegerExponent[#2, 2]) || (IntegerExponent[#1, 2] ==
IntegerExponent[#2, 2] && #1 < #2) &]],
FindPermutation[Length[t] + 1 - t]];
PermutationOrder[p]];

Table[o[i], {i, 1, 100}]


Result (not in OEIS, but see addendum below):

$\{1,2,3,2,4,6,3,4,14,9,18,12,12,42,15,4,24,40,60,51,24,30,130,90,60,72,140,42,156,48,15,12,168,48,414,483,33,36,660,39,380,672,437,364,403,315,550,48,48,369,1950,481,280,180,90,56,144,756,252,4278,4350,816,105,12,432,98,120,1924,186,64,8736,4004,351,552,32604,720,77,496,16740,6783,130,72,1680,330,228,152,87,240,711,6930,1344,1947,495,1680,30240,96,25200,24486,22440,540\}$

Note: If this calculation is correct, it answers at least one of your questions. The order is not the size of the largest cycle, since there are examples where the order exceeds $n$.

For what it’s worth, here are the first $32$ permutations Mathematica came up with.

1:  ()
2:  (1 2)
3:  (1 3 2)
4:  (1 4)
5:  (1 5 3 4)
6:  (1 6 2 3 5 4)
7:  (1 7 4)(2 3 6)
8:  (1 8)(2 4)(3 7 5 6)
9:  (1 9 5 7 6 3 8)(2 4)
10: (1 10 3 9 6 4 2 5 8)
11: (1 11 6 4 2 5 9 7 8)(3 10)
12: (1 12 2 6 5 10 4 3 11 7 9 8)
13: (1 13 7 10 4 3 12 2 6 5 11 8)
14: (1 14 4 3 13 8)(2 7 11 9 10 5 12)
15: (1 15 8)(2 7 12)(3 14 4)(5 13 9 11 10)
16: (1 16)(2 8)(3 15 9 12)(5 14)(6 7 13 10)
17: (1 17 9 13 11 12 3 16)(2 8)(5 15 10 6 7 14)
18: (1 18 5 16)(2 9 14 6 8)(3 17 10 7 15 11 13 12)
19: (1 19 10 7 16)(2 9 15 12 3 18 5 17 11 14 6 8)
20: (1 20 3 19 11 15 13 14 7 17 12 4 5 18 6 9 16)(2 10 8)
21: (1 21 11 16)(2 10 8)(3 20)(4 5 19 12)(6 9 17 13 15 14 7 18)
22: (1 22 6 10 9 18 7 19 13 16)(2 11 17 14 8)(3 21 12 4 5 20)
23: (1 23 12 4 5 21 13 17 15 16)(2 11 18 7 20 3 22 6 10 9 19 14 8)
24: (1 24 2 12 5 22 7 21 14 9 20 4 6 11 19 15 17 16)(3 23 13 18 8)
25: (1 25 13 19 16)(2 12 5 23 14 9 21 15 18 8 3 24)(4 6 11 20)(7 22)
26: (1 26 7 23 15 19 17 18 9 22 8 3 25 14 10 11 21 16)(2 13 20 4 6 12 5 24)
27: (1 27 14 10 11 22 8 3 26 7 24 2 13 21 17 19 18 9 23 16)(4 6 12 5 25 15 20)
28: (1 28 4 7 25 16)(2 14 11 23 17 20 5 26 8 3 27 15 21 18 10 12 6 13 22 9 24)
29: (1 29 15 22 9 25 17 21 19 20 5 27 16)(2 14 11 24)(3 28 4 7 26 8)(6 13 23 18 10 12)
30: (1 30 8 3 29 16)(2 15 23 19 21 20 5 28 4 7 27 17 22 10 13 24)(6 14 12)(9 26)(11 25 18)
31: (1 31 16)(2 15 24)(3 30 8)(4 7 28)(5 29 17 23 20)(6 14 12)(9 27 18 11 26)(10 13 25 19 22)
32: (1 32)(2 16)(3 31 17 24)(4 8)(5 30 9 28)(6 15 25 20)(7 29 18 12)(10 14 13 26)(11 27 19 23 21 22)


Note that $1$ always goes to $n$ (which is clear from the definition). If you look at where $n$ goes for $n=1,2,3,\dots$, you get the sequence $1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9\dots$, which appears in OEIS as A003602. Not surprisingly, this is a “fractal sequence obtained from powers of 2.”

• One might add that the inverse permutation maps $n-k$ to $2k+1$ for $0\leqslant k\leqslant\left[n/2\right]$, $\left[n/2\right]-k$ to $2(2k+1)$ for $0\leqslant k\leqslant\left[n/4\right]$, $\left[n/4\right]-k$ to $4(2k+1)$ for $0\leqslant k\leqslant\left[n/8\right]$, etc. – მამუკა ჯიბლაძე Jul 3 '18 at 5:36