Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

208 views

Skip to first unread message

Mar 7, 2004, 2:00:35â€¯AM3/7/04

to

:)

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.

Mar 7, 2004, 3:30:50â€¯AM3/7/04

to

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.

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_

Mar 7, 2004, 4:04:28â€¯AM3/7/04

to

In article <DLz2c.47129$kR4.1...@weber.videotron.net>,

"zaphod" <colin....@videotron.ca> wrote:

"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.

Mar 7, 2004, 4:10:31â€¯AM3/7/04

to

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

Mar 7, 2004, 4:30:35â€¯AM3/7/04

to

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!

Mar 7, 2004, 7:11:19â€¯AM3/7/04

to

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

Mar 7, 2004, 10:16:51â€¯AM3/7/04

to

thank you everybody!! i indeed had never heard of the OEIS before. i'm glad

somebody had a more elegant way of talking about the sequence in my

so-called set K. :-)

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

Mar 7, 2004, 10:49:07â€¯AM3/7/04

to

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.

Mar 7, 2004, 10:48:46â€¯AM3/7/04

to

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.

Mar 7, 2004, 11:07:59â€¯AM3/7/04

to

"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*

Mar 7, 2004, 11:48:03â€¯AM3/7/04

to

"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!!

Mar 7, 2004, 12:48:12â€¯PM3/7/04

to

"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

Mar 7, 2004, 1:39:31â€¯PM3/7/04

to

Hello,

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)

Mar 7, 2004, 1:45:02â€¯PM3/7/04

to

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

Mar 7, 2004, 2:02:14â€¯PM3/7/04

to

Rainer Rosenthal wrote:

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.

Mar 7, 2004, 5:03:02â€¯PM3/7/04

to

Zdenek Jizba 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.

>

> 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

Mar 7, 2004, 9:18:05â€¯PM3/7/04

to

philippe 92 <anti...@free.invalid> writes:

> 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

Mar 7, 2004, 9:21:33â€¯PM3/7/04

to

"zaphod" <colin....@videotron.ca> writes:

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

Mar 8, 2004, 3:27:09â€¯PM3/8/04

to

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.

Mar 11, 2004, 2:43:00â€¯PM3/11/04

to

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.

Mar 11, 2004, 6:27:10â€¯PM3/11/04

to

Hello,

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.

Mar 11, 2004, 7:04:17â€¯PM3/11/04

to

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

Mar 13, 2004, 6:10:27â€¯PM3/13/04

to

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.

Mar 15, 2004, 3:05:04â€¯PM3/15/04

to

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.

Mar 15, 2004, 3:45:24â€¯PM3/15/04

to

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

Mar 15, 2004, 6:34:03â€¯PM3/15/04

to

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?

Mar 15, 2004, 6:58:37â€¯PM3/15/04

to

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.

>

> alright. man, and i really thought that sqrt(2) thing was cool...

>

>

> *pouts*

>

>

>

> *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"?-)

Mar 15, 2004, 8:24:15â€¯PM3/15/04

to

On Tue, 16 Mar 2004, Rainer Rosenthal wrote:

> Zdenek Jizba wrote

> > sqrt(21) however is a tougie

>

> a what?

Probably meant "a toughy."

J

Mar 16, 2004, 3:49:28â€¯AM3/16/04

to

Virgil <ITSnetNOTcom/vir...@COMCAST.com> wrote in message news:<ITSnetNOTcom/virgil-3575C3....@news.nntpservers.com>...

> 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.

>

> 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.

> 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 ! ===

Mar 16, 2004, 10:53:26â€¯AM3/16/04

to

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(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

Mar 16, 2004, 1:07:43â€¯PM3/16/04

to

Jim Nastos wrote:

> On Tue, 16 Mar 2004, Rainer Rosenthal wrote:

>

>>Zdenek Jizba wrote

> On Tue, 16 Mar 2004, Rainer Rosenthal wrote:

>

>>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(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

>>

>> a what?

> Probably meant "a toughy."

>>

>> 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

Mar 16, 2004, 1:34:42â€¯PM3/16/04

to

Hello,

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

0 new messages

Search

Clear search

Close search

Google apps

Main menu