Newsgroups: sci.math,sci.math.research From: randall@coyote.csusm.edu (Randall Rathbun) Subject: Non-recursive series solution needed Date: Wed, 12 Apr 1995 02:07:22 GMT Keywords: Solution, non-recursive series Topic: Finding a direct non-recursive formula for a series: Can anyone find a direct, non-recursive algorithm for the series listed below? This will help crack a companion series, both of which create Heron triangles with two rational medians. T Series level term 0 1 1 1 2 2 3 3 4 5 5 11 6 37 7 83 8 274 9 1217 10 6161 11 22833 12 165713 13 1249441 14 9434290 15 68570323 16 1013908933 17 11548470571 18 142844426789 19 2279343327171 20 57760865728994 21 979023970244321 22 etc.... T(i-1)*T(i-4)+T(i-2)*T(i-3) T(i) = --------------------------- T(i-5) T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 Thanks for any help! Please email at randall@coyote.csusm.edu or ralph@defcen.gov.au NOTE: The smallest Heron triangle with two rational medians is 73 51 26 with area 420 and medians 35/2 97/2. - Randall [Mod. note: This either is or is close to a Somos sequence, described by David Gale in the Intelligencer. - Greg] ============================================================================== Newsgroups: sci.math,sci.math.research From: kevin2003@delphi.com (Kevin Brown) Subject: Re: Non-recursive series solution needed Date: Fri, 14 Apr 1995 20:26:47 GMT RR = Randall Rathbun RR> RR> T(i-1)*T(i-4)+T(i-2)*T(i-3) RR> T(i) = --------------------------- RR> T(i-5) RR> RR> T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 VB = Vincent Broman VB> While I haven't checked the initial conditions on this, here are VB> suggestions for semi-general solutions. VB> T(n) = a*r^n + b*s^n VB> solves the general equation for any a and b... Otherwise, I'd VB> also try solutions like a*r^n*sin(c*n) + b*s^n*cos(c*n). The magnitude of T(n) seems to increase faster than geometrically, so I think it can't be expressed in either of those forms. If you define the ratio sequence s(n) = T(n+2)/T(n) then you have s3/s0 = s2/s1 + 1, which gives an interesting sequence that oscillates somewhat but seems to grow geometrically. If we define s(n+1) T(n+3) T(n) q(n) = -------- = -------------- s(n) T(n+1) T(n+2) then the values of q(n) seem to exhibit a rough seven-step cycle with the approximate asymptotic values 0.84988 1.67051 1.88098 0.91686 1.11147 2.07966 1.30297 (These seven values also seem to oscillate slightly.) Notice that T(2k+1) -------- = q(0) q(2) q(4) ... q(2(k-1)) T(2k) so the ratio of consecutive T values increases indefinitely. (The ratios T(2k)/T(2k-1) are given by 2 q(1) q(3)...q(2k-3).) The geometric mean of the q values seems to be around 4/3, so a very rough estimate of T(m)/T(m-1) would be (4/3)^(m/2). Then an even rougher estimate of T(m) would be (4/3)^(m(m+1)/4). Let's see, for m=20 this gives about (1.3)10^13, which is at least in the ballpark with the true value of (5.7)10^13. With some refinements this could probably be improved. ============================================================================== Newsgroups: sci.math,sci.math.research From: dsavitt@unixg.ubc.ca (David Savitt) Subject: Re: Non-recursive series solution needed Date: Fri, 14 Apr 1995 23:26:46 GMT In article <9504141620591.kevin2003.DLITE@delphi.com>, Kevin Brown wrote: > > T(i-1)*T(i-4)+T(i-2)*T(i-3) > T(i) = --------------------------- > T(i-5) > > T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 Nothing nontrivial of the form T(i)=r^i will satisfy the recursion relation--inserting r^i for T(i), the RHS becomes 2*r^i. However, if c is any root of x^12-x^4-1=0 and a,b are any constants, T(i)=c^(i^2+a*i+b) does satisfy the recurrence. >If you define >the ratio sequence s(n) = T(n+2)/T(n) then you have s3/s0 = s2/s1 + 1. >If we define q(n)=s(n+1)/s(n) >then the values of q(n) seem to exhibit a rough seven-step cycle >with the approximate asymptotic values > The geometric mean of the q values seems to be around 4/3. The q(i) satisfy the recurrence relation q(i-1)q(i+1)=1+1/q(i), so if the q(i) were to tend to a limit k, k would satsify k^2=1+1/k, or k^3-k-1=0. One such value of k is around 1.32..., which I suppose is where the 4/3 comes from. > Then an even rougher estimate of T(m) would be (4/3)^(m(m+1)/4). Replacing 4/3 by the k above, k^(1/4) is the c introduced before, i.e. the rough estimate of T(m) is c^(m^2+m). Also, notice that the q(i) will satisfy the (terminating) continued fraction 1/q(i)=q(i-2)/(1+q(i-3)/(1+q(i-4)/(...+q(2)/(1+q(1)/(3/2))...) -Dave -- ------------------------------------------------------------------------------ Dave Savitt | 3rd year mathematics | AKA Little Dave | Go Canucks! dsavitt@unixg.ubc.ca | University of B.C. | AKA Goliath | Go Grizzlies! --- "I am not a crook" - Richard Nixon ----- "I am not your cook" - my mom --- ============================================================================== Date: Wed, 19 Apr 95 13:00:22 CDT From: rusin (Dave Rusin) To: randall@coyote.csusm.edu Subject: Re: Non-recursive series solution needed Newsgroups: sci.math,sci.math.research In article <3mfckq$u1b@coyote.csusm.edu> you write: >Can anyone find a direct, non-recursive algorithm for the series >listed below? This will help crack a companion series, both of >which create Heron triangles with two rational medians. OK, I give up. I can see that Heron triangles with two rational medians correspond to solutions of a set of diophantine equations of the form Ax^2+By^2+C=square Dx^2+Ey^2+F=square a quadratic in x^2 and y^2 = square But how do you get a parametric family of solutions out of this? I'm used to elliptic curves, searching for (e.g.) perfect squares S making S-a and S-b also squares; but this looks more like a surface, and there I'm at the limit of my algebraic geometry. Can you summarize the creation of your sequence? Provide backgroupnd references? (Evidently I didn't key in the right things to the Math Reviews CDROM) thanks dave ============================================================================== Date: Thu, 20 Apr 1995 19:39:15 -0700 From: randall@coyote.csusm.edu (Randall Rathbun) To: randall@coyote.csusm.edu, rusin@math.niu.edu Subject: Re: Non-recursive series solution needed Cc: ralph@defcen.gov.au, randall@coyote.csusm.edu Dave: Here's a quick note... Ralph and I are doing real time work on this problem. As far as I know, this is original, Ralph did his doctoral thesis on this (plus more) We define the S & T series from our recursive relationship (1) X[i-4]*x[i-1]+x[i-3]*x[i-2] (1) X[i] = --------------------------- x[i-5] and the first five terms to initialize the series: The first T series is what I posted to the net. T series: 1 1 2 1 3 2 4 3 5 5 6 11 7 37 8 83 9 274 10 1217 11 6161 12 22833 13 165713 14 1249441 15 9434290 16 68570323 17 1013908933 18 11548470571 19 142844426789 20 2279343327171 21 57760865728994 22 979023970244321 23 23510036246274433 24 771025645214210753 25 29636604976524724225 etc ... The second is similar, called the S series: S series: 1 1 2 1 3 -1 4 1 5 -7 6 -8 7 1 8 -57 9 391 10 455 11 2729 12 22352 13 -175111 14 -47767 15 -8888873 16 -69739671 17 565353361 18 -3385862936 19 195345149609 20 1747973613295 21 -4686154246801 22 632038062613231 23 -34045765616463119 24 -319807929289790304 25 -11453004955077020783 etc ... Taking absolute values of the S series: (and using the formuli below) a[i]=s[i+3]*t[i+3]*(s[i]^2*t[i+1]^2*t[i+2]^4+s[i+1]^2*s[i+2]^4*t[i]^2) b[i]=s[i+2]*t[i+2]*(s[i+1]^2*s[i+2]^2*t[i+1]^2*t[i+2]^2+s[i]^2*s[i+3]^2*t[i]^2*t[i+3]^2) c[i]=s[i+1]*t[i+1]*(4^(mod(i,2)*s[i]^2*s[i+2]^4*t[i+3]^2+4^(mod(i+1,2)*s[i+3]^2*t[i]^2*t[i+2]^4) k=gcd(a[i],b[i],c[i]) sides = a[i]/k b[i]/k c[i]/k We can obtain rational Heron Triangles with two rational medians: First few examples: Sides: 51 26 73 Area: 420 Medians: 97/2 61.6116872030... 35/2 Sides: 875 291 626 Area: 55440 Medians: 433/2 746.71296359444... 572 Sides: 13816 15155 28779 Area: 23931600 Medians: 21937 21263.5331553813... 3589/2 Sides: 185629 1930456 1823675 Area: 142334216640 Medians: 3751059/2 865135.3787986016... 2048523/2 Sides: 2396426547 46263061 2442655864 Area: 2137147184560080 Medians: 2488886435/2 2419541044.2575038950... 1175099279 Sides: 356388643246 336426334971 31982445133 Area: 4323341954766548553840 Medians: 159215456444 189003177751.5926688483... 692364218455/2 I hope this answers your question. If you have any more, please feel free to ask. - Randall Rathbun (with Ralph Buchholz) ============================================================================== Newsgroups: sci.math,sci.math.research From: pmontgom@cwi.nl (Peter L. Montgomery) Subject: Re: Non-recursive series solution needed Date: Thu, 20 Apr 1995 07:43:48 GMT >RR = Randall Rathbun >RR> >RR> T(i-1)*T(i-4)+T(i-2)*T(i-3) >RR> T(i) = --------------------------- >RR> T(i-5) >RR> >RR> T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 > I didn't find an explit formula for T(n), but I have several observations (long); . If we try to extend the sequence backwards, we get T[1] = T[-2] = T[-3] = 1, T[-4] = 2, T[-5] = 3. In general T[-2 - n] = T[n]. . Define s[n] = T[n-1]. Then s[-2] = s[-1] = s[0] = s[1] = s[2] = 1, s[n] * s[n-5] = s[n-1] * s[n-4] + s[n-2] * s[n-3], s[-n] = s[n]. The last condition (symmetry) suggests it may be simpler to find a general formula for s[n] than for T[n]. . The s sequence appears to satisfy s[n]^2 + s[n-2] * s[n+2] = 3 s[n-1] * s[n+1] (n odd) s[n]^2 + s[n-2] * s[n+2] = 2 s[n-1] * s[n+1] (n even) (For the T sequence, reverse "odd" and "even".) If we find a general formula for s[n], we will need to distinguish odd and even n. Of course this can be hidden, if we reference (-1)^n or cos(pi * n). . Numerical data suggest the sequence is periodic modulo primes and prime powers. For example, the pattern modulo 16 seems to be n mod 12 0 1 2 3 4 5 6 7 8 9 10 11 s[n] mod 16 1 1 1 2 3 5 11 5 3 2 1 1 There seem to be many patterns like s[n+10] == 3 * 3^n * s[n] (mod 5) and s[5] == 0 (mod 5) s[n+12] == - (-1)^n * s[n] (mod 7) s[n+12] == 8 * 8^n * s[n] (mod 11) and s[6] == 0 (mod 11) s[n+14] == 25 * 16^n * s[n] (mod 37) and s[7] == 0 (mod 37) . The value of s[n] seems to be very close to r^(n^2), where r ~= 1.07425451486467 . The constant r^4 ~= 1.3317685368462 compares to (4/3) suggested by Kevin Brown and to 1.3247... (root of x^3 = x + 1) suggested by David Savitt. . When n is even, s[n+1] * s[n-1] - s[n]^2 is a perfect square. When n is odd, this is the product of the neighboring square roots (up to sign): n s[n] s[n+1]*s[n-1] - s[n]^2 u[n] v[n] = u[n]/s[n] 0 1 0 0 0 1 1 0 1 1 2 1 1 -1 -1 3 2 -1 -8 -4 4 3 1 57 19 5 5 8 = 1 * 8 455 91 6 11 64 = 8 * 8 -22352 -2032 7 37 -456 = -8 * 57 -47797 -1291 8 83 3249 = 57 * 57 69739671 840237 9 274 25935 = 57 * 455 -3385862936 -12357164 10 1217 207025 = 455 * 455 -1747973613295 -1436297135 The u[n] sequence has the square roots, with the signs chosen to preserve the pattern in the third column. Some likely (but unproved) identities are s[2n]^2 = u[n]^2 - u[n-1] * u[n+1] s[2n-1] * s[2n+1] = 2 u[n]^2 - u[n-1] * u[n+1] s[2n-2] * s[2n+2] = 3 u[n]^2 - u[n-1] * u[n+1] s[2n-3] * s[2n+3] = 5 u[n]^2 - 4 u[n-1] * u[n+1] s[2n-4] * s[2n+4] = 11 u[n]^2 - 9 u[n-1] * u[n+1] s[2n-5] * s[2n+5] = 74 u[n]^2 - 25 u[n-1] * u[n+1] s[2n+1]^2 = -4 u[n] * u[n+1] + u[n-1] * u[n+2] s[2n ] * s[2n+2] = -3 u[n] * u[n+1] + u[n-1] * u[n+2] s[2n-1] * s[2n+3] = -5 u[n] * u[n+1] + 2 u[n-1] * u[n+2] s[2n-2] * s[2n+4] = -11 u[n] * u[n+1] + 3 u[n-1] * u[n+2] s[2n-3] * s[2n+5] = -37 u[n] * u[n+1] + 10 u[n+1] * u[n+2] If these patterns are correct, then the coefficients can be found by (separately) setting n = 0 and n = 1, since u[0] = 0. s[2n+j] * s[2n-j] = s[j+2] * s[j-2] * u[n]^2 - s[j]^2 * u[n-1] * u[n+1] s[2n+1+j] * s[2n+1-j] = - s[j+3] * s[j-3] * u[n] * u[n+1] + s[j+1] * s[j-1] * u[n-1] * u[n+2] Now setting n = 2 gives s[j+4] * s[j-4] = s[j+2] * s[j-2] + 8 s[j]^2 s[j+5] * s[j-5] = -8 s[j+3] * s[j-3] + 57 s[j+1] * s[j-1] These recurrences reference only even subscripts (or only odd subscripts) in s, and (if correct) may be easier to manipulate. Also, s[2n-1] * s[2n+3] - s[2n+1]^2 = u[n-1] * u[n+2] - u[n] * u[n+1] appears to be a perfect square, but I see no pattern for its square root. For n = 0, 1, 2, 3, 4, it is 1, 1, 7^2, 1, 391^2, respectively. I do note -391 = 3249 - 3640 = u[4]^2 + u[3] * u[5]. If this conjecture is correct, then s[n] will always be a sum of two squares when n is odd. s[1] = 1 = 1^2 + 0^2 s[3] = 2 = 1^2 + 1^2 s[5] = 5 = 2^2 + 1^2 s[7] = 37 = 6^2 + 1^2 s[9] = 274 = 15^2 + 7^2 s[11] = 6161 = 56^2 + 55^2 = 65^2 + 44^2 s[13] = 165713 = 407^2 + 8^2 s[15] = 9434290 = 3071^2 + 57^2 (and other ways) s[17] = 1013908933 = 22742^2 + 22287^2 (and other ways) s[2n+1] = (s[n]*s[n+1])^2 + (another square) The apparent identity u[n]^2 - s[2n]^2 = u[n-1] * u[n+1] may let us write u[n] as a product of two other sequences, by looking at expressions like GCD(u[n] + s[2n], u[n-1]). I have not investigated this. If we define v[n] = u[n]/s[n], then v[n] appears to be an integer (see the earlier observation about patterns modulo 5, 11, 37). The v[n] sequence seems to be periodic modulo small primes, but with long periods: Mod 2, period 3: 0, 1, 1 Mod 3, period 16: 0, 1, 2, 2, 1, 1, 2, 2, 0, 1, 1, 2, 2, 1, 1, 2 Mod 4, period 12: 0, 1, 3, 0, 3, 3, 0, 1, 1, 0, 1, 3 v[n+3] == (-1)^n v[n] mod 4 Mod 5, period 40: 0, 1, 4, 1, 4, 1, 3, 4, 2, 1, 0, 1, 3, 4, 2, 1, 1, 1, 1, 1, 0, 4, 4, 4, 4, 4, 3, 1, 2, 4, 0, 4, 3, 1, 2, 4, 1, 4, 1, 4 v[n+10] == 2^(n-1) v[n] (mod 5) Mod 7, period 20: 0, 1, 6, 3, 5, 0, 5, 4, 6, 6, 0, 1, 1, 3, 2, 0, 2, 4, 1, 6 Mod 11, period 120 Mod 13, period 40: 0, 1, 12, 9, 6, 0, 9, 9, 8, 12, 0, 12, 5, 9, 4, 0, 7, 9, 1, 1, 0, 12, 12, 4, 6, 0, 9, 4, 8, 1, 0, 1, 5, 4, 4, 0, 7, 4, 1, 12 v[5n+6] == +- 4^(n+1) v[5n+1] (mod 13) Mod 17, period 288 Mod 19, period 16: 0, 1, 18, 15, 0, 15, 1, 1, 0, 18, 18, 4, 0, 4, 1, 18 In order to continue these periodic patterns to negative n, we should define v[-n] = -v[n] and u[-n] = -u[n] (i.e., use the other square root there). -- Peter L. Montgomery pmontgom@cwi.nl San Rafael, California Mathematically gifted, unemployed, U.S. citizen. Interested in computer architecture, program optimization, computer arithmetic, cryptography, compilers, computational mathematics. 17 years industrial experience. ============================================================================== Date: Fri, 21 Apr 95 14:11:35 CDT From: rusin (Dave Rusin) To: pmontgom@cwi.nl Subject: Re: Non-recursive series solution needed Newsgroups: sci.math,sci.math.research In article you write: >I didn't find an explit formula for T(n), but I have >several observations (long); These were great! I haven't had time to read through it all, but I'm glad you had a chance to play with this. I have a sneaking suspicion that the solutions are related to points on an elliptic curve, a connection I have pursued rather than tackling the numbers directly. Part of what made me think this was that in your paper some time ago (in re speeding up factorization programs I think) you noted that some sort of similar recurrence occurs for the homogeneous coordinates of the points on an elliptic curve: if nP+Q = (x[n]: y[n]: z[n]), then there's some sort of product preserved (like x[n+1]y[n-1]-x[n-1]y[n+1] or something?) I looked again when this problem was posted, and didn't see in your paper what I thought I remembered, but perhaps this is more familiar to you. If I'm right, that these T[n] are related to points on curves, that would seem to prevent an easy formula for the T[n] Certainly no genus-1 curve admits a rational parameterization, but even if the T[n] are one step removed from that, it seems that an 'easy' formula for T[n] would let you compute high powers in elliptic curves over a finite field, and thus let you factor easily. So on philosophical grounds I rejected the possibility that T[n] would have a nice formula. Finally, the poster's first article suggested the sequence had something to do with rational Heron triangles; examples like Tunnell's work on congruent numbers suggested to me that elliptic curves may well have been at the root of the problem which generated the T[n] in the first place. I wrote the poster for more details yesterday; no response yet. I'll be looking at your post in detail over the weekend but if these comments should happen to make you think of a more concrete connection with elliptic curves, I'd like to hear of it. dave ============================================================================== Date: Fri, 21 Apr 1995 21:46:17 +0200 From: Peter-Lawrence.Montgomery@cwi.nl To: rusin@math.niu.edu (Dave Rusin) Subject: Re: Non-recursive series solution needed Glad you like it. There is at least one typo (besides the obvious "explit" -> "explicit"). u[7] should by -47767 rather than -47797. I have noticed a partial doubling formula: s[8] = 83 = 3^4 + 2*1^4 s[12] = 22833 = 11^4 + 2*8^4 s[16] = 68570323 = 83^4 + 2*57^4 suggesting s[4n] = s[2n]^4 + 2*u[n]^4 Meanwhile u[2n] seems to be divisible by u[n]*s[2n], but I have been unable to express the quotient in terms of u[n] and s[2n]. If we find such a recursion, then we can quickly compute s[2^n] and u[2^(n-1)] for moderate n to hundreds of decimal places, and estimate limit s[n]^(1/n^2) to high precision. No, I didn't use elliptic curves to derive the stuff in my posting. But some of the polynomials associated with elliptic curves have degrees which grow quadratically; perhaps the solution can be expressed in terms of those polynomials. ============================================================================== Newsgroups: sci.math,sci.math.research From: kevin2003@delphi.com (Kevin Brown) Date: Sun, 23 Apr 1995 21:39:44 GMT Subject: Re: Non-recursive series solution needed RR = Randall Rathbun RR> RR> T(i-1)*T(i-4)+T(i-2)*T(i-3) RR> T(i) = --------------------------- RR> T(i-5) RR> RR> T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 Define the sequence s(n) as follows T(n) T(n+3) s(n) = -------------- T(n+1) T(n+2) The first several values of s(n) are tabulated below (read by rows): 1.50000 0.83333 1.46667 2.01818 1.01966 0.98144 1.97999 1.53352 0.83440 1.43362 2.03445 1.04040 0.96398 1.95826 1.56711 0.83652 1.40094 2.04873 1.06222 0.94762 1.93489 1.60066 0.83971 1.36874 2.06095 1.08509 0.93237 1.91000 1.63407 0.84396 1.33709 2.07106 1.10901 0.91823 1.88370 1.66720 0.84929 1.30606 2.07899 1.13395 0.90519 1.85612 1.69994 0.85569 1.27573 2.08472 1.15987 0.89324 1.82737 1.73215 0.86316 1.24615 2.08821 1.18675 0.88240 1.79757 1.76373 0.87172 1.21740 2.08946 1.21455 0.87264 1.76686 1.79452 0.88137 1.18951 2.08844 1.24322 0.86398 1.73536 1.82441 0.89210 1.16254 2.08517 1.27271 0.85639 1.70320 1.85328 0.90393 1.13651 2.07967 1.30297 0.84988 1.67051 etc Remarkably, each of these seven columns is just a phase-shifted version of a single function f(m). The function f appears to be a very pure harmonic function that oscillates between the values of 0.833 and 2.089 with period near 124. The function f(m) seems to match very closely to the form f(m) = A - B sqrt( C - sin(m/k) ) Essentially it's a sine wave, but the peaks are a bit narrower than the valleys. It's more convenient to shift the indicies by taking the initial values T(0)=T(1)=T(2)=T(3)=1 and T(4)=2. Then the first few values of s(n) are 1 2 3/2 5/6 22/15 111/55 415/407 etc The values of the T sequence with even indicies can be expressed in terms of the s(n) values as T(4) = [(1)(2)] T(6) = [(1)(2)]^2 [(3/2)(5/6)] T(8) = [(1)(2)]^3 [(3/2)(5/6)]^2 [(22/15)(111/55)] etc and with odd indicies T(5) = [(2)(3/2)] T(7) = [(2)(3/2)]^2 [(5/6)(22/15)] T(9) = [(2)(3/2)]^3 [(5/6)(22/15)]^2 [(111/55)(415/407)] etc (Each of the bracketed terms reduces to the form T(k)T(k+4)/(T(k+2)^2), which can be used to prove that all the T values are integers.) In general, we have m-1 T(2m) = PROD [s(2k)s(2k+1)]^(m-1-k) k=0 m-1 T(2m+1) = PROD [s(2k+1)s(2k+2)]^(m-1-k) k=0 Substituting for each s(n) the appropriate expression in terms of the period function f(n), we have a product of many terms of the form A + B sqrt(C-sin(jn)). Expanding this product will result in a series, and it might be possible to collect powers of the trig function and sum the series. This would be more promising if there was a simpler trig expression for f(n) than the one I have postulated. ============================================================================== Newsgroups: sci.math,sci.math.research From: elkies@ramanujan.math.harvard.edu (Noam Elkies) Subject: 1,2,3,5,11,37,...: Non-recursive solution found Date: Wed, 26 Apr 1995 17:59:25 GMT Summary: Closed form in terms of elliptic theta functions Keywords: Somos recurrence, elliptic theta functions Randall Rathbun: > T(i-1)*T(i-4)+T(i-2)*T(i-3) > T(i) = --------------------------- > T(i-5) > > T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 Two versions of a closed form are given below, together with consequences for the asymptotics of the T(i). First, some preliminary observations: We can extend the functional equation to negative i, finding the sequence ..., 11, 5, 3, 2, 1, 1, 1, 1, 1, 2, 3, 5, 11, ... the symmetry suggests renumbering the T's so that the central 1 is the zeroth. Numerical experiments show that the functional equation has analogs expressing T(i+k+1)T(i-k) as a linear combination of T(i)T(i+1) and T(i-1)T(i+2) for all k. We might hope for a similar equation expressing T(i+k)T(i-k) in terms of T(i)^2 and T(i+1)T(i-1). We don't quite find that; for instance if k=2 then T(i)^2 + T(i-2)T(i+2) is either twice or three times T(i-1)T(i+1) depending on the parity of i. But we can fix this, without losing either the symmetry or the T(i+k+1)T(i-k) identity, by replacing every other T(i) by r*T(i) for a suitable constant r. Indeed let r be the 4th root of 2/3, and define c(-i) = c(i) = T(i-1) if i is even, r*T(i-1) if i is odd, so for i=0,1,2,3,... c(i) is 1,r,1,2r,3,2r,5,11r,... . These satisfy the recurrence c(i-2) c(i+2) = sqrt(6) * c(i)^2 - c(i-1) c(i+1). This looks like a Somos recurrence on sequences of elliptic theta functions (presumably Michael Somos hasn't seen this thread yet, or he would have remarked on this some time back). Indeed let q = 0.02208942811097933557356088... z = 0.1141942041600238048921321... b = 0.9576898995913810138013844... u = 0.7889128685374661530379575... then c(i) = b * u^(n^2) * [sum from n=-infty to + infty of (q^(n^2)*z^(i*n)]. (These values of q,z,b,u were obtained numerically from the condition that the formula for c(i) hold for the initial values i=0,1,2,3.) It follows that c(i) = f(i)*C^(i^2) where C = u * exp(log^2(z) / 4 log(q)) = 1.074254514864672463110626... and f(i) is a quasiperiodic function with the single irrational period 2 log(q) / log(z) = 3.51420405240870236831... which is bounded away from zero; this gives the asymptotic behavior of c(i), and thus also of T(i) though the T's also have a period of 2 due to the factors of r. The continued fraction of the period starts 3, 1, 1, 17, 9, 1, 15, 2, 7, 2, 7, 1, 1, ... and yields the good rational approximations 7/2 (whence the apparent period-7 behavior noted by Kevin Brown ), 123/35 (explaining the oscillation "with period near 124" observed by Kevin), and 1237/352. The numbers T(i-1) can also be obtained "arithmetically" from the elliptic curve C/q^(2Z) associated to our theta functions. Wasting some more time on gp, I found that we're dealing with the elliptic curve E: y^2 + xy + y = x^3 - 2x (#102-A1(E) in Cremona's table) which has [a rational 2-torsion point at (0,0) and] a rational point P: (x,y) = (2,2) of infinite order. For i=0,1,2,3,... the x-coordinate of the i-th multiple of P on E in lowest terms is 1/0 [sic], 2/1, 1/1, 8/1, 9/1, 50/49, 121/64, 2738, 6889/3249, ... , with numerators 1, 2, 1, 2*2^2, 3^2, 2*5^2, 11^2, 2*37^2, 83^2, ... ! Indeed the numerator of i*P is always T(i-1)^2 or 2*T(i-1)^2 according as i is even or odd, and the canonical height of P on E is log(C) = 0.0716269464704400357381372... Note that 7P is an integral point with large (x,y), so very close to the origin (inf,inf) of E(R); this reflects the fact that z^7 is close to a power of q^2 (namely q^4), which is also what was responsible for the nearly 7-periodic behavior of T(i). --Noam D. Elkies (elkies@ramanujan.harvard.edu) Dept. of Mathematics, Harvard University ============================================================================== From: Noam Elkies Date: Thu, 27 Apr 1995 11:06:36 -0400 To: rusin@math.niu.edu Subject: Re: 1,2,3,5,11,37,...: Non-recursive solution found >Everyone seems to be forgetting that the original poster's >interest was in Heron triangles with two rational medians, I certainly had forgotten that... >which sounds suspiciously like the congruent number problem I doubt it, since such triangles are parametrized by a surface, not a curve as happens for congruent numbers (though that elliptic curve of conductor 102 might lie on the surface). >solved by Tunnell. Not quite -- Tunnell's characterization of congruent numbers is still contingent on part of the conjecture of Birch and Swinnerton Dyer. --Noam D. Elkies (elkies@math.harvard.edu) Dept. of Mathematics, Harvard University ============================================================================== From: Noam Elkies Date: Thu, 27 Apr 1995 16:24:08 -0400 To: rusin@math.niu.edu Subject: Re: 1,2,3,5,11,37,...: Non-recursive solution found Oops -- I did indeed mistranslate the coordinates [1,1,0,-2,0]. To compute this, I first computed the j-invariant of C/(q^2Z) (it's subst(trunc(jell(x)),x,q^2) in GP), expanding in a continued fraction to recognize it as a rational number, and using pointell to compute the x-coordinate of the point corresponding to z, which also yields the correct quadratic twist. NDE ============================================================================== Newsgroups: sci.math,sci.math.research From: elkies@ramanujan.math.harvard.edu (Noam Elkies) Subject: Correction Re: 1,2,3,5,11,37,... Date: Fri, 28 Apr 1995 02:45:28 GMT Summary: Wrong equation for elliptic curve Keywords: Somos recurrence, elliptic theta functions In article <3nm1lt$ifu@decaxp.harvard.edu> I wrote: >[....] >The numbers T(i-1) can also be obtained "arithmetically" from the >elliptic curve C/q^(2Z) associated to our theta functions. Wasting >some more time on gp, I found that we're dealing with the elliptic curve >E: y^2 + xy + y = x^3 - 2x (#102-A1(E) in Cremona's table) >which has [a rational 2-torsion point at (0,0) and] a rational point >P: (x,y) = (2,2) >[...] As Dave Rusin (rusin@math.niu.edu) points out, I transposed two coefficients of the elliptic curve; the curve with the above equation does not even contain the point (2,2). The correct equation is E: y^2 + xy = x^3 + x^2 - 2x. This was obtained by 1) computing the j-invariant j(E)=j(q^2) as a real number, 2) using its continued fraction to recognize j(E) as the rational number 11^6/612, 3) computing the x-coordinate of the point z on the curve C*/q^(2Z), which determines the correct quadratic twist, and 4) reducing to standard minimal form, and 5) looking up the resulting curve in Cremona's tables. --Noam D. Elkies (elkies@ramanujan.harvard.edu) Dept. of Mathematics, Harvard University ============================================================================== Newsgroups: sci.math,sci.math.research From: kevin2003@delphi.com (Kevin Brown) Subject: Re: 1,2,3,5,11,37,...: Non-recursive sol Date: Fri, 28 Apr 1995 06:26:38 GMT Randall Rathbun: > T(i-1)*T(i-4)+T(i-2)*T(i-3) > T(i) = --------------------------- > T(i-5) > > T(0) = 1 T(1) = 1 T(2) = 2 T(3) = 3 T(4) = 5 This sequence (formed by the convolution of successive terms) reminds me of the sequence of coefficients for the power series solution of the equation x x'' + a (x')^2 = b (1) Among the solutions of this equation (with appropriate choices of a,b) are exp(t), sin(t), cos(t), (A+Bt)^n, A+Bt+Ct^2, and sqrt(A+Bt+Ct^2). This last function represents the separation between any two objects in unaccelerated motion. Other solutions include the cycloid relation for (non-rotating) gravitational free-fall, and the radial distance of a mass from a central point about which it revolves with constant angular velocity and radial freedom. The power series solution of equation (1) can be written x(t) = c[0] + c[1] t + c[2] t^2 + c[3] t^3 + ... where the coefficients c[i] satisfy the convolutions n / b if n = 2 SUM A(k,n-k) c[k] c[n-k] = ( k=0 \ 0 if n > 2 with A(k,j) = (a-1) j (k-j) + k(k-1)/2 Any choice of c[0], c[1], c[2], and c[3], with c[1]c[2] not zero, determines the values of a,b and therefore all the remaining coefficients. There are many interesting things about these sequences of c[k] values. Focusing on just the sequences with |c[k]| = 1, k=0,1,2,3, there are obviously 16 possible choices, but only 8 up to a simple sign change. These 8 can be arranged as four groups of 2: k I II III IV --- -------- ---------- --------- --------- 0 1 1 -1 1 1 1 1 1 1 1 -1 1 1 1 -1 1 -1 2 1 1 1 -1 -1 -1 1 1 3 -1 1 1 1 -1 1 1 -1 4 1/2 1/2 3/2 -3/2 0 0 1 1 5 1/2 -1/2 5/2 5/2 4/5 -4/5 1 -1 6 -3/2 -3/2 9/2 -9/2 2/5 2/5 1 1 7 3/2 -3/2 19/2 19/2 -2/5 2/5 1 -1 8 3/8 3/8 133/8 -133/8 -1/2 -1/2 1 1 9 -29/8 29/8 267/8 267/8 1/30 -1/30 1 -1 etc Clearly the coefficients in each group differ only in sign. The coefficients in groups I and II diverge, and those in group IV are all units. Only the group III sequences converge. Interestingly, these coefficients are given very closely by c[k-1] = 2 exp(uk) sin(wk) for k>2, where u = -0.145370157... / 1.877672951... for III(a) w = ( \ 1.263919649... for III(b) Notice that the two possible values of w sum to 3.1415926... The integer numerators and denominators of these c[k] sequences also have many interesting properties. For example, primes p congruent to +1 (mod 4) first appear in the denominator at c[p], whereas primes congruent to -1 (mod 4) first appear at c[p^2]. The sequence of numerators is much less regular 1 -1 -1 1 0 -4 2 2 -1 -1 59 -9 -1 233 8 -934 49 .. etc Incidentally, the value of b in the ubiquitous equation (1) is essentially just a constant of integration, and the underlying relation is the derivitive x x'' + q x' x'' = 0 where q=3 for unaccelerated separations and q=2 for (non-rotating) gravitational separations. Isolating q and differentiating again leads to the basic relation, free of arbitrary constants, x x' x'' x'''' - x x' (x'')^2 - x (x'')^2 x''' + (x')^2 x'' x''' = 0 Dividing by x x' x'' x''' gives the nice form x'''' x''' x'' x' ------ - ----- - ---- + ----- = 0 x''' x'' x' x ============================================================================== MathSciNet entry of some connection: ============================================================================== 93a:11012 11B37 11B50 Robinson, Raphael M. Periodicity of Somos sequences. (English) Proc. Amer. Math. Soc. 116 (1992), no. 3, 613--619. _________________________________________________________________ For $k\geq 4$ the sequence defined by $a\sb 0=a\sb 1=\cdots=a\sb {k-1}=1$ and $a\sb na\sb {n-k}=\sum\sp {[k/2]}\sb {i=1}a\sb {n-i}a\sb {n-k+i}$ $(n\geq k)$ is called a Somos$(k)$ sequence. It is known that the terms of this sequence are integers for $k=4,5,6,7$ but not for $k=8$. For some sequences related to the Somos$(k)$ sequences, the author shows that they are periodic modulo $m$ for every $m$, although the periodicity problem remains open for the original sequences. Some observations are also made concerning the prime divisors of the terms and the rate of growth of certain sequences. Reviewed by Peter Kiss © Copyright American Mathematical Society 1993, 1997 [See also Malouf's article in Discrete Math in 1991 -- djr] ============================================================================== This question also presented by Don Zagier at St Andrews, 1996; see http://www-groups.dcs.st-andrews.ac.uk/~john/Zagier/Problems.html for the complete set of problems. Here is a text version of his solution: The sequence ( tn ) starts 1, 1, 1, 1, 1, 2, 3, 5, 11, 37, 83, ... It is required to show that all of the tn are integral. The proof comes from the theory of elliptic curves, and can be expressed either in terms of the denominators of the coordinates of the multiples of a particular point on a particular elliptic curves, or in terms of special values of certain Jacobi theta functions. In the first version, one computes the point nP + T on the elliptic curve E : y(x + y) = x(x - 1)(x + 2), where T is the 2 - torsion point (0,0) and P is the point of infinite order (2,2); this has the form (xn, yn) where the exact denominators of xn and yn are tn2 and tn3, respectively, for some integer tn, and the rules of computation on elliptic curves lead to the given recursion for the t's. I'll omit the analysis, indicating instead two ways that one could be led to find this solution. The first is algebraic. Dividing the recursion tntn+5 = tn+1tn+4 + tn+2tn+3 by tn+1tn+4 gives the simpler recursion wnwn+2 = 1 + 1/wn+1 for the numbers wn = tn+3tn/tn+1tn+2. This says that the seqence of pairs (X, Y) = (wn,wn+1) is generated from the initial value (X, Y) = (1, 1) by (X, Y) |--> (Y, (1 + Y-1)/X). A picture shows that these points (wn, wn+1) all lie on a curve, which is then easily found to be given by the equation (XY - 1)(5 - X - Y) = 6. This is a curve of genus 1 which is isomorphic to the above E via (x,y) = 2(X + Y - 2)/(Y + X - 5), 2(Y - 2X + 1)/(X + Y - 5). The other method is more analytic: one computes the first few (in my case, 300) terms tn numerically, studies their numerical growth, and tries to fit this data by a nice analytic expression. One quickly finds that the growth is roughly exponential in n2, but with some slow fluctuations around this and also with a dependency on the parity of n. This suggests trying the Ansatz tn = C plus or minus BnAn2, where (- 1)n = plus or minus 1. This is easily seen to give a solution to our recursion if A is the root of A12 = A4 + 1, and the numerical value A = 1.07283 (approx) does indeed give a reasonably good fit to the data, but eventually fails more and more thoroughly. Looking more carefully, we try the same Ansatz but with C plus or minus replaced by a function C plus or minus (n) which lies between fixed limits but is almost periodic in n, and this works, but with a new value A = 1.07425 (approx). (The coefficient C plus or minus (n) in fact depends on the position of the point (wn, wn+1) on the above-mentioned curve (XY - 1)(5 - X - Y) = 6.) Expanding the function C plus or minus (n) numerically into a Fourier series, we discover that it is a Jacobi theta function, and since theta functions (or quotients of them) are elliptic functions, this leads quickly to elliptic curves and to the above curve E. By the way, by varying the coefficients in the recursion for the tn one can replace the above (E, P) by essentially any elliptic curve over Q and any rational point on it, so that in an elementary course in number theory one could develop (or at least introduce) the entire theory of elliptic curves just by starting with these simple recursions!