Consider the function $f(x) = x^2 + 2$ mod $17$. Use the two-pebble algorithm to determine the following parameters for starting point $x = 0$. The transient is 3, Period is 4, and the Meeting Time is 3 - but how?
I got the period as 4 because if we compute f(0) we get - 2,6,4,1,3,11,4,1,3,11 and if we compute ff(0) we get (6,4,1,3,11,4,1,3,11,4) . If we take point 1 in the loop, it takes 4 steps to get to the next point 1 in the loop, so the period is 4.
However with transient someone explained it like this:
How can we get the transient? Now that we know what the period is, we can start all over. Race two 'pebbles' down the track, recursively applying the function to the both of them, starting at your base input. However this time, instead of applying the function twice to one pebble for every time we apply it once to the other one, we will put the other one on 'pause' at the beginning while we move our first pebble one down the line of recursion the period numbers of times. This is the equivalent of giving it a 'head start' in our race. The consequence of this, is that after we apply f recursively to both of these pebbles the transient numbers of times, each will meet up! Why? The one that starts at the beginning, after moving the transient number of times, has travelled to the very beginning of the cycle (definition of the transient). The one that we gave the head start has moved (period + transient) spaces. But this is the same thing as (transient + period) number of spaces. Hence, it has moved to the start of the cycle, and then around the cycle one time. They will both be at the start of the cycle!!! Using this information, we can calculate the transient by just computing more iterations until the two pebbles meet up!
The problem is, I'm not able to get to the point where the values match up, so it's impossible to find the transient value.
Please help!
 A: The period here is $4$, so the second pebble starts at $\ p_{20}=f^4(0)=1\ $, while the first one starts at $\ p_{10}=0\ $.  The sequences resulting from the recursive application of $\ f\ $ to these starting points are given in the following table:
\begin{array}{c|ccccccc}
t&0&1&2&3&4&5&6\\
\hline
p_{1t}&0&2&6&\color{red}4&1&3&11\\
\hline
p_{2t}&1&3&11& \color{red}4&1&3&11\\
\hline
\end{array}
We see that the two sequences match at $\ t=3\ $, and hence thereafter, so the length of the transient is $3$.
Reply to query below from OP
Yes, the sequence you get by iterating $\ f^2\ $ on $\ 0\ $ does eventually match up with the original sequence, although, if $\ d\ $ is the period,  it's only every $\ d$-th term where they match. The sequence in question is
$$\ f^0(0), f^2(0), \dots, f^{2t}(0), \dots=p_{10}, p_{12},\dots,p_{1\,2t}, \dots\ ,
$$
and its $\ (t+1)$-th term, $\ p_{1\,2t}\ $, will match the $\ (t+1)$-th term, $\ p_{1t}\ $, of the original whenever $\ 2t=$$t+nd\ $, for some positive integer $\ n\ $, and $\ t\ge$$\text{length of transient}\ $. That is $\ t=nd=4n\ $, in this case.
\begin{array}{c|ccccccc}
t&0&1&2&3&4&5&6&7&8\\
\hline
p_{1t}&0&2&6&4&\color{red}1&3&11&4&\color{red}1\\
\hline
p_{1\,2t}&0&6&1&11&\color{red}1&11&1&11&\color{red}1\\
\hline
\end{array}
