Thread: Continued Fraction Expansion Problems

Hello All, I have some questions regarding Continued Fraction Expansion.

As an initial reference, these problems have come from my textbook in the "additional examples" area. My book doesn't really give the best explanation of those examples all the time, and as a result I have a few questions.

Q1. The numbers a_k can be found for 113/50 by using a continued fraction algorithm. Note that 113/50 is rational, and as a result it will have to terminate. Can anyone help me find this a_k ?

Q2. Given the following, one should be able to form a continued fraction expansion for $\displaystyle e $.

We initially write (x,y,z,....) for the continued fraction of $\displaystyle x + (1/(y+(1/(z+(1/...)))))$. From here, the continued fraction expansion for $\displaystyle 2.718281828459045$ is $\displaystyle (2,1,2,1,1,4,1,1,6,1,1,8,1,1) $. Knowing this, how many terms are necessary in order to accurately get 4 decimal places (2.718) ?

Q3. Assume that x=Sqrt[3]-1. It can be proven that x = 1/(1+(1/(2+x))). Can somebody prove this? After it has been proven, the proof can be used to find the continued fraction expansion for x (Can somebody show this?). Next, find the continued franction expansion for Sqrt[3]. Once completed, a good accuracy check is that the first 6 or 7 terms of the expansion should give a reasonable approximation for Sqrt[3]. (The underlined portions are the questions I am asking).

Q4. What is the continued fraction expansion of Sqrt[5]? My book notes that it might be helpful if "you find the continued fraction explansion of x where 0<x<1 and x is related to Sqrt[5].

Q5. What is the continued fraction expansion of Sqrt[7]? My book notes that part of the expansion is (2,1,1,1,4,1,1,1,...). Is the next entry in this expansion a 2 or a 4 ? Also, it mentions that you can find some number like what I had mentioned in Q4, and once we have our answer we should be able to show why it is correct.

Any help is appreciated!

first question I will show you how u can find the continued fraction for 133/50

$\displaystyle \frac{113}{50} = 2.26$

i=2

$\displaystyle 2.26 - 2 = .26 $

$\displaystyle \frac{26}{100} $

$\displaystyle \frac{100}{26} = 3+ \frac{22}{26} $
3 is $\displaystyle a_1 $

$\displaystyle \frac{26}{22} = 1 + \frac{4}{22} $
1 is $\displaystyle a_2 $

$\displaystyle \frac{22}{4} = 5 + \frac{2}{4} $

$\displaystyle a_3 = 5 $

$\displaystyle \frac{4}{2} = 2 $

$\displaystyle a_4 = 2 $ so the continued fraction is

[i ; a_1 , a_2 , a_3 , a_4 ]
[2; 3 , 1 , 5 , 2 ]

Q2
I think the best way is to find the continued fraction for 2.718 = r

i =2

r- 2 =718/1000

1000/718 = 1 + 282/718

718/282 = 2 + 154/282

282/154 = 1 + 128/154

154 /128 = 1 + 26/128

128/26 = 4 + 24/26

26/24 = 1 + 2/24

24/2 = 12 end

[2 ; 1, 2, 1, 1, 4, 1, 12 ]

for more information see this

http://en.wikipedia.org/wiki/Continued_fraction

Originally Posted by Amer

first question I will show you how u can find the continued fraction for 133/50

$\displaystyle \frac{113}{50} = 2.26$

i=2

$\displaystyle 2.26 - 2 = .26 $

$\displaystyle \frac{26}{100} $

$\displaystyle \frac{100}{26} = 3+ \frac{22}{26} $
3 is $\displaystyle a_1 $

$\displaystyle \frac{26}{22} = 1 + \frac{4}{22} $
1 is $\displaystyle a_2 $

$\displaystyle \frac{22}{4} = 5 + \frac{2}{4} $

$\displaystyle a_3 = 5 $

$\displaystyle \frac{4}{2} = 2 $

$\displaystyle a_4 = 2 $ so the continued fraction is

[i ; a_1 , a_2 , a_3 , a_4 ]
[2; 3 , 1 , 5 , 2 ]

