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?

An 851-frog which sits on 1517 will be happy as a 37-frog sitting on 37 after 18 hops: ('x: N on M' denotes an N-frog sitting on M after x hops)

0: 851 on 1517
1: 851 on 666
2: 666 on 1517
3: 666 on 851
4: 666 on 185
5: 185 on 851
6: 185 on 666
7: 185 on 481
8: 185 on 296
9: 185 on 111
10: 111 on 296
11: 111 on 185
12: 111 on 74
13: 74 on 185
14: 74 on 111
15: 74 on 37
16: 37 on 111
17: 37 on 74
18: 37 on 37, a happy 37-frog


As for the second question, "Where will an N-frog that sits on M be happy?" I have an answer, which I'm fairly certain is right, but cannot prove. The frog will end up as a happy y-frog sitting on y, where y is the greatest common factor of M and N. For example, the prime factorization of 851 is 23 * 37, while the prime factorization of 1517 is 37 * 41. The only factors they share are 1 and 37, our answer to part 1. I have also tested this with other low M-N pairing and a randomly chosen high pairing (of 57382 (2*13*2207) and 42894 (2*3*3*2383) and had it work out correctly. However, I have no formal proof, as before stated.

Posted by Tiralmo on 2005-07-09 07:33:11