Here's a summary of recent comments concerning integer sequences generated by iterations of the function f(x,y) = kxy (mod x+y) (1) As discussed in Limit Cycles of xy (mod x+y), given any two positive integers x[0] and x[1] we define a sequence by the recurrence x[n] = f(x[n-1],x[n-2]), with the understanding that the least non-negative residue is assigned at each stage, and the sequence terminates at the kth term if x[k]=0. The previous article treated only the case k=1, but in subsequent discussions of other quadratic forms David Einstein observed that every function of the form f(x,y) = Ax^2 +Bxy + Cy^2 (mod x+y) (2) is equivalent to one of the form kxy (mod x+y) with k = B-A-C, so I've adopted the more general case. The main questions that have been discussed are (1) Do there exist solution cycles of length n for every integer n? (2) For which values of the parameter k is a divergent sequence possible? (3) Do there exist any "primitive" solution cycles other than {5,7,11}, {7,5,11}, and {23,61,59,119,79,95}? Regarding question (1) David suggested a method for constructing cycles of any finite length using the Chinese Remainder Theorem. Suppose the integers {A,B,C,D,E} constitute a solution cycle, and let x denote the greatest common divisor (gcd) of A and B. If we put a=A/x and b=B/x then by definition abx^2 = C (mod ax+bx). Clearly x must divide C, so we have that gcd(A,B) divides gcd(B,C). Similarly, gcd(B,C) divides gcd(C,D) and so on around the loop. Thus, each pair of consecutive elements in a solution cycle has the same gcd, which we will call x. This shows that every solution cycle of length 5 is of the form {ax,bx,cx,dx,ex} where the integers a,b,c,d,e are coprime in consecutive pairs. (They need not all be mutually coprime.) We can cancel x out of each congruence of the form abx^2 = cx (mod ax+bx) to give the system of linear congruences (ab)x = c (mod a+b) (bc)x = d (mod b+c) (cd)x = e (mod c+d) (de)x = a (mod d+e) (ea)x = b (mod e+a) Since a and b are coprime, it follows that ab is coprime to a+b, etc, so we can certainly solve each individual congruence for x. Furthermore, if the sums (a+b), (b+c), (c+d), (d+e) and (e+a) are mutually coprime, then the Chinese Remainder theorem ensures infinitely many simultaneous solutions of the form x=Mj+Q, where M is the product of the moduli. So, to generate a solution cycle of length 5 (for example), choose a set of mutually coprime moduli m1,m2,m3,m4,m5 (where m1=(a+b), etc) from which the corresponding values of a,b,c,d,e can be computed from the formulas a = (m1-m2+m3-m4+m5)/2 b = (m2-m3+m4-m5+m1)/2 c = (m3-m4+m5-m1+m2)/2 d = (m4-m5+m1-m2+m3)/2 e = (m5-m1+m2-m3+m4)/2 Assuming the resulting values of a,b,c,d,e are coprime in consecutive pairs (including e,a), we are assured of a solution (infinitely many, in fact) using the CRT. This method relies on the proposition that for any given integer n we can construct a cycle of integers a,b,c,d... that are coprime in consecutive pairs and such that all the sums mi of consecutive terms are coprime. Here's a proof that this can in fact always be done. The first step is the most interesting: For any odd n select n distinct odd primes p1<p2<...<pn such that pn/p1 < (n+1)/(n-1). Define the "sums" of the cycle as s1=2p1, s2=2p2, ..., sn=2pn. The actual terms of the root cycle are then v1 = p1 - p2 + p3 - ... + pn v2 = p2 - p3 + p4 - ... + p1 v3 = p3 - p4 + p5 - ... + p2 etc Clearly each v is odd and coprime to its immediate neighbors. Now we set up the system of congruences v1 v2 x = v3 (mod 2p1) v2 v3 x = v4 (mod 2p2) etc. Recall that, by the CRT, if gcd(c,d)=1 then any congruence of the form x = a (mod cd) is equivalent to the pair of congruences x = a (mod c) and x = a (mod d). Therefore, since all the v are odd, each of the above congruences can be split into two, one of which is simply x=1 (mod 2). Thus, we need an odd solution of the system v1 v2 x = v3 (mod p1) v2 v3 x = v4 (mod p2) etc. and we are assured of such a solution by the CRT. (Note that the system solution is of the form x = Mk+U where M=p1*p2*..*pn and k is any integer. Since M is odd, we can find an odd x for any U.) Notice that the above construction relies on the fact that for any positive integer n there exists an increasing sequence of n primes p1, p2, ..., pn such that pn/p1 is less than (n+1)/(n-1). To prove this, consider the sequence of real numbers [(n+1)/(n-1)]^k for k = 0,1,2,... These values partition the real number line into segments, for each of which the ratio of largest to smallest values is (n+1)/(n-1). If the kth segment contains fewer than n primes, then the sum of the reciprocals of the primes in that segment is less than n[(n-1)/(n+1)]^k. It follows that the sum of the reciprocals of all the primes is less than n times the geometric sum of [(n-1)/(n+1)]^k for k=0,1,2,..., which converges. This contradicts the fact that the sum of the reciprocals of the primes diverges. Hence, there must be segments containing n or more primes. So this completes the answer to question (1), proving that there exist solution cycles of length n for every positive integer n. Just for fun I checked to find the first occurrance of prime sets that satisfy the requirements of the proof for each n. Here's what I found n p1 ln(p1)/ln(n) --- ---- ------------ 2 2 1.0000 3 7 1.7712 4 19 2.1239 5 29 2.0922 6 53 2.2158 7 83 2.2708 8 127 2.3295 9 163 2.3182 10 223 2.3483 20 1181 2.3613 30 3163 2.3695 100 49169 2.3458 If p1(n) denotes the minimum p1 for a set satisfying the condition, then it appears p1(n) = n^c where c is about 2.3.... So the interesting question that arises out of all this is: What bounds can be placed on the exponent c in the equation p1(n)=n^c ? I suspect a certain tolerance would be equivalent to the Riemann Hypothesis. The max value seems to occur at n=17 where c=2.403... For the range of n values from 60 to 100 I find 2.3301 < c < 2.3682. Question (2) concerns the possibility that the terms of a solution sequence increase without limit. Here a suggestion from Peter Brown led to consideration of arithmetic solution sequences, i.e., sequences with terms of the form x[n]=sn+q for constants s and q. It turns out that a sequence based on f(x,y) = kxy (mod x+y) has a solution of the form x[n] = sn+q if and only if sk = -6 and qk is even. For example, with k=1 we have descending solution sequences of the form x[n] = -6n + u, where u = 0, 2, or 4. On the other hand, the recurrence based on f(x,y) = x^2 + y^2 (mod x+y), which is equivalent to f(x,y)=-2xy (mod x+y), has increasing (divergent) solution sequences of the form x[n] = 3n + u, where u = 0, 1, or 2. The answer to Question (3) turns out to be 'yes' by the brute force search method. I found two more primitive cycles (1271 3727 1343 3911) (3527 4769 8259 5879 4271) and David Einstein also found these two plus another (11791 16057 15603 17383) Notice that the Chinese Remainder method of generating solution cycles tends to give cycles with very large common factors, roughly in proportion to the product of all the sums of the coprime parts of each pair of consecutive terms. In contrast, consider the primitive solution cycle {23,61,59,119,79,95} This corresponds to the set of moduli 84 120 178 198 174 118 Since this cycle has an even period the moduli taken with alternating signs must sum to zero, so there are just 5 degrees of freedom. However, given these six moduli we have a free choice of one of the individual terms. Choosing 23 for the first term we get the system of congruences (23)(61)x = 59 (mod 84) (61)(59)x = 119 (mod 120) (59)(119)x = 79 (mod 178) (119)(79)x = 95 (mod 198) (79)(95)x = 23 (mod 174) (95)(23)x = 61 (mod 118) which happens to have the solution x=1. (Of course there are really infinitely many solutions x = 4221173880j + 1 for any integer j.) I suppose there are primitive cycles of length n for every positive integer n, but I don't know how to prove it. Interestingly, there do not seem to be any more primitive cycles of length 3 besides {5,7,11}. (See the article A Knot of Congruences and Problem #3 on the Most Wanted List.) Is the number of primitive solutions of length n finite?

Return to MathPages Main Menu