Consider a cycle of length n. Consider two integers, i and j that have arbitrary initial values in [0, n).

We want to prove that the following loop always terminates:

    while i % n != j % n:
        i += 1
        j += 2

If we represent this as an equation over time, where t is the number of loops, we want to prove that for some t the following is true:

    (i + t) % n = (j + 2t) % n

Solving for t:

    (i % n) + (t % n) = (j % n) + (2t % n)
    (i % n) - (j % n) = t % n
    (i - j) % n = t % n

We can generalize for arbitrary speeds of the pointers. Let's say i moves at speed x and j moves at speed y:

    (i + x*t) % n = (j + y*t) % n
    (i % n) + (x*t) % n = (j % n) + (y*t % n)
    (i - j) % n = t*(y - x) % n

This will always have a solution if (y-x) is coprime with n.

A trivial case where it doesn't work, for example, is x=2, y=4, n=any even number. Imagine if i starts on an odd number and j starts on an even number. It's clear that i will always be odd and j will always be even. Note that y-x (2 in this case) shares a prime factor (not coprime) with all even numbers.

Thank you very much. I like the equation over time.

Your explanation is difficult to follow when you do distributivity of % over +. I mean when you move from

    (i + t) % n = (j + 2t) % n

to

    (i % n) + (t % n) = (j % n) + (2t % n)

Here I read the '=' as normal number equality. A simplified example to demostrate that distributivity is not valid here:

    (5 + x) % 3 = 4
    5 % 3 + x % 3 = 4

In the second line x=5 is a solution. But in the first line x is not a solution.

It's better to express your explanation using "= (mod n)" from the beginning.

    (i + t) % n = (j + 2t) % n 
    i + t = j + 2t (mod n)

Note that if you add the requirement that i and j start on the same node, then no matter what step size you use for x and y, as long as they are integers > 0 and x != y, then i and j will meet again if and only if there is a cycle.

For particular values of x, y, and loop period there may be values of i and j such that going forward from those they never meet, but it is not possible to get into one of those positions if a past state had i == j.

Proof:

In the following I'll use your notation for the most part, except allowing for a "lead in" of length L from that common starting node to the start of the loop, so the nodes are numbered 0, 1, 2, ..., L-1, L, L+1, ..., L+n-1, with the nodes in the loop being {L, L+1, L+2, ..., L+n-1}.

At time t, i has taken xt steps and j has taken yt steps. Let t >= L/x and t >= L/y, so that i and j are both past the lead in into the loop.

Then i is xt-L steps into the loop, and j is yt-L into the loop. These will be at the same spot in the loop if xt-L = yt-L mod n, which happens whenever (x-y)t = 0 mod n. All multiples of n are solutions of this, so just pick any that are >= L/x and L/y, and you have a solution.

If i and j do not start at the same place, all bets are off. That 0 is replaced with the differences between the starting node numbers, and as your example shows may not have a solution for some combinations of parameters.

Hi! Just a question, since I've never been good with proofs. Why use the modulo operator in the while-loop? Couldn't we just test if i != j?

The modulo represents the cycle.

Maybe it would be helpful to rewrite the loop with a condition as you described, and %= i and j with n after incrementing (by 1 or by 2) both variables in the loop body.

Intuitive explanation: Once the pointers enter the cycle the fast one will eventually approach the slow one from behind like runners on a stadium track. If it's one node behind the slow one, then they'll meet on the next move (slow advances one, fast advances two). And if the fast one is two nodes behind, on the next move it'll be one node behind.

3 will also work. People pick 2 intuitively, and it minimizes the overall runtime of the algorithm.

(google "Proof of Floyd's Cycle Chasing" for details)

Another advantage of 2 is that it works even if the two pointers do not start on the same element.

It's not specifically 2, any two speeds that are coprime will have the same property.

Counterexample: loop of 8 nodes, numbered 0, 1, ..., 7.

Start with one pointer at node 0, moving with speed 5. Start the second pointer at node 1, with speed 3 which is coprime to 5, the speed of the first pointer.

The pointer positions at each step are:

  0 5 2 7 4 1 6 3 repeat
  1 4 7 2 5 0 3 6 repeat

The condition we need in order to guarantee it works regardless of where the two pointers start is that the difference between the speeds is coprime to the cycle length.

Off the top of my head, because if you don’t know where the last element points back to, and there’s an even chance it could be any previous element, the median element is the one on the middle. Two at a time means when you reach the last element and loop back. The lagging pointer will point to the middle element so. Across a population on lists, it will perform better that ratios that favour the lagging pointer being closer to ge back end of the list when the leading pointer loops.

Also, with a 3 skip you could jump 2 ahead of the lagging pointer when you loop back behind and jump over it, which means when it advances it won’t catch you so they won’t meet.