For any prime number $n$, let $x$ be the set [1:n] and let $S$ be a concatenated sequence of $n$ sub-sequences that are constructed by repeating each $(i \in x)$ for $n$ times.
For example when $n=5$ , S=[ 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5].
Now, Suppose we circularly shift $S$ with an integer ($j \in [1:n^2]$ ) such that $j$ is not a multiple of $n$.
I need to derive a formula in terms of $j$ and $n$ that find how many rotation times needed to make $S$ starts with all the $n$ numbers?
For example, consider our $S$ sequence mentioned above for $n=5$ , Suppose the rotation shift is $j=6$.
- Without rotation:
S=[ 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5].
- 1st rotation: $S1=$ Rotate($S,6$),
S1=[2 2 2 2 3 3 3 3 3 4 4 4 4 4 5 5 5 5 5 1 1 1 1 1 2].
- 2nd rotation: $S2=$ Rotate($S1,6$),
S2=[3 3 3 4 4 4 4 4 5 5 5 5 5 1 1 1 1 1 2 2 2 2 2 3 3].
- 3rd rotation: $S3=$ Rotate($S2,6$),
S3=[4 4 5 5 5 5 5 1 1 1 1 1 2 2 2 2 2 3 3 3 3].
- 4th rotation: $S4=$ Rotate($S3,6$),
S4=[5 1 1 1 1 1 2 2 2 2 2 3 3 3 3 4 4 5 5 5 5].
As we can see from the example , 4 times of rotations needed to guarantee that $S$ starts with the {2, 3, 4, 5} numbers.
Please be informed that the upper bound can be derived as $lcm(j,n^2)$. However, this bound is not tight to obtain the exact number of rotations. Therefore, I am looking for a formula that find the lower-bound of rotations which obtain the exact required number of rotations.
Also, Please note that I can find that number of rotations through simulation where the tables below give some examples. However, I could not derive an exact mathematical formula for the lower-bound in terms of $n$ and $j$. So, I need an urgent help on that please.
1) When $n=3$ $$\begin{array}{c|c|} \text{the shift amount } (j) & \text{Number of rotations} \\ \hline 4, 7 & 2 \\ \hline 2, 5 & 3 \\ \hline 8 & 4 \\ \hline 1 & 6 \\ \hline \end{array}$$
2) When $n=5$ $$\begin{array}{c|c|} \text{the shift amount } (j) & \text{Number of rotations} \\ \hline 6, 11, 16, 21 & 4 \\ \hline 4, 9, 14, 19 & 5 \\ \hline 7, 18, 22 & 6 \\ \hline 3 & 7 \\ \hline 8, 23 & 8 \\ \hline 2, 17 & 10 \\ \hline 12 & 12 \\ \hline 13 & 15 \\ \hline 24 & 16 \\ \hline 1 & 20 \\ \hline \end{array}$$
Thanks in advance.