[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:	Mathematics at DEC

Moderator:	RUSURE::EDP

Created:	Mon Feb 03 1986
Last Modified:	Fri Jun 06 1997
Last Successful Update:	Fri Jun 06 1997
Number of topics:	2083
Total number of notes:	14613

1338.0. "how can we get continued fractions for square roots ?" by HANNAH::OSMAN (see HANNAH::IGLOO$:[OSMAN]ERIC.VT240) Wed Nov 14 1990 11:02

Goal:   Pick any integer n and represent its sqrt like this:

sqrt(n) = a+1
	    ----
	    b+1
	      ----
	      c+1 ...

where a,b,c are the (largest possible) positive integers.

In short form, let's write this as

sqrt(n) = <a b c ...>

Let's try sqrt(2):

sqrt(2) = a+1/rest

With minimal numerical analysis, we find a=1, so

[1]   sqrt(2) = 1+1/r

Now we want to find integer b in

r = b+1/rest

Well, solving [1] for r, we get

r=1/(sqrt(2)-1)

rationalizing denominator by multiplying top and bottom by sqrt(2)+1, we get

r=1+sqrt(2)

Substituting that r back into [1], we get

sqrt(2) = 1+1/(1+sqrt(2))

Substituting this last into itself ad nauseum, we get

sqrt(2) = 1+1/(1+1+1/(1+1+1/(1+1+1/(1+...

which is

sqrt(2) = 1+1/(2+1/(2+1/...

which we can write in short form as

sqrt(2) = <1 2 2 2 ...>

It's important to note the slight numerical analysis that was used to
get a=1.

Now let's try sqrt(3):

sqrt(3) = a+1/r

With some numerical analysis, we get a=1.  So

[1]   sqrt(3) = 1+1/r

Solving for r,

r=1/(sqrt(3)-1)

Rationalizing,

[2]   r=(1+sqrt(3))/2

We'd like to represent this r again as

[3]   r=b+1/rest

with b as largest possible positive integer.

What is b ?  Well, we're looking for largest integer b such that

2b < 1+sqrt(3) < 2(b+1)

By original numerical analysis, we know sqrt(3) is between 1 and 2, hence
1+sqrt(3) is between 2 and 3, hence

2b < 2.something < 2(b+1)

Since b is an integer, b=1.

Substituting back into [3], we get

[4]   r=1+1/rest

Recall [2] which said r=(1+sqrt(3))/2.  Equate these last two and we have

(1+sqrt(3))/2 = 1+1/rest

Solve for "rest", which we start by subtracting 1 from both sides and
taking reciprocal:

rest = 1/((1+sqrt(3))/2 - 1)

Multiply top and bottom by 2:

rest = 2/(1+sqrt(3)-2).  Simplify that to      rest = 2/(sqrt(3)-1).

Rationalize, which nicely gives a 2 on bottom which we cancel with top, so

rest = 1 + sqrt(3).

The fact that we have sqrt(3) standing alone is our signal that we are
done and can substitute back.  Recall [4]   r=1+1/rest.  Substitute:

r=1+1/(1+sqrt(3)).

Recall [1]   sqrt(3) = 1+1/r.  Substitute ad nauseum:

sqrt(3) = 1+1/1+1/(1+1+1/1+1/(1+1+1/1+1/(1+1+1/...

Simplifying, we have

sqrt(3) = 1+1/1+1/2+1/1+1/2+1/1+1/2+1/...

or in short form,

sqrt(3) = <1 1 2 1 2 1 2 1 2 ...>

The question is, can we simplify this procedure for sqrt(n) for any
integer n ?

T.R	Title	User	Personal Name	Date	Lines
1338.1	Article answers question.	CADSYS::COOPER	Topher Cooper	`Sun Nov 25 1990 16:59`	28
	You will find the answer to your question in: Vuillemin, Jean E.; Exact Real Computer Arithmetic with Continued Fractions; IEEE Transactions on Computers, vol 39, #8; Aug. 1990 pp1087-1105 This discusses using a representation of continued fractions as an implementation for the exact representation of real numbers. The continued fraction is represented (in its most basic form) as a list of numbers (possibly with a loop) with a continuation which specifies how to extend the list, if needed for computation. There are some oddities from most perspectives -- i.e., you may be unable to specify in finite time whether two numbers with a finite representation are equal; but overall, a very general, not extraordinarily inefficient, representation is given for "computable" reals. Two basic algorithms are given. The "algebraic algorithm" allows algebraic reals to be specified, while the "transcendental algorithm" allows a broad class of transcendental reals to be specified (logs, exponentials, trig, and inverse trig; the abstract says "as well as a wide class of special functions", but these special functions are left, essentially as an exercise for the reader). Anyway, on page 1100 is an algorithm (specialized from the algebraic algorithm) for finding the representation of the square root of an arbitrary rational number. You will have to read the preceding material since the description does not stand on its own. Topher
1338.2	x=p+1/(a+1/(a+1/(a+...	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Thu Nov 29 1990 10:33`	65
	If a quadratic equation with integer coefficients kx�+qx+r = 0 has any positive real solutions, then at least one of those can be represented as a simple repeating continued fraction. The converse can be proven too, namely that any simple repeating continued fraction is the root of exactly one quadratic equation with integer coefficients. I thought it would be interesting to take a simple case, and try to find the corresponding quadratic equation. For example, suppose we start with x = p + 1/(a + 1/(a + 1/(a + ... for integers p and a. What quadratic equation is this a root of ? First, write it like this: 1/(x-p) = a+1/(a+1/(a+1/... Concentrate just on that right side for a moment. Call it y. We have [1] 1/(x-p) = y y = a+1/... The "..." is y all over again so we have y = a+1/y Transforming, we get y� - ay - 1 = 0 This is a quadratic equation having roots y = (a�sqrt(a�+4))/2 Plugging that y back into [1] and solving for x, we have x1,x2 = p + 2/(a�sqrt(a�+4)) If we assume these two x's are the roots of the quadratic equation (x-x1)(x-x2) = 0 then we have (x-(p+2/(a+sqrt(a�+4))(x-(p+2/(a-sqrt(a�+4)) = 0 Would any of you other readers be willing to manually, or perhaps with MAPLE simplify this last equation to the form kx�+qx+r = 0 This will tell us which quadratic equations have roots of the form x = p + 1/(a + 1/(a + 1/(a + ... Thanks ! /Eric
1338.3		GUESS::DERAMO	Dan D'Eramo	`Thu Nov 29 1990 12:01`	29
	re .2, >> y� - ay - 1 = 0 >> >>This is a quadratic equation having roots >> >> y = (a�sqrt(a�+4))/2 >> >>Plugging that y back into [1] and solving for x, we have >> >> x1,x2 = p + 2/(a�sqrt(a�+4)) The product of the roots of y� - ay - 1 = 0 is -1, the constant term of the polynomial equation. So it is easy to find the reciprocals of those roots. 2/(a+sqrt(a�+4)) = (-a+sqrt(a�+4))/2 2/(a-sqrt(a�+4)) = (-a-sqrt(a�+4))/2 Then x1,x2 = p + (-a�sqrt(a�+4))/2 x� + (a-2p)x + ((2p-a)� - (a�+4))/4 = 0 x� + (a-2p)x + (p�-ap-1) = 0 Dan
1338.4		GUESS::DERAMO	Dan D'Eramo	`Thu Nov 29 1990 12:05`	12
	re .0, >> sqrt(2) = <1 2 2 2 ...> This is the positive root of x� - 2 = 0. Plugging in to .-1 yields a-2p = 0 p�-ap-1 = -2 And what do you know, p=1,a=2 fits! Dan
1338.5	avoiding quadratic formula, and interesting questions for readers	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Tue Dec 04 1990 09:47`	223
	Thanks to Dan's reminder about the product and sum of roots, I realize now that we don't even need to apply the quadratic formula at all to find what equations have the roots [1] x = p + 1 ---- a + 1 ---- a + 1 ---- a + ... As before, write this as x = p + 1/y where y = a+1/y Solving for y, y� = ay + 1 [2] y� - ay - 1 = 0 Don't bother with the quadratic formula at this point at all, but instead just assume this quadratic equation has two roots y and y . Therefore � � (y - y ) (y - y ) = 0 � � When expanded, that's y� - y y - y y + y y = 0 � � � � or y� - (y + y )y + y y = 0 � � � � Matching this with equation [2], we have [3] y + y = a, y y = -1 � � � � Go back to equation [1], and assume it has two roots x and x , which are produced from the two y's. � � So we have x = p + 1/y , x = p + 1/y � � � � Using [3], 1/y is -y and 1/y is -y so we can write the x's as: � � � � [4] x = p - y , x = p - y � � � � As these are roots, we know (x - x ) (x - x ) = 0 � � Expanding, just as we did with the y's before, we get: x� - (x + x )x + x x = 0 � � � � Using [4] to produce the sums and products, we rewrite as x� - (2p - (y + y ))x + p� - (y + y )p + y y � � � � � � Recall [3] which says: [3] y + y = a, y y = -1 � � � � This allows us to simplify our x equation still further: x� - (2p - a)x + p� - ap - 1 = 0 We write slightly differently, to show that it's exactly what Dan got: [5] x� + (a - 2p)x + (p� - ap - 1) = 0 Let's use this in a practical example. Suppose we'd like to know the closed form for [4] x = 2 + 1 ---- 3 + 1 ---- 3 + 1 ---- 3 + ... We have p=2, a=3. Applying [5], the closed form is represented by the roots of the equation x� - x - 3 = 0 Applying quadratic formula, we get 1 � sqrt (13) [6] x = -------------- 2 We can check [6] directly to see if we get the same x. Rewrite [4] as x = 2 + 1/y where y = 3 + 1/y so y - 3 = 1/y or x = 2 + y - 3 or x = y - 1 Writing the y equation as standard quadratic form, we have y� - 3y - 1 = 0 Using quadratic formula, we have 3 � sqrt (13) y = -------------- 2 Subtract 1 to produce x: 3 � sqrt (13) x = -------------- - 1 2 Cross-multiply to get: 1 � sqrt (13) x = -------------- 2 This is exactly what we got in [6], so we're confident that we computed [5] correctly. Intermediate exploratory exercises for the reader: What quadratic equation describes the values of: x = p + 1 ---- q + 1 ---- a + 1 ---- a + 1 ---- a + ... ??? What quadratic equation describes the values of: x = p + 1 ---- a + 1 ---- b + 1 ---- a + 1 ---- b + ... ??? Advanced exploratory exercise for the reader: Represent the more general case as x = [ p p p ... p <a a a ... a > ] G � � � n � � � m This notation stands for the repeating fraction starting with some arbitrary p's, then finishing with infinitely repeating series of a's. Here's an example: x = [ 2 4 6 <3 1 1> ] stands for... x = 2 + 1 ----- 4 + 1 ----- 6 + 1 ----- 3 + 1 ----- 1 + 1 ----- 1 + 1 ----- 3 + 1 ----- 1 + 1 ----- 1 + 1 ----- 3 + ... ( the 3 1 1 denominators repeat) The advanced questions: o Prove that all x are solutions to a quadratic equation having G functions of the p's and a's in the coefficients. o Find the quadratic equation !
1338.6	How to compute continued fractions for sqrt(n)	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Wed Dec 12 1990 11:37`	239
	I have finally figured out how to compute the continued fraction for square roots. Contained in this paper: 1) An example of computing sqrt(19) 2) A generalized example with reference to an unprovem theorem (see another note for discussion of the theorem) Suppose we wish to express sqrt(19) = a + 1/b where a is an integer. Well, 44 is 16, and 55 is 25, too much, so a = 4. So we have sqrt(19) = 4 + 1/b To make the equation still hold, then necessarily the 1/b is sqrt(19)-4, and we want to leave the "1/" there, so we write as: sqrt(19) = 4 + 1/(1/(sqrt(19)-4)) Rationalize the denominator by multiplying top and bottom by sqrt(19)+4, giving us sqrt(19) = 4 + 1/((sqrt(19)+4)/3) We remind ourselves the form we're trying to follow, namely sqrt(19) = 4 + 1/(a + 1/b) (This is a form, so the "a" and "b" are different than before. So, we have (sqrt(19)+4)/3 = a + 1/b This "a" is easily seen be 2, since 4 < sqrt(19) < 5, hence 8 < sqrt(19)+4 < 9. So, (sqrt(19)+4)/3 = 2 + 1/b As before, we represent b as the reciprocal of the lefthand side with a subtracted, so (sqrt(19)+4)/3 = 2 + 1/(1/((sqrt(19)+4/3) - 2) Combining the -2 with the fraction by cross-multiplying, we have (sqrt(19)+4)/3 = 2 + 1/(1/((sqrt(19)-2)/3)) Remove the inner reciprocal by flipping, so (sqrt(19)+4)/3 = 2 + 1/(3/(sqrt(19)-2)) Rationalize denominator again, giving (sqrt(19)+4)/3 = 2 + 1/(3(sqrt(19)+2)/15) THIS IS WHERE AN UNPROVEN BUT HOPEFULLY EASY-TO-PROVE THEOREM APPEARS. Namely, the 15 is divisible by 3 and I believe the denominator at this step always will be. See another note where I address the theorem directly. So, (sqrt(19)+4)/3 = 2 + 1/((sqrt(19)+2)/5) In process, we've come full circle, because now we want to solve (sqrt(19)+2)/5 = a + 1/b which can be done exactly as we did with (sqrt(19)+4)/3. Eventually, we come back to (sqrt(19)+4)/3, so we know the pattern repeats. The particular string of a's that emerge for this example shows that sqrt(19) = 4+1/(2+1/(1+1/(3+1/(1+1/(2+1/... Written in short form sqrt(19) = 4 2 1 3 1 2 8 2 1 3 1 2 8 2 1 3 1 2 8 ... To generalize all of this, suppose we start with (sqrt(r)+s)/t and we wish to generate the continued fraction. So, we the form (sqrt(r)+s)/t = a + 1/b We can find a, given only the \|sqrt(r)\|. The vertical bar means "floor" of what's inside, or the largest integer less than the value inside. So, a = \|(\|sqrt(r)\|+s)/t\| Represent b as the reciprocal of the difference of "a" and (sqrt(r)+s)/t: b = 1/((sqrt(r)+s)/t) - a) Cross-multiply to make single fraction on bottom: b = 1/(((sqrt(r)+s-at)/(at)) Since it's a single fraction, we can flip and simplify: b = at/((sqrt(r)+s-at) We want to rationalize the bottom, so let w=s-at and rationalize: b = at(sqrt(r)-w)/(r-ww) HERE'S WHERE THE UNPROVED THEOREM COMES IN. THE THEOREM SAYS: "at" divides evenly into r-ww or as mathematicians like to say it: at \| r-ww So, assuming that theorem is true, we let x=(r-ww)/at, so we have b = (sqrt(r)-w)/x This is an identical problem as before. If w and x match the original s and t, we can stop since we know the values will repeat the same forever. If w and x don't match, we just set up the form (sqrt(r)-w)/x = a +1/b and repeat the process. I formalized the above in a program, and ran it for all the numbers from 1 to 100. Here they are: sqrt(1) = 1. sqrt(2) = 1 2 2 2 ... sqrt(3) = 1 1 2 1 2 1 2 ... sqrt(4) = 2. sqrt(5) = 2 4 4 4 ... sqrt(6) = 2 2 4 2 4 2 4 ... sqrt(7) = 2 1 1 1 4 1 1 1 4 1 1 1 4 ... sqrt(8) = 2 1 4 1 4 1 4 ... sqrt(9) = 3. sqrt(10) = 3 6 6 6 ... sqrt(11) = 3 3 6 3 6 3 6 ... sqrt(12) = 3 2 6 2 6 2 6 ... sqrt(13) = 3 1 1 1 1 6 1 1 1 1 6 1 1 1 1 6 ... sqrt(14) = 3 1 2 1 6 1 2 1 6 1 2 1 6 ... sqrt(15) = 3 1 6 1 6 1 6 ... sqrt(16) = 4. sqrt(17) = 4 8 8 8 ... sqrt(18) = 4 4 8 4 8 4 8 ... sqrt(19) = 4 2 1 3 1 2 8 2 1 3 1 2 8 2 1 3 1 2 8 ... sqrt(20) = 4 2 8 2 8 2 8 ... sqrt(21) = 4 1 1 2 1 1 8 1 1 2 1 1 8 1 1 2 1 1 8 ... sqrt(22) = 4 1 2 4 2 1 8 1 2 4 2 1 8 1 2 4 2 1 8 ... sqrt(23) = 4 1 3 1 8 1 3 1 8 1 3 1 8 ... sqrt(24) = 4 1 8 1 8 1 8 ... sqrt(25) = 5. sqrt(26) = 5 10 10 10 ... sqrt(27) = 5 5 10 5 10 5 10 ... sqrt(28) = 5 3 2 3 10 3 2 3 10 3 2 3 10 ... sqrt(29) = 5 2 1 1 2 10 2 1 1 2 10 2 1 1 2 10 ... sqrt(30) = 5 2 10 2 10 2 10 ... sqrt(31) = 5 1 1 3 5 3 1 1 10 1 1 3 5 3 1 1 10 1 1 3 5 3 1 1 10 ... sqrt(32) = 5 1 1 1 10 1 1 1 10 1 1 1 10 ... sqrt(33) = 5 1 2 1 10 1 2 1 10 1 2 1 10 ... sqrt(34) = 5 1 4 1 10 1 4 1 10 1 4 1 10 ... sqrt(35) = 5 1 10 1 10 1 10 ... sqrt(36) = 6. sqrt(37) = 6 12 12 12 ... sqrt(38) = 6 6 12 6 12 6 12 ... sqrt(39) = 6 4 12 4 12 4 12 ... sqrt(40) = 6 3 12 3 12 3 12 ... sqrt(41) = 6 2 2 12 2 2 12 2 2 12 ... sqrt(42) = 6 2 12 2 12 2 12 ... sqrt(43) = 6 1 1 3 1 5 1 3 1 1 12 1 1 3 1 5 1 3 1 1 12 1 1 3 1 5 1 3 1 1 12 ... sqrt(44) = 6 1 1 1 2 1 1 1 12 1 1 1 2 1 1 1 12 1 1 1 2 1 1 1 12 ... sqrt(45) = 6 1 2 2 2 1 12 1 2 2 2 1 12 1 2 2 2 1 12 ... sqrt(46) = 6 1 3 1 1 2 6 2 1 1 3 1 12 1 3 1 1 2 6 2 1 1 3 1 12 1 3 1 1 2 6 2 1 1 3 1 12 ... sqrt(47) = 6 1 5 1 12 1 5 1 12 1 5 1 12 ... sqrt(48) = 6 1 12 1 12 1 12 ... sqrt(49) = 7. sqrt(50) = 7 14 14 14 ... sqrt(51) = 7 7 14 7 14 7 14 ... sqrt(52) = 7 4 1 2 1 4 14 4 1 2 1 4 14 4 1 2 1 4 14 ... sqrt(53) = 7 3 1 1 3 14 3 1 1 3 14 3 1 1 3 14 ... sqrt(54) = 7 2 1 6 1 2 14 2 1 6 1 2 14 2 1 6 1 2 14 ... sqrt(55) = 7 2 2 2 14 2 2 2 14 2 2 2 14 ... sqrt(56) = 7 2 14 2 14 2 14 ... sqrt(57) = 7 1 1 4 1 1 14 1 1 4 1 1 14 1 1 4 1 1 14 ... sqrt(58) = 7 1 1 1 1 1 1 14 1 1 1 1 1 1 14 1 1 1 1 1 1 14 ... sqrt(59) = 7 1 2 7 2 1 14 1 2 7 2 1 14 1 2 7 2 1 14 ... sqrt(60) = 7 1 2 1 14 1 2 1 14 1 2 1 14 ... sqrt(61) = 7 1 4 3 1 2 2 1 3 4 1 14 1 4 3 1 2 2 1 3 4 1 14 1 4 3 1 2 2 1 3 4 1 14 ... sqrt(62) = 7 1 6 1 14 1 6 1 14 1 6 1 14 ... sqrt(63) = 7 1 14 1 14 1 14 ... sqrt(64) = 8. sqrt(65) = 8 16 16 16 ... sqrt(66) = 8 8 16 8 16 8 16 ... sqrt(67) = 8 5 2 1 1 7 1 1 2 5 16 5 2 1 1 7 1 1 2 5 16 5 2 1 1 7 1 1 2 5 16 ... sqrt(68) = 8 4 16 4 16 4 16 ... sqrt(69) = 8 3 3 1 4 1 3 3 16 3 3 1 4 1 3 3 16 3 3 1 4 1 3 3 16 ... sqrt(70) = 8 2 1 2 1 2 16 2 1 2 1 2 16 2 1 2 1 2 16 ... sqrt(71) = 8 2 2 1 7 1 2 2 16 2 2 1 7 1 2 2 16 2 2 1 7 1 2 2 16 ... sqrt(72) = 8 2 16 2 16 2 16 ... sqrt(73) = 8 1 1 5 5 1 1 16 1 1 5 5 1 1 16 1 1 5 5 1 1 16 ... sqrt(74) = 8 1 1 1 1 16 1 1 1 1 16 1 1 1 1 16 ... sqrt(75) = 8 1 1 1 16 1 1 1 16 1 1 1 16 ... sqrt(76) = 8 1 2 1 1 5 4 5 1 1 2 1 16 1 2 1 1 5 4 5 1 1 2 1 16 1 2 1 1 5 4 5 1 1 2 1 16 ... sqrt(77) = 8 1 3 2 3 1 16 1 3 2 3 1 16 1 3 2 3 1 16 ... sqrt(78) = 8 1 4 1 16 1 4 1 16 1 4 1 16 ... sqrt(79) = 8 1 7 1 16 1 7 1 16 1 7 1 16 ... sqrt(80) = 8 1 16 1 16 1 16 ... sqrt(81) = 9. sqrt(82) = 9 18 18 18 ... sqrt(83) = 9 9 18 9 18 9 18 ... sqrt(84) = 9 6 18 6 18 6 18 ... sqrt(85) = 9 4 1 1 4 18 4 1 1 4 18 4 1 1 4 18 ... sqrt(86) = 9 3 1 1 1 8 1 1 1 3 18 3 1 1 1 8 1 1 1 3 18 3 1 1 1 8 1 1 1 3 18 ... sqrt(87) = 9 3 18 3 18 3 18 ... sqrt(88) = 9 2 1 1 1 2 18 2 1 1 1 2 18 2 1 1 1 2 18 ... sqrt(89) = 9 2 3 3 2 18 2 3 3 2 18 2 3 3 2 18 ... sqrt(90) = 9 2 18 2 18 2 18 ... sqrt(91) = 9 1 1 5 1 5 1 1 18 1 1 5 1 5 1 1 18 1 1 5 1 5 1 1 18 ... sqrt(92) = 9 1 1 2 4 2 1 1 18 1 1 2 4 2 1 1 18 1 1 2 4 2 1 1 18 ... sqrt(93) = 9 1 1 1 4 6 4 1 1 1 18 1 1 1 4 6 4 1 1 1 18 1 1 1 4 6 4 1 1 1 18 ... sqrt(94) = 9 1 2 3 1 1 5 1 8 1 5 1 1 3 2 1 18 1 2 3 1 1 5 1 8 1 5 1 1 3 2 1 18 1 2 3 1 1 5 1 8 1 5 1 1 3 2 1 18 ... sqrt(95) = 9 1 2 1 18 1 2 1 18 1 2 1 18 ... sqrt(96) = 9 1 3 1 18 1 3 1 18 1 3 1 18 ... sqrt(97) = 9 1 5 1 1 1 1 1 1 5 1 18 1 5 1 1 1 1 1 1 5 1 18 1 5 1 1 1 1 1 1 5 1 18 ... sqrt(98) = 9 1 8 1 18 1 8 1 18 1 8 1 18 ... sqrt(99) = 9 1 18 1 18 1 18 ... Anyone that wants a copy of the program, send a SASE to Eric Osman Digital Equipment Corp. USA
1338.7	Continued fractions is non-unique.	CADSYS::COOPER	Topher Cooper	`Wed Dec 12 1990 12:45`	10
	Very good, Eric. Note that you do not have to use "floor". Equally valid fractions will result if you use "ceiling" or sometimes use one and sometimes the other (e.g., alternating, rounding or randomly). You might have started your example with a = 25. The initial 1/b would then have had to be negative, but there is nothing wrong with that, it just means that the next a would have been negative rather than positive. Topher
1338.8		GUESS::DERAMO	Sometimes they leave skid marks.	`Wed Dec 12 1990 13:05`	12
	re .7 Continued fractions is non-unique. However, there is a bijective correspondence between the irrationals in (0,1) and \omega-sequences of positive integers, x <--> 1/(n0 + 1/(n1 + 1/(n2 + ...))). If you topologize the irrationals in (0,1) as a subspace of the order topology on the real line, and topologize the set of such sequences as a product of discrete spaces, then continued fraction evaluation is a homeomorhpism (a bijection and both it and its inverse are continuous). Dan
1338.9	translating into English...	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Wed Dec 12 1990 13:39`	7
	Gee, if I were as good a go player as Dan is a mathematician... By limiting the values to POSITIVE ones, then every positive real has a UNIQUE mapping to a simple continued fraction. (I think my number theory book uses the term "simple" continued fraction to mean positive integers as the "a's".)
1338.10		GUESS::DERAMO	Sometimes they leave skid marks.	`Wed Dec 12 1990 14:40`	40
	Thanks. >> By limiting the values to POSITIVE ones, then every positive real has >> a UNIQUE mapping to a simple continued fraction. (I think my number >> theory book uses the term "simple" continued fraction to mean positive >> integers as the "a's".) Be careful with that word "UNIQUE". If you define [n0,n1,n2,...] = 1/(n1 + 1/(n2 + 1/(n3 + ...))) then the bijective correspondence is between the irrationals in (0,1) and the nonterminating continued fractions of positive integers [n0,n1,n2,...]. If you define <a0,a1,a2,...> = a0 + 1/(a1 + 1/(a2 + ...))) = a0 + [a1,a2,a3,...] = 1/[a0,a1,a2,...] then there is a bijective correspondence between the irrationals GREATER THAN ONE and the nonterminating continued fractions of positive integers <a0,a1,a2,...>. Or, there is a bijective correspondence between the positive irrationals and the nonterminating continued fractions <a0,a1,a2,...> where a0 is a nonnegative integer and a1,a2,a3,... are positive integers. The rationals/terminating continued fractions cause even more problems if you desire uniqueness, as for example 2 = <2> = <1,1>. If you "outlaw" terminating with a 1 then how do you represent 1 = <1>? You have to be very careful if you want to specify a unique canonical form for expressing rationals. Dan
1338.11	not to mention...	HANNAH::OSMAN	see HANNAH::IGLOO$:[OSMAN]ERIC.VT240	`Wed Dec 12 1990 14:53`	8
	Not to mention that [a0,a1,a2] = a0+1/(a1+1/a2) = a0+1/(a1+1/(a2-1 + 1/1)) = [a0,a1,a2-1,1] but my book number theory book defines uniqueness and acknowledges this specific-but-uninteresting counterexample. /Eric