This problem originates from a programming interview problem. In that problem, we are asked to convert the array $[a_0, a_1, \cdots, a_{N-1}, b_0, b_1, \cdots, b_{N-1}, c_0, c_1, \cdots, c_{N-1}]$ into $[a_0, b_0, c_0, \cdots, a_{N-1}, b_{N-1}, c_{N-1}]$ in place. We can verify that the number originally at index $i$ would be moved to the new index $$ f(i) = 3(i \mod N)+[i/N], \qquad 0\leq i \leq 3N-1. $$ It also seems that if we repeatedly apply $f$ to the same index $i$, eventually there will be an integer $n$ such that $f^n(i)=i$.
My idea was that we repeatedly move the element at index $i$ to the index $f(i)$, and the element at the index $f(i)$ to the index $f^2(i)$ etc. Since these indices form a loop, eventually we'll move all the elements in the set $f^k(i)$ to their correct final positions.
When I program this idea, however, I need to find out the next element that has not been moved into its correct final position. For example, in the case N=1001, the next elements (x), the cyclic length, and the sum of the elements in the set $f^k(x)$ are the following:
x= 0, len= 1, sum= 0 x= 1, len= 234, sum= 351234 x= 2, len= 234, sum= 351234 x= 4, len= 234, sum= 351234 x= 5, len= 234, sum= 351234 x= 7, len= 234, sum= 351234 x= 10, len= 234, sum= 351234 x= 11, len= 234, sum= 351234 x= 14, len= 234, sum= 351234 x= 19, len= 78, sum= 117078 x= 20, len= 234, sum= 351234 x= 22, len= 234, sum= 351234 x= 35, len= 234, sum= 351234 x= 38, len= 78, sum= 117078 x= 61, len= 234, sum= 351234 x= 79, len= 18, sum= 27018 x= 158, len= 18, sum= 27018 x= 1501, len= 1, sum= 1501 x= 3002, len= 1, sum= 3002
What I'm interested to know, is for any positive interger $N$, to find a way to get the next "x" in the sequence in $O(1)$ time and $O(1)$ space. Thanks!
