ratio of integers = sqrt(2)
zaphod
of course not (at least not really), but still something interesting
nonetheless... usually the approximations you find of sqrt(2) are found by
calculating series which involve trig functions and all sorts of
not-so-pretty things. i mean, who really likes series and stuff? i know i
dont.
so here's something a little bit more fun to approximate sqrt(2) with:
take the following 2 sets, S and T given by:
S = {s | s = q^2, q element of Z*} aka: the set of square integers
T = {t | t = (p^2 + p)/2, q element of Z*} aka: the set of triangular
numbers
take the intersection of sets S and T and call it K = {1, 36, 1225, ...}
[*more on set K later...]
now each element k of set K is also an element s and t from sets S and T,
with solutions q and p given in the definitions of the sets.
if you take the p and q solutions of a given element k and take the ratio
p/q, and then take the limit as k -> infinity, the limit is sqrt(2).
for example:
for k=1, p=1 and q=1 -> p/q = 1
for k=36, p=8 and q=6 -> p/q = 1.333333333333333333333333...
for k=1225, p=49 and q=35 -> p/q = 1.4
as k gets larger, the values of p/q will rapidly converge to sqrt(2)
i accidentally found this out while i was dabbling around with the relation
of square and triangular numbers... for a while, this result seemed
fascinating to me since p and q are, by definition, positive integers... so,
a ratio of integers (albeit infinitely large) being equal to the square root
of 2 was kinda weird. but since p and q in a sense cease being integers
when we take the limit of k at infinity, there is really nothing of real
value here other than pure curiosity.
but like i said, i think this representation of sqrt(2) is more
mathematically beautiful than series with transcedental functions in them.
as much as i hate to agree with Kronecker, sometimes i must admit that
integers are sometimes more appealing. :)
feel free to leave comments.
*as for set K, if you're curious as to a faster way to find elements of K
than by simply writing out S and T and trying to find similar elements,
here's an algorithm for generating its elements (in sequence, too)
[((k1)-1)^2]/(k0) = k2
example: we know that the first two elements of K are 1 and 36.. so you
put in k0=1 and that k1=36.. plug it into the formula and you get:
[(36-1)^2]/1 = 1225
YAY!!
have fun.
Robin Chapman
> :)
>
> of course not (at least not really), but still something interesting
> nonetheless... usually the approximations you find of sqrt(2) are found
> by calculating series which involve trig functions and all sorts of
> not-so-pretty things. i mean, who really likes series and stuff? i know
> i dont.
Ramanujan did, for one.
> so, a ratio of integers (albeit infinitely large) being equal to the
> square root
> of 2 was kinda weird.
Er, yeah!
--
Robin Chapman, www.maths.ex.ac.uk/~rjc/rjc.html
"Lacan, Jacques, 79, 91-92; mistakes his penis for a square root, 88-9"
Francis Wheen, _How Mumbo-Jumbo Conquered the World_
Virgil
"zaphod" <colin....@videotron.ca> wrote:
> of course not (at least not really), but still something interesting
> nonetheless... usually the approximations you find of sqrt(2) are found by
> calculating series which involve trig functions and all sorts of
> not-so-pretty things. i mean, who really likes series and stuff? i know i
> dont.
The rational approximations of sqrt(2) that I find most common start
with a rational reasonably close to sqrt(2), even 1 or 2 is close
enough, as r_0, and then iterate the recursion formula. Of course, the
better your first guess, the fewer iterations are needed. Each iteration
roughly doubles the number of significant digits of accuracy
For the root of any positive integer m, assuming it not to be the square
of an integer, one uses recursion formula r_{n+1} = (r_n + m/r_n)/2.
Rainer Rosenthal
zaphod wrote
>
> S = {s | s = q^2} (square integers)
> T = {t | t = (p^2 + p)/2} (triangular numbers)
>
> Intersection K = {1, 36, 1225, ...}
> ...
> if you take the p and q solutions of a given element k
> and take the ratio p/q, and then take the limit as
> k -> infinity, the limit is sqrt(2).
>
> for example:
>
> for k=1, p=1 and q=1 -> p/q = 1
> for k=36, p=8 and q=6 -> p/q = 1.333333333333333333333333...
> for k=1225, p=49 and q=35 -> p/q = 1.4
>
> as k gets larger, the values of p/q will rapidly converge to sqrt(2)
>
This looked very recreational indeed and I am sure you did have a
lot of fun with your findings.
I immediately looked into the OEIS and found for "1,36,1225":
http://www.research.att.com/projects/OEIS?Anum=A001110
Sequence: 0,1,36,1225,41616,1413721,48024900,1631432881,
55420693056, 1882672131025,63955431761796
Name: Both triangular and square:
a(n) = 34a(n-1) - a(n-2) + 2.
If you never have heard of this wonderful archive of sequences, you
will now know it and, surely, like it. Thanks to Neil Sloane, who
puts a lot of his life into it.
The formula in the archive is very neat and I will test it against the
known values a(1)=1, a(2)=36, a(3)=1225: 34*36-1+2 = 1225. Aha, OK.
You will find some more interesting formulas in the OEIS, provided
by SeqFans all over the world, so that your finding might be welcomed
as well. There could be no more appropriate place for dicussing your
possible extension of the list of formulas than alt.math.recreational.
Here are some of the formulas:
If L is a square-triangular number, then the next one is
1 + 17*L + 6*sqrt(L + 8*L^2) (Jun 27 2001)
a(n) = A001109(n)^2 = A001108(n)*(A001108(n)+1)/2 =
(A000129(n)*A001333(n))^2 =
(A000129(n)*(A000129(n) + A000129(n-1)))^2 (Apr 19, 2000)
a_{n} = 35(a_{n-1} - a_{n-2}) + a_{n-3} for n>3,
a_1 = 0, a_2 = 1, a_3 = 36. (Oct 23, 2003)
The following formula mentions a relation to 2^(1/2) = sqrt(2):
a_{n} = 35(a_{n-1}-a_{n-2}} + a_{n-3}; a(n) =
-1/16 + ((-24+17*2^(1/2))/2^(11/2))*(17-12*2^(1/2))^(n-1)+
+((24+17*2^(1/2))/2^(11/2))*(17+12*2^(1/2))^(n-1) (Nov 07 2003)
Example:
a(2)=((17+12*sqrt(2)^2+(17-12*sqrt(2)^2-2)/32=
=(289+24*sqrt(2)+288+289-24*sqrt(2)+288-2)/32=(578+576-2)/32=
=1152/32=36 and 6^2=36=8*9/2 =>a(2)
is both the sixth square and the 8th triangular number.
> i accidentally found this out while i was dabbling around with
> the relation of square and triangular numbers... for a while,
> this result seemed fascinating to me since p and q are, by
> definition, positive integers... so, a ratio of integers (albeit
> infinitely large) being equal to the square root of 2 was kinda
> weird. but since p and q in a sense cease being integers when
> we take the limit of k at infinity, there is really nothing of
> real value here other than pure curiosity.
Fishing for compliments, eh? OK: This was really really nice!!
As well as your interesting relation below.
> [((k1)-1)^2]/(k0) = k2
>
> example: we know that the first two elements of K are 1 and 36.. so you
> put in k0=1 and that k1=36.. plug it into the formula and you get:
>
> [(36-1)^2]/1 = 1225
>
> YAY!!
In the nomenclature of the OEIS with k2=a(n+1), k1=a(n), k0=a(n-1)
this reads
a(n+1)*a(n) = (a(n)-1)^2
I checked it with the value found in the OEIS and it is a marvellous
formula! Congratulations again and I look forward for a fine discussion
here in alt.math.recreational. I urge you to send your findings to
Neil's OEIS. If you like, I can help you with the formalism.
I give a copy of the list of references found in the OEIS:
References
A. H. Beiler, Recreations in the Theory of Numbers,
Dover, NY, 1964, p. 193.
L. E. Dickson, History of the Theory of Numbers.
Carnegie Institute Public. 256, Washington, DC, Vol. 1,
1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 10.
H. G. Forder, A Simple Proof of a Result on Diophantine
Approximation, Math. Gaz., 47 (1963), 237-238.
P. Lafer, Discovering the square-triangular numbers,
Fib. Quart., 9 (1971), 93-105.
Martin Gardner, Time Travel and other Mathematical Bewilderments,
pp. 16-17, Freeman 1988
D. A. Q., Triangular square numbers - a postscript,
Math. Gaz., 56 (1972), 311-314.
J. H. Silverman, A Friendly Introduction to Number Theory,
p 196, Prentice Hall 2001
Best regards,
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
Robin Chapman wrote
> Er, yeah!
I think that the findings of zaphod are quite nice.
The sequence of "squaretriangles" has a lot of lovely
properties to which he added
a(n+1)*a(n) = (a(n)-1)^2
a relation so simple and fine that it *must* find
entrance into the OEIS.
The limiting relation with sqrt(2) seems to be interesting
as well and you are the great mathematician here, who may
present a good explanation to the friendly audience of
alt.math.recreational. Will you? It would be great!
Rainer Rosenthal
Rainer Rosenthal wrote
>
> The limiting relation with sqrt(2) seems to be interesting
> as well
Hmm... not really :-)
If s^2 = t*(t+1)/2 then t*(t+1)/s^2 = (t/s)^2 + small = 2 or
(t/s)^2 ~ 2 for large s and t. So t/s ---> sqrt(2) for sides
s and t of large "squaretriangles".
But how about a(n-1)*a(n+1) = (a(n)-1)^2? Is it as easy to see?
Kind regards,
Rainer Rosenthal
r.ros...@web.de
zaphod
somebody had a more elegant way of talking about the sequence in my
so-called set K. :-)
before i send anything to Neil's OEIS, what am i sending exactly? i assume
only the part about the limit of p/q, right?
and no, i wasnt fishing for any compliments, but they are welcome
nonetheless :-p
Zdenek Jizba
zaphod wrote:
> :)
>
> of course not (at least not really), but still something interesting
> nonetheless... usually the approximations you find of sqrt(2) are found by
> calculating series which involve trig functions and all sorts of
> not-so-pretty things. i mean, who really likes series and stuff? i know i
> dont.
The ancient Greeks had their "ladders" to calculate square roots.
For sqrt(2) the ladder was:
2 3
5 7
12 17
29 41
(The first column integer equals the sum of the two integers
above, and the second column integer equals the sum of the
last two integers in column 1) For other ladders the rule differs.
AFAIK they found ladders for square roots up to 17.
Rainer Rosenthal
zaphod wrote
> before i send anything to Neil's OEIS, what am i
> sending exactly? i assume only the part about
> the limit of p/q, right?
>
No, that is the not so interesting part, sorry.
See my other posting, which shows that from
p(p+1)/2=q^2 for large p and q immediately follows
that p/q ~ sqrt(2).
But your relation k0*k2 = (k1-1)^2 is very nice.
Let's see what others will say.
zaphod
"Rainer Rosenthal" <r.ros...@web.de> wrote in message
news:c2fg9p$1t86g7$1...@ID-54909.news.uni-berlin.de...
>
>
> No, that is the not so interesting part, sorry.
> See my other posting, which shows that from
> p(p+1)/2=q^2 for large p and q immediately follows
> that p/q ~ sqrt(2).
>
> But your relation k0*k2 = (k1-1)^2 is very nice.
> Let's see what others will say.
>
> Best regards,
> Rainer Rosenthal
> r.ros...@web.de
>
alright. man, and i really thought that sqrt(2) thing was cool...
*pouts*
zaphod
"Zdenek Jizba" <ji...@verizon.net> wrote in message
news:404B446E...@verizon.net...
>
>
>
> The ancient Greeks had their "ladders" to calculate square roots.
> For sqrt(2) the ladder was:
> 2 3
> 5 7
> 12 17
> 29 41
>
> (The first column integer equals the sum of the two integers
> above, and the second column integer equals the sum of the
> last two integers in column 1) For other ladders the rule differs.
> AFAIK they found ladders for square roots up to 17.
>
that is really really cool!!
Gary Shannon
"zaphod" <colin....@videotron.ca> wrote in message
news:DLz2c.47129$kR4.1...@weber.videotron.net...
> :)
>
> of course not (at least not really), but still something interesting
> nonetheless... usually the approximations you find of sqrt(2) are found
by
> calculating series which involve trig functions and all sorts of
> not-so-pretty things. i mean, who really likes series and stuff? i know
i
> dont.
How about continued fractions? They are definitely cool.
sqrt(2)= 1+1/(2+1/(2+1/(2+1/(...))))
--gary
philippe 92
zaphod wrote:
[...]
>
> so here's something a little bit more fun to approximate sqrt(2) with:
> take the following 2 sets, S and T given by:
>
> S = {s | s = q^2, q element of Z*} aka: the set of square integers
> T = {t | t = (p^2 + p)/2, q element of Z*} aka: the set of triangular
> numbers
>
> take the intersection of sets S and T and call it K = {1, 36, 1225, ...}
> [*more on set K later...]
>
> now each element k of set K is also an element s and t from sets S and T,
> with solutions q and p given in the definitions of the sets.
>
> if you take the p and q solutions of a given element k and take the ratio
> p/q, and then take the limit as k -> infinity, the limit is sqrt(2).
[...]
A few hints (and key words) about that.
Summary : Your set K is related to the "Pell equation" X^2 - 2*Y^2 = 1
It gives "best approximations" of sqrt(2), given by reduced fractions of
the "continued fraction" decomposition of sqrt(2).
This theory is related with "Diophantine approximations".
There is another set K', related to the solutions of X^2 - 2*Y^2 = -1
giving also best approximations of sqrt(2)
This equation is related to the following puzzle :
Find two triangles, one being the double of the other.
Solutions :
(0,0), (6,3), (210,105)...
of the form (x^2-1)/8, (y^2-1)/8
(x,y) = (1,1), (7,5), (41,29)...
the x/y -> sqrt(2)
The set K+K' is given by x_0=1, y_0=1 and the formulas
x_(n+1) = x_n + 2*y_n
y_(n+1) = x_n + y_n
for n -> oo (infinity), x_n/y_n -> sqrt(2)
One over two is higher (set K), the other is lower (set K').
This set (K+K') gives all the best approximations of sqrt(2).
Details :
What numbers are both triangular and squares (the set K) ?
Answer 1, 36, 1125, 41616, ...
How to find them ?
m(m+1)/2 = n^2 let y = 2*m and x = 2*n+1 we get
m, n integer, <=> x odd, y even
x^2 - 2*y^2 = 1
This last equation is called "Pell equation"
The general form is X^2 - D*Y^2 = 1 with D>0 not square.
(generalised Pell equation is X^2 - D*Y^2 = K)
It is part of "Diophantine equations", that is equations to be solved in
integers. There is a full theory about the Pell equations.
Main results are :
There are always infinitely many solutions.
The least non trivial solution is called the fundamental solution
(the trivial solution is x=1, y=0)
let x_0, y_0 be the fundamental solution.
All solutions are given by recursive formulas
x_(n+1) = x_0*x_n + D*y_0*y_n
y_(n+1) = y_0*x_n + x_0*y_n
if x_(-1)=1, y_(-1)=0 is the trivial solution, this gives (x_0,y_0) too.
In our case D=2, x_0=3, y_0=2, and
x_(n+1) = 3*x_n + 4*y_n
y_(n+1) = 2*x_n + 3*y_n
From the equations results immediately :
(x_n/y_n)^2 = 2 + (1/y_n)^2
for n -> oo (infinity), (x_n/y_n)^2 -> 2, so x_n/y_n -> sqrt(2)
Study of the Pell equation is related to "continued fraction"
decomposition. That is (as mentionned by Gary)
r = r_0 + 1/(r_1 + 1/(r_2 + 1/(....
If we decompose sqrt(2) in continued fractions we get :
sqrt(2)= 1 + 1/(2+ 1/(2+ 1/(2+ 1/(2+ ....
If we stop the decomposition at a given rank k, we can reduce the
continued fraction to a simple fraction
P_k/Q_k
for sqrt(2)
P_0/Q_0 = 1/1
P_1/Q_1 = 3/2
P_2/Q_2 = 7/5
P_3/Q_3 = 17/12
The reduced fraction from the continued fraction decomposition give the
"best approximations" of r=sqrt(D) and we have
|r -(Pk/Qk)| < 1/Q_k^2 for any k (|x| = absolute value)
Improving this theory links to the "Diophantine approximations".
The continued fraction decomposition of sqrt(D) is related to solutions
of the Pell equation
X^2 - D*Y^2 = +/-1
In the case of sqrt(2) the solutions of the Pell equation is given by
the odd numbered reduced fractions
(the even numbered give the X^2 - 2*Y^2 = -1 solutions)
applying the recursion formulas to the fundamental (1,1) of this last
equation :
x_(n+1) = x_n + 2*y_n
y_(n+1) = x_n + y_n
give all solutions of *both* equations, and all reduced fractions.
That is *all* the best approximations of sqrt(2).
One over two is higher (x_n/y_n)^2 = 2 + (1/y_n)^2,
the other is lower (x_n/y_n)^2 = 2 - (1/y_n)^2.
regards
--
philippe
(chephip at free dot fr)
Rainer Rosenthal
philippe 92 wrote
>
> A few hints (and key words) about that.
>
Thanks for the interesting comments, which compare
nicely with what I just received in de.sci.mathematik,
when I asked for that "greek ladder".
Could you please comment the nice finding of 'zaphod',
which reads
a(n-1)*a(n+1) = (a(n)-1)^2
for a(n) being the sequence
http://www.research.att.com/projects/OEIS?Anum=A001110
Best regards
Rainer Rosenthal
r.ros...@web.de
Robin Chapman
All of these are related to units in Z[sqrt(2)].
If x^2 is square and triangular, then x^2 = (y^2+y)/2
and so 2(2x)^2 = (2y+1)^2 - 1. So u^2 - 8x^2 = 1
where u = 2y + 1. Conseqently
(u + 2 sqrt(2) x)(u - 2 sqrt(2) x) = 1.
This means that u + 2 sqrt(2) is a positive unit in the ring Z[sqrt(2)].
It's well-known that such units are of the form
a_n + b_n sqrt(2) = (1 + sqrt(2))^n.
To ensure a_n^2 - 2 b_n^2 = 1 we also need n even ---
a_{2n} + b_{2n} sqrt(2) = (3 + 2 sqrt(2))^n.
This gives recurrence
a_{2n+2} = 3 a_{2n} + 4 b_{2n}
and
b_{2n+2} = 2 a_{2n} + 3 b_{2n}.
Here we are actually interested in b_{2n}/2 or rather (b_{2n}/2)^2.
(We can see from these recurrences that b_{2n} is even).
What's the relation to sqrt(2). Certainly a_{2n} and b_{2n} -> infinty
rapidly, so soon a_{2n} + b_{2n} sqrt(2) is large. As
(a_{2n} + b_{2n} sqrt(2))(a_{2n} - b_{2n} sqrt(2)) = 1,
then a_{2n} - b_{2n} sqrt(2) is a small positive number, and
a_{2n}/b_{2n} - sqrt(2) is even smaller.
If we set t = 3 + sqrt(2) we get formulae
a_{2n} = (t^n + t^{-n})/2
and
b_{2n} = (t^n - t^{-n})/(2 sqrt(2)).
Using these any "mysterious" identity involving these numbers can be
sledgehammered into submission.
As a consequence, the n-th square triangle is
(b_{2n}/2)^2 = (t^{2n) - 2 + t^{-2n})/32.
Odysseus
>
> The ancient Greeks had their "ladders" to calculate square roots.
> For sqrt(2) the ladder was:
> 2 3
> 5 7
> 12 17
> 29 41
>
> (The first column integer equals the sum of the two integers
> above, and the second column integer equals the sum of the
> last two integers in column 1) For other ladders the rule differs.
> AFAIK they found ladders for square roots up to 17.
Continuing to (70,99) we arrive at the aspect ratio of the ISO paper
sizes: for example an A4 sheet of stationery is 210 mm wide by 297 mm tall.
Note that the ratio between successive entries in each column
converges to sqrt(2) +/- 1, a number called the "sacred cut", the
second in an interesting sequence of irrationals that begins with the
"golden section". The sacred cut may be found in the proportions of
the regular unicursal octogram in much the same way as is the golden
section in the regular pentagram.
--
Odysseus
Rich Holmes
> Summary : Your set K is related to the "Pell equation" X^2 - 2*Y^2 = 1
> It gives "best approximations" of sqrt(2), given by reduced fractions
> of the "continued fraction" decomposition of sqrt(2).
This is, I believe, related to the following: Consider Pythagorean
triples (a,b,c) where a^2+b^2 = c^2. Of course these triples
correspond to the sides of right triangles whose legs and hypoteneuse
are all integers.
You can't have a = b, but you can find triples where a + 1 = b. For
large a, b and a are nearly equal, so the corresponding triangle is
nearly an isoceles right triangle. In that case 2a/c and 2b/c are
approximations to sqrt(2), or better yet (a+b)/c.
Finding Pythagorean triples where a + 1 = b involves solving a Pell
equation, and the resulting series of approximations to sqrt(2) turns
out to be the same as the ones generated by the odd convergents of the
continued fraction expansion of sqrt(2).
[For example: (a,b,c) = (3,4,5) gives the approximation (3+4)/5
= 1.4;
(a,b,c) = (20,21,29) gives (20+21)/29 = 1.41379
(a,b,c) = (119,120,169) gives (119+120)/169 = 1.41420
and so on.]
- Rich Holmes
Rich Holmes
And really really mysterious, until you learn that this amounts to
finding the convergents of the continued fraction for sqrt(2) without
knowing that's what you're doing....
- Rich Holmes
Rainer Rosenthal
Robin Chapman wrote
> > alt.math.recreational. Will you? It would be great!
>
> All of these are related to units in Z[sqrt(2)].
> ... interesting consequences ...
Thanks a lot for this little course in algebra!
I was very pleased by the way, in which the "greek
ladder" emerged again from (1+sqrt(2))^n.
I'm still not completely thru the fine posting but
I will succeed :-) I want to mention a small typo:
> If we set t = 3 + sqrt(2) we get formulae
^^^^^^^^^^^
"3 + 2*sqrt(2)" is the correct term. But that is clear
from what you said before. It only worried me, when
I tried to read your posting from the end :-)
The OP (zaphod) will surely enjoy your posting, too.
At least I hope so.
Rainer Rosenthal
Rainer Rosenthal wrote
>
> Thanks a lot for this little course in algebra!
Hello Robin,
please have a look at
http://www.research.att.com/projects/OEIS?Anum=A001110
where something most important is missing: your fine
explicit formula
a(n) = (t^{2n) - 2 + t^{-2n})/32 (1)
where t = 3 + 2 sqrt(2)
And another important thing is missing too:
the "mystic formula" of the lucky finder (congratulations)
zaphod, which reads
a(n+1)*a(n) = (a(n)-1)^2 (2)
and which is beautiful and by no means "sledgehammered"
by anything, even not by your fine result. If we try
to "hammer", we get truly ugly formulas:
Combining (1) and (2) and setting u(n)=t^{2n} + t^{-2n}
we have to prove
(u(n)-34)^2 = (u(n-1)-2)*(u(n+1)-2) (3)
which is not really nice :-(
But alas - here is the 34 which together with 17=34/2
mystifies many of the formulas in A001110.
Do you see an elegant bridge between (1) and (2)?
Will you, Robin, send a comment for sequence A001110?
Or shall I? If so, I think it would be best, if I
post this to SeqFan and hear their comments.
philippe 92
Rainer Rosenthal wrote:
>
> Hello Robin,
>
> please have a look at
> http://www.research.att.com/projects/OEIS?Anum=A001110
> where something most important is missing: your fine
> explicit formula
>
> a(n) = (t^{2n) - 2 + t^{-2n})/32 (1)
> where t = 3 + 2 sqrt(2)
Yes ! It is there ! written as :
a(n)=(((17+12*sqrt(2))^n)+((17-12*sqrt(2))^n)-2)/32 - Bruce
Bruce's formula and Robin's are the same because :
a(n) = (t^{2n) - 2 + t^{-2n})/32 (Robin)
t = 3 + 2 sqrt(2)
t^2 = 17+12*sqrt(2) and t^{-2} = 17-12*sqrt(2)
> And another important thing is missing too:
> the "mystic formula" of the lucky finder (congratulations)
> zaphod, which reads
>
> a(n+1)*a(n) = (a(n)-1)^2 (2)
>
> and which is beautiful and by no means "sledgehammered"
> by anything, even not by your fine result. If we try
> to "hammer", we get truly ugly formulas
Not so ugly :
a(n+1)*a(n-1) =
(t^{2n+2)+t^{-2n-2}-2)*(t^{2n-2)+t^{-2n+2}-2)/(32^2) =
(t^{4n}+t^{-4n}+t^4+t^{-4}-2(t^2+t^{-2})(t^{2n}+t^{-2n})+4)/(32^2)
the trick is to compute
t^2 + t^(-2)
t^4 + t^(-4)
t = 3 + 2 sqrt(2) so 1/t = 3 - 2 sqrt(2)
t + 1/t = 6
and t^2 + t^(-2) = (t + 1/t)^2 - 2 = 34
t^4 + t^(-4) = (t^2 + t^(-2))^2 - 2 = 34^2 - 2
Then compare with
(a(n)-1)^2 = ((t^{2n) + t^{-2n} - 34)/32)^2 =
(t^{4n} + t^{-4n} + 34^2 + 2 - 2*34(t^{2n}+t^{-2n}))/(32^2)
Q.E.D.
I didn't succeed to get "elegant" proof from the recursive
formulas.
BTW Please note a typo in my previous post
m(m+1)/2 = n^2 let y = 2*m and x = 2*n+1 we get...
should be :
m(m+1)/2 = n^2 let y = 2*n and x = 2*m+1 we get...
regards.
Rainer Rosenthal
philippe 92 wrote
> Not so ugly :
> a(n+1)*a(n-1) =
> (t^{2n+2)+t^{-2n-2}-2)*(t^{2n-2)+t^{-2n+2}-2)/(32^2) =
> ...
> the trick is to compute
> t^2 + t^(-2)
> t^4 + t^(-4)
> ...
> Then compare with
> (a(n)-1)^2 = ((t^{2n) + t^{-2n} - 34)/32)^2 =
> (t^{4n} + t^{-4n} + 34^2 + 2 - 2*34(t^{2n}+t^{-2n}))/(32^2)
> Q.E.D.
Hallo Philippe,
I read your posting just after having sent a little
summary to the SeqFan mailing list (Friends of OEIS).
So I had so immediately send another posting, which
looks like this:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Some ten minutes ago there was a new posting
in the thread in alt.math.recreational, which
showes the equivalence of Robin Chapmans formula
with one of the OEIS formulas.
And the poster "philippe 92" gives a proof for
"zaphod"'s recurrence too. OK, so I'll ask him,
if he will add this nice recurrence for A001110,
the sequence of Square Triangular Numbers:
a(n-1) * a(n+1) = (a(n)-1)^2 (1)
Everybody will agree that this is a truly fine
recurrence, won't they?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
So I ask you: would you like to propose zaphod's
finding to the OEIS?
Thanks for the interesting discussion. Today I received
a hint for a source (PDF-file), which looks like a good
additional reading to what Robin Chapman has told us:
http://modular.fas.harvard.edu/edu/Fall2001/124/lectures/
lecture 20.
Rainer Rosenthal
r.ros...@web.de
Rainer Rosenthal
zaphod <colin....@videotron.ca> wrote
>
> feel free to leave comments.
>
> *as for set K, if you're curious as to a faster way to find
> elements of K than by simply writing out S and T and trying
> to find similar elements, here's an algorithm for generating
> its elements (in sequence, too)
>
> [((k1)-1)^2]/(k0) = k2
>
> example: we know that the first two elements of K are 1 and 36.. so you
> put in k0=1 and that k1=36.. plug it into the formula and you get:
>
> [(36-1)^2]/1 = 1225
>
> YAY!!
>
> have fun.
>
Thanks, Colin, I did have fun!
Your recurrence relation k0 * k2 = (k1-1)^2 is a great find,
I'd say. I just finished a mail to the OEIS fan group SeqFan,
where I told them that not only the squaretriangles obey that
recurrence relation. (I told them you found it!)
If we start with 0 and 1, then the complete sequence is determined
by the next element r. I call this sequence S_r. Your sequence
of squaretriangles is just S_36 = 0, 1, 36, 1225, ...
The following sequences are of S_r type:
S_4 = A000290 the squares
S_5 = A004146 Alternate Lucas Numbers - 2
S_7 = A054493 A Pellian-related sequence
S_8 = A001108 a(n)-th triangular number is a square
S_9 = A049684 F(2n)^2 where F() = Fibonacci numbers
S_20 = A049683 a(n)=(L(6n)-2)/16, L=Lucas Sequence
S_25 = A089927* Expansion of 1/((1-x^2)(1-5x+x^2))
S_36 = A001110 Both triangular and square
S_49 = A049682 a(n)=(L(8n)-2)/45, L=Lucas sequence
S_144 = A004191^2 a(n)=S(n,12) (Chebyshev's poly 2. kind)
where A089927*(n) = A089927(2n-2)
Isn't it nice, that the squares obey that rule too?
Here you are: (n-1)^2 * (n+1)^2 = (n^2 - 1)^2.
The next square after k0 and k1 is k2 = (k1-1)^2/k0.
Example:
The next square after k0=9 and k1=16 is k2 = 15^2/9 = 25.
Rainer Rosenthal
zaphod <colin....@videotron.ca> wrote
> > The ancient Greeks had their "ladders" to calculate
> > square roots. For sqrt(2) the ladder was:
> >
> > 2 3
> > 5 7
> > 12 17
> > 29 41
> >
> > (The first column integer equals the sum of the two integers
> > above, and the second column integer equals the sum of the
> > last two integers in column 1) For other ladders the rule
differs.
> > AFAIK they found ladders for square roots up to 17.
> >
>
>
> that is really really cool!!
>
From Robin Chapman's posting we learned how to read this
ladder:
(1+sqrt(2)) squared: 1 + 2 + 2*sqrt(2) = 3 + 2*sqrt(2)
Multiplied with (1+sqrt(2)) again: 3+2*2 + (3+2)*sqrt(2)
which is 7 + 5*sqrt(2).
When we proceed from (a+b*sqrt(2)) to a'+b'*sqrt(2) by
multiplication with factor (1+sqrt(2)) we land at
a' = a+2b and b' = a+b. This is the building rule for
the ladder.
In the meantime I provided a comment for sequence A001110,
the squaretriangles, which calls it S_36 and enumerates
some of its relatives: S_4 (the squares) and others.
I don't know if it was a good idea to start a thread for
this matter in sci.math, since nobody answered until now.
Here it is:
Message-ID: <c315vk$21q0ho$1...@ID-54909.news.uni-berlin.de>
Subject: Recurrence for Squares and S_r Type Sequences
I am very happy to have received a welcome for these
observations from the organizer of the OEIS, Neil Sloane.
You, Colin, are explicitely mentioned, as I promised.
Zdenek Jizba
Rainer Rosenthal wrote:
Some of the other ladders:
sqrt(3) 4 7 sqrt(5) 4 9 sqrt(7) 3 8
15 26 17 38 48 127
56 97 72 161 765 2024
209 362 305 682 12192 32257
sqrt(6) 20 49 sqrt(8) 6 17 .....
198 485 35 99
1960 4801 204 577
19402 47525 1189 3363
sqrt(21) however is a tougie
Rainer Rosenthal
Zdenek Jizba wrote
>
> Some of the other ladders:
> sqrt(3) 4 7 sqrt(5) 4 9 sqrt(7) 3 8
> 15 26 17 38 48 127
> 56 97 72 161 765 2024
> 209 362 305 682 12192 32257
>
> sqrt(6) 20 49 sqrt(8) 6 17 .....
> 198 485 35 99
> 1960 4801 204 577
> 19402 47525 1189 3363
>
> sqrt(21) however is a tougie
>
a what?
Rainer Rosenthal
zaphod <colin....@videotron.ca> wrote
> >
> > No, that is the not so interesting part, sorry.
> > See my other posting, which shows that from
> > p(p+1)/2=q^2 for large p and q immediately follows
> > that p/q ~ sqrt(2).
> >
> > But your relation k0*k2 = (k1-1)^2 is very nice.
> > Let's see what others will say.
>
>
>
> *pouts*
>
Cheer up and read:
http://www.research.att.com/projects/OEIS?Anum=A001110
Isn't it fine that your
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plug it into the formula and you get:
[(36-1)^2]/1 = 1225
YAY!!
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
excitement brought you into the "hall of fame"?-)
Jim Nastos
> Zdenek Jizba wrote
> > sqrt(21) however is a tougie
>
> a what?
Probably meant "a toughy."
J
Alex.Lupas
> In article <DLz2c.47129$kR4.1...@weber.videotron.net>,
> "zaphod" <colin....@videotron.ca> wrote:
>
> > of course not (at least not really), but still something interesting
> > nonetheless... usually the approximations you find of sqrt(2) are found by
> > calculating series which involve trig functions and all sorts of
> > not-so-pretty things. i mean, who really likes series and stuff? i know i
> > dont.
>
> with a rational reasonably close to sqrt(2), even 1 or 2 is close
> enough, as r_0, and then iterate the recursion formula. Of course, the
> better your first guess, the fewer iterations are needed. Each iteration
> roughly doubles the number of significant digits of accuracy
>
> For the root of any positive integer m, assuming it not to be the square
> of an integer, one uses recursion formula r_{n+1} = (r_n + m/r_n)/2.
The rational approximations of sqrt(2) that I find most common start
with a rational reasonably close to sqrt(2), even 1 or 2 is close
enough, as r_0, and then iterate the recursion formula. Of course, the
better your first guess, the fewer iterations are needed. Each
iteration
roughly doubles the number of significant digits of accuracy
For the root of any positive integer m, assuming it not to be the
square
of an integer, one uses recursion formula r_{n+1} = (r_n + m/r_n)/2.
Comment:
[1] The sequence (r_n)_{n>=0} , x_0=(m+1)*0.5 , converges to sqrt(m)
even in case when m is arbitrary positive number.
[2] Better approximations of sqrt(A) , A>0, than (r_n) with ,
r_{n+1}=f(r_n) ,
f(x)= (x+A/x)/2 are furnished by sequences :
(y_n) , y_{n+1}=F(y_n), with F(x)= x(x^3+3A)/(3x^2+A) , y_0=(A+1)/2
, or
(z_n) , z_{n+1}=G(z_n), where
G(x)=x(x^4+10Ax^2+5A^2)/(5x^4+10Ax^2+A^2),z_0=(A+!)/2.
Much better, in case A=sqrt(2), try the approximation
X_k =approx.=sqrt(2) k in {5,6,7,8,9,10}
where X_{n+1}=H(X_n) , X_0=3/2 , and
H(x)=X(X^6+42*X^4+140*X^2 +56)/(7*X^6+70*X^4+84*X^2+8) .
Please compute X_1 , x_2, x_3, x_4 and X_5 .
Further, try to prove that that if eps:= 1/(17+12*sqrt(2)) <
1/(33,970) then
| X_k -sqrt(2) | =< 3*{eps}^{7^k} .
Therefore , choosing k=5 , i.e. X_5 (7^5=16807) is a ,,good"
approximation
of sqrt(2) . Further X_10 is ...much better ! ===
Rich Holmes
> Some of the other ladders:
> sqrt(3) 4 7 sqrt(5) 4 9 sqrt(7) 3 8
> 15 26 17 38 48 127
> 56 97 72 161 765 2024
> 209 362 305 682 12192 32257
>
> sqrt(6) 20 49 sqrt(8) 6 17 .....
> 198 485 35 99
> 1960 4801 204 577
> 19402 47525 1189 3363
>
> sqrt(21) however is a tougie
I'm not sure how you obtained these "ladders" but they correspond to
(some of the) convergents in the continued fraction expansions of the
square roots. For sqrt(21) the convergents are
1 4
1 5
2 9
5 23
7 32
12 55
103 472
115 527
218 999
551 2525
- Rich Holmes
philippe 92
> On Tue, 16 Mar 2004, Rainer Rosenthal wrote:
>
>>Zdenek Jizba wrote
>>> sqrt(3) 4 7 sqrt(5) 4 9 sqrt(7) 3 8
>>> 15 26 17 38 48 127
>>> 56 97 72 161 765 2024
>>> 209 362 305 682 12192 32257
>>>
>>
>> a what?
> Probably meant "a toughy."
Hello,
What is the rule for finding such ladders ?
IMHO, the Greek ladder is much simpler. In paper
http://www2.sunysuffolk.edu/wrightj/MA28/Babylon/05GreekLadder.pdf
The Greek ladder for sqrt(D) is defined as :
1. Begin with P=Q=1
2. Next row: Q(n+1)=Q(n)+P(n), P(n+1)=D*Q(n)+P(n)
3. Factor out any common factors Q->Qr, P->Pr
example of sqrt(3) gives :
Q P Qr Pr
1 1 1 1
2 4 1 2 * common to Zdenek's ladders
6 10 3 5
16 28 4 7 *
44 76 11 19
120 208 15 26 *
328 568 41 71
...
(Because it is linear recursion, the P,Q may be replaced by Pr,Qr to get
lower numbers, as done in the mentioned paper)
to be compared with ladder given by Zdenek :
Q P
1 2 (value added to the original post)
4 7
15 26
56 97
209 362
P(n) = 2*P(n-1) + 3*Q(n-1)
Q(n) = P(n-1) + 2*Q(n-1)
The methods differ even more for bigger D, for example sqrt(7)
Original Greek method :
Qr Pr (reduced P,Q)
1 1
1 4
5 11
8 23
31 79
55 148
203 533
368 977
1345 3553
2449 6484
8933 23627
16280 43079
59359 157039
108199 286276
the last P/Q = 2.64582... sqrt(7) = 2.64575...
Zdenek's ladder :
Q P
sqrt(7) 3 8
48 127
765 2024
12192 32257
P(n) = 8*P(n-1) + 21*Q(n-1)
Q(n) = 3*P(n-1) + 8*Q(n-1)
No common terms. But the Greek ladder is simple, the modern one is
harder to iterate.
The last P/Q = 2.6457513123...
sqrt(7) = 2.6457513110...
The modern ladder is much more efficient (gives better accuracy).
How to find the numbers used in the modern ladders ?
and the "toughy" sqrt(21) :
Q P
sqrt(21) 12 55
1320 6049
145188 365455
...
P(n) = 55*P(n-1) + 252*Q(n-1)
Q(n) = 12*P(n-1) + 55*Q(n-1)
not really worse than sqrt(7)
Once you get the start point (from a unit in Z[sqrt(D)] ),
say P_0, Q_0, developping the (P+Q*sqrt(D))(P_0+Q_0*sqrt(D)) product
you get the recursion formulas :
P(n) = P_0*P(n-1) + Q_0*D*Q(n-1)
Q(n) = Q_0*P(n) + P_0*Q(n)
The hardest point is to find the P_0, Q_0.
P_0^2 - D*Q_0^2 = +/-1
It is found with the "PQa algorithm" :
Let U(0)=0, V(0)=1, a=E[sqrt(D)], with E[x]=integer part of x.
and additional variables P,Q : Q(-1)=1, Q(0)=0, P(-1)=0, P(0)=1
Then iterate for i>=0:
a(i) = E[(U(i)+sqrt(D))/V(i)] = E[(U(i)+a)/V(i)]
U(i+1) = a(i)*V(i)-U(i), V(i+1) = (D-U(i+1)^2)/V(i),
(P,Q)(i+1) = a(i)*(P,Q)(i)+(P,Q)(i-1)
And stop when the algorithm loops (V(i) becomes 1 again)
a(i) are the terms of the continued fraction
P(i)/Q(i) are the reduced fractions of sqrt(D)
P(i)^2 - D*Y(i)^2 = (-1)^i*V(i)
example for D=21 :
i U(i) V(i) a(i) P(i+1) Q(i+1)
0 1
1 0
0 0 1 4 4 1
1 4 5 1 5 1
2 1 4 1 9 2
3 3 3 2 23 5
4 3 4 1 32 7
5 1 5 1 55 12
6 4 1 stop (V=1) : 55^2 - 21*12^2 = (-1)^6 = 1
the sqrt(199) needs only 20 steps to get the monsters.
Q P
sqrt(199) 1153080099 16266196520
...
P(n) = 16266196520*P(n-1) + 229462939701*Q(n-1)
Q(n) = 1153080099*P(n-1) + 16266196520*Q(n-1)
This algorithm may be easily programmed.
An example in javascript in my site (french) at
http://chephip.free.fr/exepqa.html
Or use the "generic quadratic solver" to solve the
X^2 - D*Y^2 +/-1 = 0 Pell equation at :
http://www.alpertron.com.ar/QUAD.HTM
However this uses mathematics not known by ancient Greeks.
(The PQa algorithm is from Lagrange).
An intersting site for ancient method of square roots :
http://www2.sunysuffolk.edu/wrightj/MA28/Babylon/
the 04SquareRoots.pdf is fine for a general overview.
Regards
philippe 92
Rich Holmes wrote:
> Zdenek Jizba <ji...@verizon.net> writes:
>
>
>> Some of the other ladders:
>> sqrt(3) 4 7 sqrt(5) 4 9 sqrt(7) 3 8
>> 15 26 17 38 48 127
>> 56 97 72 161 765 2024
>> 209 362 305 682 12192 32257
>>
>> sqrt(21) however is a tougie
>
>
> I'm not sure how you obtained these "ladders" but they correspond to
> (some of the) convergents in the continued fraction expansions of the
> square roots. For sqrt(21) the convergents are
Yes ! all is in the "some of"...
The ladders have the additional property they are _linear recursions_
That is
P(n) = a*P(n-1) + b*Q(n-1)
Q(n) = c*P(n-1) + d*Q(n-1)
Which is _not_ the case for the set of all convergents.
These ladders are in fact obtained from |X^2 - D*Y^2| = 1
to get |(X/Y)^2 - D| = 1/Y^2
Solving this equation results in the linear recursions and the given
ladders.
regards