Q2
I think the best way is to find the continued fraction for 2.718 = r

i =2

r- 2 =718/1000

1000/718 = 1 + 282/718

718/282 = 2 + 154/282

282/154 = 1 + 128/154

154 /128 = 1 + 26/128

128/26 = 4 + 24/26

26/24 = 1 + 2/24

24/2 = 12 end

[2 ; 1, 2, 1, 1, 4, 1, 12 ]

for more information see this

Continued fraction - Wikipedia, the free encyclopedia

Okay, I'm trying to follow along your work here.

What is i ?

Also for Q1 I take it a_k that I was looking for is a_4 = 2 (which terminates the algorithm) ?

For Q2, I take it there are 7 terms necessary in order to get 4 digits of accuracy because there are 7 items in this array [2 ; 1, 2, 1, 1, 4, 1, 12 ] ?

------ Also, anyone have any ideas on the other questions or is able to confirm his Q1 and Q2 responses?

Originally Posted by Samson

Okay, I'm trying to follow along your work here.

What is i ?

Also for Q1 I take it a_k that I was looking for is a_4 = 2 (which terminates the algorithm) ?

For Q2, I take it there are 7 terms necessary in order to get 4 digits of accuracy because there are 7 items in this array [2 ; 1, 2, 1, 1, 4, 1, 12 ] ?

------ Also, anyone have any ideas on the other questions or is able to confirm his Q1 and Q2 responses?

i the integer part for the number that we want to find the continued fraction for it
yeah a_4 terminated the algorithms

Q2 is true 7 terms

Q3

$\displaystyle x = \sqrt{3} -1 $

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

take the second

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

$\displaystyle x = \frac{1}{\frac{2+x+1}{2+x}} $

$\displaystyle x = \frac{2+x}{x+3} $

$\displaystyle x(x+3) = 2+x $

$\displaystyle x^2 +3x = 2+x \Rightarrow x^2+2x-2=0 $

find x,then we are done

how to write $\displaystyle x =\sqrt{3}-1 $ in continued fraction using $\displaystyle x = \frac{1}{1+ \frac{1}{2+x}} $

$\displaystyle \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr ac{1}{2+..}}}}}}}}}}$

I just sub x value each time it will never end

$\displaystyle \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr ac{1}{2+..}}}}}}}}}}$

so

$\displaystyle \sqrt{3} = 1 +\dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr ac{1}{2+..}}}}}}}}}}$

the continued fraction of sqrt{3} [1,2,1,2,1,2,...]
first 6 terms will be (1,2,1,2,1,2)

Also, note that, given some set of numbers $\displaystyle a_0, a_1, a_2, \dots a_n$, if the series $\displaystyle u_{n + 1} = u_n^{-1} + a_n$ converges towards your value, then the continued fraction expansion of this value is $\displaystyle [a_n, a_{n - 1}, a_{n - 2}, \dots, a_0]$. The reciprocal is true as well.

That might give you a clue ...

Originally Posted by Amer

i the integer part for the number that we want to find the continued fraction for it
yeah a_4 terminated the algorithms

Q2 is true 7 terms

Q3

$\displaystyle x = \sqrt{3} -1 $

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

take the second

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

$\displaystyle x = \frac{1}{\frac{2+x+1}{2+x}} $

$\displaystyle x = \frac{2+x}{x+3} $

$\displaystyle x(x+3) = 2+x $

$\displaystyle x^2 +3x = 2+x \Rightarrow x^2+2x-2=0 $

find x,then we are done

how to write $\displaystyle x =\sqrt{3}-1 $ in continued fraction using $\displaystyle x = \frac{1}{1+ \frac{1}{2+x}} $

$\displaystyle \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr ac{1}{2+..}}}}}}}}}}$

I just sub x value each time it will never end

$\displaystyle \sqrt{3}-1 = \dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr ac{1}{2+..}}}}}}}}}}$

so

