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?
Lets start start with arbitrary positive integers M0, and N0. If M0 > N0, the frog will jump down the measuring-tape until it finds an M < N0. Let W0 be the first M such that M < N0. It follows that W0 = M0 % N0 (% is the modulo operator, or the remainder when M0 is divided by N0).
For the next iteration, N1 = W0, and
- W1 = (N0 + W0) % N1 = N0 % W0
It follows for any integer k > 1 that:
This forces 0 ¡Ü Wk ¡Ü W(k-1), and since Wk is always in integer if we start with integers, Wk must converge for a finite k.
As for where the frog will be happy, this will happen at the greatest common divisor of M and N.
This can be shown by noticing that if X and Y are relatively prime (ie. if GCD(M,N) = 1), X % Y is relatively prime to Y. Thus, by recursion, if M and N are relatively prime, the frog will be happy when it reaches 1. Next, note that the space of sequences (Wk) is closed under scalar multiplication. This means for an arbitrary M and N, M = sX, N = sY for some positive integers s, X and Y with X and Y relatively prime. Since we know the frog starting on (X,Y) will be happy at 1, our (M,N) frog will be happy at s = GCD(M,N). //
Solution for positive integers M, N
