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!