Continued Fraction Expansion Problems

Printable View

Show 40 post(s) from this thread on one page

June 8th 2010, 09:11 AM
undefined

Quote:

Originally Posted by Samson

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.

The procedure is the same for Q4 and Q5, so there's no need to treat them separately. If you know how to do one, you know how to do them all.

The 4 is chosen because $4^2 < 23$ and $5^2 > 23$ .
June 8th 2010, 09:17 AM
Amer

Quote:

Originally Posted by Samson

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.

$\sqrt{5}$

the floor of sqrt[5] is 2

$\sqrt{5} = 2 + \sqrt{5} -2 = 2 + \frac{(\sqrt{5}-2)(\sqrt{5}+2)}{\sqrt{5}+2}= 2 + \frac{5 -4}{\sqrt{5}+2} = 2 + \frac{1}{\sqrt{5}+2}$
[2 ;

$\sqrt{5}+2 = 4 + \sqrt{5} - 2$

[2;4

$\sqrt{5} - 2 = \frac{(\sqrt{5}-2)(\sqrt{5}+2)}{\sqrt{5}+2} = \frac{1}{\sqrt{5} +2 }$

$\sqrt{5} +2 = 4 + \sqrt{5} - 2$

[2;4,4

and so on
June 8th 2010, 09:23 AM
Samson

Quote:

Originally Posted by Samson

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.

Can someone explain how they got from

(1/(Sqrt[23]-4)) --> 1 + (Sqrt[23]-3)/7 ?

Source: (from the link - Problem 64)
June 8th 2010, 09:26 AM
Samson

Quote:

Originally Posted by Amer

$\sqrt{5}$

the floor of sqrt[5] is 2

$\sqrt{5} = 2 + \sqrt{5} -2 = 2 + \frac{(\sqrt{5}-2)(\sqrt{5}+2)}{\sqrt{5}+2}= 2 + \frac{5 -4}{\sqrt{5}+2} = 2 + \frac{1}{\sqrt{5}+2}$
[2 ;

$\sqrt{5}+2 = 4 + \sqrt{5} - 2$

[2;4

$\sqrt{5} - 2 = \frac{(\sqrt{5}-2)(\sqrt{5}+2)}{\sqrt{5}+2} = \frac{1}{\sqrt{5} +2 }$

$\sqrt{5} +2 = 4 + \sqrt{5} - 2$

[2;4,4

and so on

So why do you use the 4 in this part (I see why, but I mean how did you decide to use it instead of, say 6 or 8 (6, then -4, or 8 then -6) ?)

$\sqrt{5} +2 = 4 + \sqrt{5} - 2$
June 8th 2010, 09:31 AM
undefined

Quote:

Originally Posted by Samson

Can someone explain how they got from

(1/(Sqrt[23]-4)) --> 1 + (Sqrt[23]-3)/7 ?

Source: (from the link - Problem 64)

First rationalize the denominator. Then express as the sum of an integer and a number between 0 and 1.
June 8th 2010, 09:32 AM
Amer

$\sqrt{7}$ the has the floor 2

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

turned over $\frac{3}{\sqrt{7}+2}$

$\frac{\sqrt{7}+2}{3}$ we say before $\sqrt{7} = 2 +\sqrt{7}-2$

so

$\frac{2+\sqrt{7} -2 +2 }{3} = \frac{4 + \sqrt{7}-2}{3} = 1 + \frac{\sqrt{7} -1}{3}= 1 + \frac{7-1}{3(\sqrt{7}+1)}= \frac{6}{3(\sqrt{7}+1)}$

turned over $\frac{6}{3(\sqrt{7}+1)}$

$\frac{\sqrt{7}+1}{2}$ multiply with the conjugate and so on

i find [2;1
can u continue ?
June 8th 2010, 09:50 AM
Samson

Okay, first off, what's the point of turning it over to get

$\frac{45}{\sqrt{7}+2}$ and $\frac{6}{3(\sqrt{7}+1)}$ (respectively) ?

Then, how did you get from

$\frac{4 + \sqrt{7}-2}{3}$ to $1 + \frac{\sqrt{7} -1}{3}$ ?

Lastly, when did you know to place 2 and 1 in the list like you did ( [2;1 ) ?
June 8th 2010, 10:07 AM
Amer

Quote:

Originally Posted by Samson

Okay, first off, what's the point of turning it over to get

$\frac{45}{\sqrt{7}+2}$ and $\frac{6}{3(\sqrt{7}+1)}$ (respectively) ?

Then, how did you get from

$\frac{4 + \sqrt{7}-2}{3}$ to $1 + \frac{\sqrt{7} -1}{3}$ ?

Lastly, when did you know to place 2 and 1 in the list like you did ( [2;1 ) ?

in fact I'm just doing what in here

the way is for example we want to find continued fraction of sqrt[s]

let f=floor of sqrt[s] ok

then it is trivial that

sqrt[s] = f + sqrt[s] - f, is it ok for now if it then we find the first number

[f;

now we say sqrt[s] = f + (sqrt[s] - f ) the expression in the brackets multiply it with it is conjugate

$\frac{(\sqrt{s}-f)(\sqrt{s}+f)}{\sqrt{s}+f} = \frac{s - f^2}{\sqrt{s}+f}$

turn over it

$\frac{\sqrt{s}+f}{s - f^2}$ we say that sqrt[s] = f + sqrt[s] - f
so

$\frac{\sqrt{s}+f}{s - f^2} = \frac{2f + \sqrt{s} - f }{s - f^2 }$

suppose that 2f/(s-f^2) = r + t/(s-f^2) , r is integer so

$\frac{2f + \sqrt{s} - f }{s - f^2 } = r + \frac{ \sqrt{s} - f +t}{s-f^2}$

[f;r,

$\frac{ \sqrt{s} - f +t}{s-f^2}$ multiply with the conjugate then turn over and so on
June 8th 2010, 10:11 AM
Samson

I'm trying to follow you, but I think if you worked with the explicit example I had pointed out I'd understand. Those are the steps I'm missing.
June 8th 2010, 10:20 AM
Amer

I worked it in sqrt[7] and sqrt[5]

read them
hope u will get the answer
June 8th 2010, 10:24 AM
Samson

Quote:

Originally Posted by Amer

I worked it in sqrt[7] and sqrt[5]

read them
hope u will get the answer

I'm asking explicitly if you or someone can explain how you got from

$\frac{4 + \sqrt{7}-2}{3}$ to $1 + \frac{\sqrt{7} -1}{3}$ ?
June 8th 2010, 10:33 AM
undefined

Quote:

Originally Posted by Samson

I'm asking explicitly if you or someone can explain how you got from

$\frac{4 + \sqrt{7}-2}{3}$ to $1 + \frac{\sqrt{7} -1}{3}$ ?

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

Note that $\left\lfloor \frac{\sqrt{7}+2}{3} \right\rfloor = 1$ and $0 < \frac{\sqrt{7} -1}{3} < 1$ .
June 8th 2010, 10:45 AM
Samson

Quote:

Originally Posted by undefined

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

Note that $\left\lfloor \frac{\sqrt{7}+2}{3} \right\rfloor = 1$ and $0 < \frac{\sqrt{7} -1}{3} < 1$ .

Thank you for that explanation, that is exactly what I needed. I will try to apply this, but if anyone wants to add anymore onto either Sqrt[5] or Sqrt[7], please feel free. I'll be logging on later and it would be great if I had something to check my work against!
July 2nd 2010, 03:44 AM
Samson

Quote:

Originally Posted by Samson

Hello all,

Can anyone provide the complete solution to either one of these? I know that Latex has been down for a while but now that its back up, I'm hoping somebody might be able to provide these.

*Note: If the users that helped give part of it before are still available, it would be totally awesome if you're able to complete the solutions you started! I'd really appreciate it! lol, I've been trying to see the end of the tunnel for 2 weeks on just these 2 problems!

Can anybody help with these? It's been floating up here for nearly a month lol! Anyone have these solutions?
July 3rd 2010, 11:51 PM
undefined

Here's my code:

Code:

import java.util.ArrayList; public class ContFracSqrt { static boolean v=true; // verbosity public static void main(String[] args) { print(cfe(5)); } static void print(ArrayList<Integer> a) { int i; String s=a.toString(); if(a.size()>1) for(i=2;;i++) if(s.charAt(i)==',') { s=s.substring(0,i)+"; ("+s.substring(i+2); s=s.substring(0,s.length()-1)+")]"; break; } System.out.println(s); } static ArrayList<Integer> cfe(int n) { ArrayList<Integer> x=new ArrayList<Integer>(); int a=(int)Math.sqrt(n),b=a,c=1,d,e,f,g; x.add(a); if(a*a==n) return x; if(v) System.out.println("\\sqrt{"+n+"}="+a+"+\\dfrac{\\sqrt{"+n+"}-"+a+"}{1}"); if(v) System.out.print("\\dfrac{1}{\\sqrt{"+n+"}-"+a+"}="); while(true) { d=c; c=n-b*b; g=gcd(c,d); c/=g; d/=g; b=-b; f=a-c; for(e=0;b<=f;e++) b+=c; x.add(e); if(v) System.out.println(e+"+\\dfrac{\\sqrt{"+n+"}-"+b+"}{"+c+"}"); if(b==a&&c==1) return x; if(v) System.out.print("\\dfrac{"+c+"}{\\sqrt{"+n+"}-"+b+"}="); } } static int gcd(int a,int b) { return (b==0)?a:gcd(b,a%b); } }

Which gives output for $\displaystyle \sqrt{5}$ :

$\sqrt{5}=2+\dfrac{\sqrt{5}-2}{1}$

$\dfrac{1}{\sqrt{5}-2}=4+\dfrac{\sqrt{5}-2}{1}$

$[2; (4)]$

and for $\displaystyle \sqrt{7}$ :

$\sqrt{7}=2+\dfrac{\sqrt{7}-2}{1}$

$\dfrac{1}{\sqrt{7}-2}=1+\dfrac{\sqrt{7}-1}{3}$

$\dfrac{3}{\sqrt{7}-1}=1+\dfrac{\sqrt{7}-1}{2}$

$\dfrac{2}{\sqrt{7}-1}=1+\dfrac{\sqrt{7}-2}{3}$

$\dfrac{3}{\sqrt{7}-2}=4+\dfrac{\sqrt{7}-2}{1}$

$[2; (1, 1, 1, 4)]$

Let me know how this works for you. I decided against ASCII mode since LaTeX is so much nicer.

Show 40 post(s) from this thread on one page

All times are GMT -8. The time now is 02:04 PM.

Copyright © 2005-2013 Math Help Forum. All rights reserved.

Copyright © 2005-2013 Math Help Forum. All rights reserved.