Detecting Cycles in an Iterated Sequence

Define $x_0 = 2$ and $x_{n+1} = (x_n^2 + 3) \bmod 20$, and ask: does this sequence ever repeat a value? With only 20 possible remainders, it must eventually repeat by pigeonhole — but where does the loop start, and how long is it? Storing every value you've seen and checking for repeats works, but it costs memory proportional to how far you go. There's a classic trick that finds the cycle using only two pointers and no memory of history at all.

The shape of an eventually-periodic sequence

Once a deterministic sequence $x_{n+1} = f(x_n)$ repeats any value, it's trapped: from that point on it must retrace exactly the same steps forever, because $f$ always produces the same output from the same input. So the sequence looks like a "rho" shape — a straight run-in of length $\mu$ (the tail), followed by a loop of length $\lambda$ (the cycle) that it circles forever after.

Floyd's cycle detection ("tortoise and hare")

Run two pointers through the sequence at different speeds: the tortoise moves one step per iteration, $t \leftarrow f(t)$; the hare moves two steps, $h \leftarrow f(f(h))$. Both start at $x_0$. Because the hare gains one extra step on the tortoise every iteration, and both are eventually confined to a loop of finite length $\lambda$, the hare is guaranteed to lap the tortoise and land on exactly the same value within one full loop — so if a cycle exists, the two pointers must meet. In plain English: imagine two runners on a circular track who never leave the track once they enter it — the faster one, going twice the speed, is bound to catch up to the slower one from behind, no matter where either started.

Worked example: tracing the sequence by hand

$x_0=2$: $x_1 = (4+3)\bmod 20 = 7$, $x_2 = (49+3)\bmod20 = 12$, $x_3=(144+3)\bmod20=7$. Already $x_3 = x_1 = 7$ — the sequence hit 7 again after just one extra step, so the tail is $x_0=2$ alone ($\mu=1$) and the cycle is $7 \to 12 \to 7 \to \cdots$, length $\lambda = 2$. Run the tortoise/hare check: tortoise at $x_0=2$, hare at $x_0=2$. Step 1: tortoise$\to x_1=7$, hare$\to x_2=12$ (two steps: $2\to7\to12$). Not equal. Step 2: tortoise$\to x_2=12$, hare$\to x_4 = f(f(12)) = f(7) = 12$ (since $x_3=7$, $x_4=12$). Tortoise is at 12, hare is at 12 — they meet, confirming a cycle exists, found in just two iterations without ever storing a list of past values.

What this means in practice

This exact two-pointer trick, at constant memory, is used to detect loops in linked-list-style structures generally, and the underlying pigeonhole reasoning — a process with finitely many states run forward indefinitely must repeat a state — is the same argument behind guaranteeing that a deterministic pseudo-random generator or a discretized mean-reverting process with finite precision eventually cycles.