Number of iterations required for a transposition cipher to yield the original input

Question

I have asked this question on math.stackexchange.com but received no response; hoping someone on here can help.

Suppose a function $f$, representing what I call a "dynamic transposition cipher" taking one string of text $str$ as input, is defined so that it outputs another string of text $res$ which is the transposed characters of $str$ according to the following algorithm:

1. Let $i_1 = 1$, $i_2 = $ the number of characters in $str$, and $res = ""$ (empty string)

2. While $i_2 - i_1 > 1$:

   a. Append the character $str[i_1]$ to $res$

   b. Append the character $str[i_2]$ to $res$

   c. Increment $i_1$ by $1$

   d. Decrement $i_2$ by $1$

3. If $i_1 = i_2$, then append the character $str[i_1]$ to $res$; otherwise, append the characters $str[i_1]$ followed by $str[i_2]$ to $res$.

4. Return $res$

Assume that string indices begin at one, i.e. "ABC"$[1] = $ "A" and that each character of $str$ is unique.

For example, $f($"ABCDEF"$)$ would equal "AFBECD", and $f($"AFBECD"$)$ would equal "ADFCBE". We can keep iterating $f \circ f \circ f(x)$, yielding "AEDBFC", "ACEFDB", and finally "ABCDEF", which was our original input. All in all, for any string $str$ of 5 characters, $f(str)$ = 4, since it takes four iterations including the original string.

Let $g(n)$ represent the number of iterations required to transpose a string of $n$ characters back into itself according to $f$.

Following this formula for strings of 1 through 10 characters, there is unusual variation in the number of iterations required: $g(2) = 2$, $g(3) = 3$, $g(4) = 4$, $g(5) = 4$, $g(6) = 6$, $g(7) = 7$, $g(8) = 5$, $g(9) = 5$, and $g(10) = 10$. I have calculated these values up to $g(30)$: $g(28) = 21$, $g(29) = 10$, and $g(30) = 30$.

Plotting these discrete points, we can find several linear functions which collectively fit some of the points: $y = x$ fits some, $y = 0.5x + 1.5$ fits others, while $y = 0.25x + 2.5$ fits still others, while there are many more data pairs not accounted for. I am not noticing much of a pattern that holds consistently besides $y=x$.

What would be a definition of $g(n) \space | \space n \in \Bbb I, n > 0$?

Answer 1

First off, the listed values for $g(n)$ are incremented by 1. For example, for $n=6$, it takes 5 (not 6) iterations of $f$ to take the input string to itself: $f^{(5)}(\texttt{ABCDEF})=\texttt{ABCDEF}$.

It is convenient to index the positions in $n$-symbol string from $0$ to $n-1$. Then the function $f$ defines a permutation where a symbol from position $i$ goes to position $$p(i) = \begin{cases} 2i, & \text{if } i\leq \frac{n-1}2\\ 2n-1-2i, & \text{if } i> \frac{n-1}2. \end{cases}$$

It can be seen that $p(i)\equiv \pm 2i\pmod{2n-1}$. The set of positions $\{ 1, \dots, n-1 \}$ is in one to one correspondence with the subsets $\{i,-i\}$ of $\mathbb{Z}/(2n-1)\mathbb{Z}$. Clearly, $p(\{i,-i\}) = \{2i,-2i\}$.

If $f^{(k)}$ has a fixed point at position $i$, then $2^k i \equiv \pm i\pmod{2n-1}$. To have this hold for all positions, it is sufficient and necessary (by considering $i$ coprime to $2n-1$) that $2^k \equiv \pm 1\pmod{2n-1}$.

It follows that $g(n)=$ A003558$(n-1)$ (or, to match the values listed by OP, $g(n)=$ A003558$(n-1) + 1$).

P.S. Sequence A216066, which is almost identical to A003558, explicitly mentions the transformation $f$ and attributes it to Wolfgang Tomášek.