Why does iterating x = f(x) over a finite value range always repeat a value?

## What an implicit sequence is An **implicit sequence** is generated rather than stored: pick a start value `x0` and a step function `f`, and the sequence is `x0, f(x0), f(f(x0)), ...`. There is no container in memory, no chain of stored links, no length field. The "next" relation is *computed on demand*. A state machine whose every state has one outgoing transition is such a sequence; so is repeatedly folding a number into a function of its digits; so is following an array slot to the slot number it stores. The interesting question about such a sequence is whether it ever stops producing new values — and if the value range is finite, the answer is always yes, for two independent reasons that people routinely conflate. ## Reason one: pigeonhole Suppose every value the iteration can ever produce belongs to some finite set of size `N`. Write down the first `N+1` terms. There are `N+1` slots and only `N` distinct values available, so at least two of those terms must be equal. This is pure counting — it says nothing about *which* values repeat or *when*, only that a repeat happens no later than step `N`. Note what the argument needs: a bound on the set of **reachable values**, not a bound on the number of steps. Those are different things, and mixing them up is the classic error. An iteration over a range of a billion values still repeats — just possibly not soon. ## Reason two: determinism turns one repeat into an endless cycle Pigeonhole alone gives you a single coincidence. Determinism upgrades it to structure. If `f` depends only on its argument — no randomness, no hidden counter, no memory of how you arrived — then `x_i == x_j` (with `i < j`) implies `x_{i+1} == x_{j+1}`, and by induction the entire future repeats with period `λ = j - i`. The sequence is periodic from step `i` onward and can never escape. Drop determinism and the guarantee evaporates. A step that consults a random source, a wall clock, or the path taken so far can revisit a value and then behave differently, so the sequence may wander forever without ever settling into a loop. ## The resulting shape Every deterministic iteration over a finite range has the same silhouette: a **tail** of `μ >= 0 ` steps that is walked exactly once, feeding into a **cycle** of length `λ >= 1` that is walked forever. It is often drawn as the Greek letter rho — a straight stroke into a loop. Two special cases matter: - `λ == 1` is a **fixed point**: `f(v) == v`, the value never changes again. It is a cycle, not an exception to the rule. - `μ == 0` means the start value already sits on the cycle, so there is no tail at all. Neither `μ` nor `λ` is bounded by anything better than `N`; you can have a tail of nearly `N` steps ending in a fixed point, or no tail and a cycle of nearly `N` values. ## A worked example: folding a number through its digits Take a positive integer and repeatedly replace it with the sum of the **cubes** of its digits. Is the value range finite? A number with `d` digits is at least `10^(d-1)`, but the largest value the map can produce from it is `729 * d` (each digit contributes at most `9^3 = 729`). For `d = 5` that is `3645`, already smaller than `10000`, and the gap only widens — so any starting value shrinks within a couple of steps into a small window of a few thousand values and can never climb back out. Finite window plus a deterministic map means the iteration must repeat. What it repeats *into* varies: some starts land on a fixed point (`153` maps to `1 + 125 + 27 = 153` and stays), others fall into a genuine loop (`136` maps to `244`, which maps back to `136`, forever). So a routine written as "keep folding until the value stops changing" does not merely run slowly on some inputs — it never returns at all on the ones that orbit. ## Why this matters for the fast/slow pattern This argument is the *precondition* that makes the two-pointer trick meaningful on sequences that were never stored anywhere. With a stored list you have an end marker to stop at; with an implicit sequence you have nothing, so detecting the cycle **is** the termination test. Recognising "the values are bounded and the step is deterministic" is what tells you a cycle is guaranteed to exist and therefore worth hunting with a constant-space technique instead of an ever-growing record of everything seen. ## What the argument does not give you It does not promise convergence to any particular value, does not bound how long the tail is relative to the cycle, does not require `f` to be reversible or one-to-one (in fact merges — two values mapping to the same successor — are exactly what create the tail), and it says nothing at all when the value range is unbounded. The map `x -> 2x` over the integers is perfectly deterministic and never repeats a value, because pigeonhole has no pen to put the pigeons in.