Determine the next number in the sequence - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T03:01:59Z http://mathoverflow.net/feeds/question/90727 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/90727/determine-the-next-number-in-the-sequence Determine the next number in the sequence Chong Luo 2012-03-09T16:21:34Z 2012-03-09T21:24:19Z <p>This problem originates from a <a href="http://www.ardendertat.com/2011/10/18/programming-interview-questions-9-convert-array/" rel="nofollow">programming interview problem</a>. 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$. </p> <p>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.</p> <p>When I program this idea, however, I need to find out <b>the next element that has not been moved into its correct final position</b>. 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:</p> <pre> 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 </pre> <p>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!</p>