Limit Cycles of xy (mod x+y)
For any two positive integers x and y define F(x,y) = xy (mod x+y).
Given two initial values x[0] and x[1] we can form a sequence using
the recurrence
x[n] = F( x[n-1] , x[n-2] )
For some initial values this produces a trivial outcome. For example,
if x[1] = x[0] is odd, then x[n] = x[0] for all n. Slightly less
obvious is the fact that if x[0]=2k and x[1]=2k-6 then x[n]=2k-6n for
all n up to k/3, at which point the sequence terminates with a value
of 0.
Most initial values lead to a fixed point, but some lead to a limit
cycle. The smallest limit cycle is {5,7,11}. Of course, it follows
that {7,5,11} is also a limit cycle. (I wonder if it's true that if
xy = z (mod x+y) and xz = y (mod x+z) then yz = x (mod y+z).)
Anyway, here are several examples of limit cycles with period 3 (along
with their gcd factorizations):
{5,7,11} 1*[5,7,11]
{69,99,111} 3*[23,33,37]
{87,111,153} 3*[29,37,51]
{184,704,776} 8*[23,88,97]
{125,475,575} 25*[5,19,23]
{384,864,1056} 96*[4,9,11]
{315,525,735} 105*[3,5,7]
{324,756,864} 108*[3,7,8]
{1575,2205,2835} 45*[35,49,63]
The smallest limit cycles with period 4 are
{96,304,384,464} 16*[6,19,24,29]
{128,192,256,320} 64*[2,3,4,5]
{243,1701,1215,2187} 243*[1,7,5,9]
{495,1375,1815,1045} 55*[9,25,33,19]
{1331,1815,2783,2541} 121*[11,15,23,21]
There smallest examples with period 5 are
{124,310,248,434,558} 62*[2,5,4,7,9]
{243,621,567,549,675} 9*[27,69,63,61,75]
{392,490,686,980,882} 14*[4,5,7,10,9]
Here are limit cycles with periods 6 and 7:
{23,61,59,119,79,95} 1*[23,61,59,119,79,95]
{77,343,371,161,147,259,315} 7*[11,49,53,23,21,37,45]
The table below presents one cycle for for each of the periods 8
through 19, and also a cycle of period 22.
T=8, gcd=59 T=9, gcd=65 T=10, gcd=441 T=11, gcd=319
1711 29 455 7 3087 7 15631 49
6431 109 1235 19 10143 23 10527 33
3599 61 845 13 9261 21 13717 43
5959 101 1495 23 18963 43 1595 5
7847 133 2015 31 6615 15 13079 41
13157 223 845 13 5733 13 9251 29
8319 141 975 15 3087 7 9889 31
11387 193 1235 19 4851 11 13079 41
1885 29 3969 9 5423 17
8379 19 9251 29
12441 39
T=12, gcd=1023 T=13, gcd=71 T=14, gcd=7161 T=15, gcd=107
17391 17 35855 505 279279 39 17441 163
25575 25 29749 419 136059 19 13375 125
33759 33 60563 853 393855 55 27071 253
17391 17 54599 769 494109 69 2033 19
3069 3 32731 461 221991 31 28783 269
13299 13 46079 649 565719 79 27071 253
9207 9 24779 349 708939 99 21293 199
11253 11 56587 797 594363 83 20651 193
17391 17 70361 991 451143 63 22791 213
5115 5 47783 673 737583 103 6313 59
11253 11 35855 505 93093 13 18511 173
9207 9 18673 263 136059 19 13375 125
25631 361 221991 31 21721 203
207669 29 28783 269
6527 61
T=16, gcd=12051 T=17, gcd=75087 T=18, gcd=551 T=19, gcd=4875
445887 37 2027349 27 143811 261 375375 77
397683 33 1276479 17 330049 599 687375 141
735111 61 3078567 41 15979 29 443625 91
1000233 83 2628045 35 40223 73 1038375 213
1409967 117 675783 9 53447 97 531375 109
735111 61 2177523 29 72181 131 960375 197
2012517 167 375435 5 73283 133 541125 111
1554579 129 2477871 33 132791 241 258375 53
2374047 197 1877175 25 96425 175 609375 125
1988415 165 3679263 49 137199 249 102375 21
1072539 89 1426653 19 220951 401 589875 121
277173 23 1877175 25 82099 149 24375 5
735111 61 976131 13 192299 349 453375 93
397683 33 1276479 17 66671 121 180375 37
1000233 83 2027349 27 197809 359 316875 65
60255 5 3078567 41 93119 169 424125 87
976131 13 251807 457 180375 37
291479 529 258375 53
365625 75
T=22, gcd=1129
624337 553
649175 575
1136903 1007
495631 439
567887 503
235961 209
134351 119
296927 263
86933 77
89191 79
134351 119
154673 137
224671 199
351119 311
147899 131
339829 301
486599 431
473051 419
655949 581
712399 631
1096259 971
716915 635
It can be shown that there exists a cycle of length n for every positive
integer n. See More Results on the Form xy (mod x+y).
There is an interesting class of cycles of period 9, in which the cycle consists
of just four distinct numbers in the pattern A BC A DB A CD. Several examples
are shown below
3575 9295 12155 3575 7865 9295 3575 12155 7865 5 11 13
5 13 17 5 11 13 5 17 11
8381 5423 7395 8381 9367 5423 8381 7395 9367 17 29
17 11 15 17 19 11 17 15 19
8300 5810 9130 8300 10790 5810 8300 9130 10790 2 5 83
10 7 11 10 13 7 10 11 13
52731 29295 41013 52731 76167 29295 52731 41013 76167 3 3 3 7 31
9 5 7 9 13 5 9 7 13
72471 123627 46893 72471 89523 123627 72471 46893 89523 3 7 7 29
17 29 11 17 21 29 17 11 21
132759 122925 113091 132759 34419 122925 132759 113091 34419 3 11 149
27 25 23 27 7 25 27 23 7
106029 82467 129591 106029 223839 82467 106029 129591 223839 3 3 7 11 17
9 7 11 9 19 7 9 11 19
197519 245891 116899 197519 173333 245891 197519 116899 173333 29 139
49 61 29 49 43 61 49 29 43
931095 517275 1344915 931095 1138005 517275 931095 1344915 1138005 3 3 5 11 11 19
9 5 13 9 11 5 9 13 11
1576575 735735 1156155 1576575 1366365 735735 1576575 1156155 1366365 3 5 7 7 11 13
15 7 11 15 13 7 15 11 13
In many of these cycles the reduced term appearing three times (i.e., the
"A" term of the cycle) is the product of the first two or three prime divisors
of the cycle's greatest common divisor.
Another interesting cycle of period 9 is shown below. In this cycle the
greatest common divisor of the cycle is one of the terms of the cycle.
80087 51821 98931 80087 108353 4711 80087 23555 61243 7 673
17 11 21 17 23 1 17 5 13
Return to MathPages Main Menu