$\displaystyle \sqrt{3} = 1 +\dfrac{1}{1+ \dfrac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\d frac{1}{2+\dfrac{1}{1+\dfrac{1}{2+\dfrac{1}{1+\dfr ac{1}{2+..}}}}}}}}}}$

the continued fraction of sqrt{3} [1,2,1,2,1,2,...]
first 6 terms will be (1,2,1,2,1,2)

Okay, I'm a little lost with what you did here:

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

take the second

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

It looks like you have the same thing before and afterwards (unless I"m totally blind).

How did you convert x=Sqrt[3]-1 to x = 1/(1+(1/(2+x))) ? It looks like you just wrote th first one then the second one and only used the second one. How did you connect them? Lastly, the first six terms are (1,2,1,2,1,2) but how do we ensure that that gives us 6 digits of accurracy (1.732050) ?

Also, anyone have any input on Q4 and Q5?

a good accuracy check is that the first 6 or 7 terms of the expansion

not 6 decimal places

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

I called this second one if we solved it for x, we will get
$\displaystyle x=\sqrt{3}-1 $ and another one see

$\displaystyle x = \frac{1}{1+ \frac{1}{2+x}} $

$\displaystyle x = \frac{1}{\frac{2+x+1}{2+x}} $

$\displaystyle x = \frac{2+x}{3+x} $

$\displaystyle x^2 +3x = 2+x $

$\displaystyle x^2 + 2x -2 = $

$\displaystyle x = \frac{-2\mp \sqrt{2^2 -4(1)(-2)}}{2(1)} $

$\displaystyle x = \frac{-2 \mp \sqrt{12}}{2} $

$\displaystyle x = \frac{-2 \mp 2\sqrt{3}}{2} = -1 \mp \sqrt{3} $

so x has two values $\displaystyle \sqrt{3} -1 $ and $\displaystyle -1-\sqrt{3} $

Originally Posted by Amer

not 6 decimal places

$\displaystyle x = \frac{1}{1+\frac{1}{2+x}} $

I called this second one if we solved it for x, we will get
$\displaystyle x=\sqrt{3}-1 $ and another one see

$\displaystyle x = \frac{1}{1+ \frac{1}{2+x}} $

What does this even mean? "Called this second one if we solved it for x" ? I don't see how you got from one line to the other...

omg

Assume that x=Sqrt[3]-1. It can be proven that x = 1/(1+(1/(2+x))). Can somebody prove this?

if I show that $\displaystyle x=\sqrt{3}-1$ is a solution for $\displaystyle x =\frac{1}{1+ \frac{1}{2+x}} $

I'm done, is it ok for now, if it is then

I sub $\displaystyle \sqrt{3}-1$ instead of x and want to show that the left hand side equal to the right hand side

want to show
$\displaystyle \frac{1}{1+ \frac{1}{2+\sqrt{3}-1}}\;\; $ equal to $\displaystyle \;\; \sqrt{3}-1$

$\displaystyle \frac{1}{1+ \frac{1}{2+\sqrt{3}-1}}= \frac{1}{1+ \frac{1}{1+\sqrt{3}}} $

$\displaystyle \frac{1}{1+ \frac{1}{1+\sqrt{3}}} = \frac{1}{\frac{1+ \sqrt{3}}{1+\sqrt{3}} + \frac{1}{1+\sqrt{3}}} $

$\displaystyle \frac{1}{\frac{1+ \sqrt{3}}{1+\sqrt{3}} + \frac{1}{1+\sqrt{3}}} = \frac{1}{\frac{1+\sqrt{3}+1}{1+\sqrt{3}}} $

$\displaystyle \frac{1}{\frac{1+\sqrt{3}+1}{1+\sqrt{3}}} = \frac{1+\sqrt{3}}{2+\sqrt{3}}$

multiply the denominator and nominator by the conjugate of the denominator

$\displaystyle \frac{1+\sqrt{3}}{2+\sqrt{3}} = \left(\frac{1+\sqrt{3}}{2+\sqrt{3}}\right)\left(\f rac{2 - \sqrt{3}}{2 - \sqrt{3}}\right) $

$\displaystyle \left(\frac{1+\sqrt{3}}{2+\sqrt{3}}\right)\left(\f rac{2 - \sqrt{3}}{2 - \sqrt{3}}\right) = \frac{2+2\sqrt{3}-\sqrt{3}-3}{2^2 - (\sqrt{3})^2} $

$\displaystyle \frac{2+2\sqrt{3}-\sqrt{3}-3}{2^2 - (\sqrt{3})^2} = \frac{\sqrt{3} -1}{4 - 3} = \sqrt{3}-1 $

end
if something is not clear point it

Here is an algorithm for Q4 and Q5. (Wikipedia - Methods of computing square roots - subheading Continued fraction expansion)

Thank you amer, I understand that was tedious of you to do but I'm very appreciative. I followed your steps this time but I was lost originally.

undefined, as far as Q4 and Q5 goes, that wikipedia article had my head spinning for that example (114)... I figured 5 and 7 would be much easier.

Somebody should be able to translate this garble for me (as I believe it has the answer right into it) if we can apply it to the questions I had asked:
Square root of 5 - Wikipedia, the free encyclopedia

As far as 7 goes, the book gave us part of the expansion (2,1,1,1,4,1,1,1,...). We just need to find out if the next entry in this expansion is a 2 or a 4 and show how we got there essentially.

Originally Posted by Samson

Thank you amer, I understand that was tedious of you to do but I'm very appreciative. I followed your steps this time but I was lost originally. .

it is not tedious but it is better to determine exactly what you do not understand, and do something not just asking try to understand.and show us some work

Originally Posted by Amer

it is not tedious but it is better to determine exactly what you do not understand, and do something not just asking try to understand.and show us some work

Well for Sqrt[5], the Wiki article shows [2;4,4,4,4,4,...] and they have it shown visually at the top of the page. How did they reach this conclusion though? How did they set it up?

Sqrt[7] i'm lost on as well.

Originally Posted by Samson

Square root of 5 - Wikipedia, the free encyclopedia

This page does not describe how the continued fraction expansion of $\displaystyle \sqrt{5}$ was obtained. (Ah, I see your newest post mentions this.) Best rational approximation is a separate topic, interesting in its own right. The best rational approximation of an irrational number for some upper limit $\displaystyle d$ of denominator will always be either a convergent or a semiconvergent of the continued fraction expansion; the choice between convergent and semiconvergent can be determined using the so-called half rule.

Computing square root continued fractions can be tricky to grasp, but if you review the sources and play around with all the numbers you will eventually see how it works. Post any specific questions.

The description of algorithm in the link I gave you is ideal for computer programmers since it clearly specifies all the variables and how they change from one iteration to the next. On the other hand, it is not immediately clear where the algorithm came from.

You can look at the example worked out in the problem statement of this Project Euler problem (#64) and see if it's any easier to follow.

Originally Posted by undefined

This page does not describe how the continued fraction expansion of $\displaystyle \sqrt{5}$ was obtained. (Ah, I see your newest post mentions this.) Best rational approximation is a separate topic, interesting in its own right. The best rational approximation of an irrational number for some upper limit $\displaystyle d$ of denominator will always be either a convergent or a semiconvergent of the continued fraction expansion; the choice between convergent and semiconvergent can be determined using the so-called half rule.

Computing square root continued fractions can be tricky to grasp, but if you review the sources and play around with all the numbers you will eventually see how it works. Post any specific questions.

The description of algorithm in the link I gave you is ideal for computer programmers since it clearly specifies all the variables and how they change from one iteration to the next. On the other hand, it is not immediately clear where the algorithm came from.

You can look at the example worked out in the problem statement of this Project Euler problem (#64) and see if it's any easier to follow.

I was able to follow along but I don't see why they chose the number '4' to start the expansion off with. I don't know how it relates to Sqrt[23]. Can someone start me off with how they got Sqrt[5]'s expansion? They give the answer but I'd like to know how they got there.

As far as Q5 goes, I need similar help because I don't know how to get to the point to where they left off in the book.