On a giant tape measure sits an N-frog: that is, a frog with a special preference for the number N. The frog's location at the beginning of each of its jumps is called M. The frog moves on the tape measure according to the following rules:
Whenever M>N, then the N-frog makes an N-jump to the left and lands on the number M-N.
Whenever M<N, then the N-frog makes an N-jump to the right and lands on number M+N; during landing it also changes its preference and becomes an M-frog.
Whenever M=N then the frog is happy and stays on that number.
Where will a 851-frog that sits on 1517 be happy?
Where will an N-frog that sits on M be happy?
(In reply to
Why does it stop? by Old Original Oskar!)
After writing the previous message, it dawned on me that you could
rewrite the algorithm in a much shorter way, and that showed me what
the algorithm actually was.
If you apply rule 1, you go from (M,N) to (M-N,N) -- you subtracted the lower number from the higher one.
If you happen to apply rule 2, you go from (M,N) to (N+M,M) and then to
(N,M) and finally to (N-M,M), so once again it's as if you had
subtracted the lower number from the higher one.
So, the algorithm is equivalent to saying: "while M and N are not
equal, subtract the lower one from the higher one"... and that's the
old fashioned description of Euclid's algorithm!
The frog will stop at the GCD of M and N.
re: Why does it stop?
