Return to Answer

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.

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.

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

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.

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.

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

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