Sep 15, 2009

Marvelous Mental Arithmetic Tricks

http://www.scribd.com/doc/18284009/Marvelous-Mental-Arithmetic-Tricks
No comments:

Sep 9, 2009

sodaconstructor: fantastic

http://sodadome.com/sodaconstructor/index.htm
No comments:

Sep 7, 2009

Jeff Erickson's Algorithms Course Materials

Thank you Jeff Erickson for the free materials!!!!

http://compgeom.cs.uiuc.edu/~jeffe//teaching/algorithms/

Algorithms Course Materials

by Jeff Erickson
August 2009 revision

This page contains all my lecture notes for the algorithms classes required for all computer science undergraduate and graduate students at the University of Illinois, Urbana-Champaign. I have taught incarnations of this course eight times: Spring 1999, Fall 2000, Spring 2001, Fall 2002, Spring 2004, Fall 2005, Fall 2006, Spring 2007, Fall 2008, and Spring 2009. These notes are numbered roughly in the order I used them in my undergraduate class, with (lettered) notes containing sprinkled in reasonable places. More advanced material is indicated by the symbol ※. More information about these notes is available after the notes themselves.

A large collection of old homeworks and exams follows the lecture notes. Most of these homework and exam problems also appear at the ends of the appropriate lecture notes. Except for various Homework Zeros, which are solely my fault, most of the homework problems were written by my teaching assistants:

Aditya Ramani, Alina Ene, Amir Nayyeri, Asha Seetharam, Ben Moseley, Brian Ensink, Chris Neihengen, Dan Bullok, Dan Cranston, Johnathon Fischer, Ekta Manaktala, Erin Wolf Chambers, Igor Gammer, Gio Kao, Kevin Milans, Kevin Small, Lan Chen, Michael Bond, Mitch Harris, Nick Hurlburt, Nitish Korula, Reza Zamani-Nasab, Rishi Talreja, Rob McCann, Shripad Thite, and Yasu Furakawa.
Please do not ask me for solutions. If you're a student, you will (usually) learn more from trying to solve a problem and failing than by reading the answer. If you really need help, ask your instructor, your TAs, and/or your fellow students. If you're an instructor, you really shouldn't assign problems that you can't solve yourself! (Because I don't always follow my own advice, some of the problems are buggy, especially in older homeworks and exams. I've tried to keep the buggy problems out of the lecture notes themselves.)

More recent version of these notes, along with current homework and exams, may be available at the official sites for the undergraduate and/or graduate algorithms classes at UIUC.

Feedback of any kind is always welcome, especially bug reports. I would particularly appreciate hearing from anyone outside UIUC who finds these notes useful (or useless)!

Copyright. Except as indicated otherwise, all material linked from this web page is Copyright © 1999–2009 Jeff Erickson. Anyone may freely download, print, copy, and/or distribute anything on this page, either electronically or on paper. However, nothing on this page may be sold in any form for more than the actual cost of printing and/or reproduction. For example, you are welcome to make local copies on your own web server, but you are not allowed to require an access fee (such as tuition) to view your local copy; that's the same as selling it. If you distribute these notes, please give me proper credit and please include a pointer to this web page (http://www.cs.uiuc.edu/~jeffe/teaching/algorithms). If you're a lawyer, read the legalese.

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License.

You know, I could write a book.
And this book would be thick enough to stun an ox.
— Laurie Anderson, "Let X=X", Big Science (1982)

Everything

If we are ready to tolerate everything as understood, there is nothing left to explain; while if we sourly refuse to take anything, even tentatively, as clear, no explanation can be given. What intrigues us as a problem, and what will satisfy us as a solution, will depend upon the line we draw between what is already clear and what needs to be clarified.
— Nelson Goodman, Fact, Fiction & Forecast (1955)

Lecture Notes

The problem is that we attempt to solve the simplest questions cleverly, thereby rendering them unusually complex.
One should seek the simple solution.
— Anton Pavlovich Chekhov (c. 1890)

Homeworks, Exams, and Head-Banging Sessions

More Information

Caveat Lector. Some of these lecture notes have been used less often than others and are therefore (sometimes considerably) less complete/polished. Almost all of these notes contain more than one lecture's worth of material. In a typical 75-minute lecture, I tend to cover 4-5 pages of material—a bit more if I'm lecturing to grad students than to undergraduates. Your mileage may vary! (Arguably, that means that as I continue to add material, the label "lecture notes" becomes less and less accurate.)

Alternate sources. My UIUC colleague Sariel Har-Peled maintains his own collection of algorithms lecture notes, which heavily overlap mine, although our presentation styles and specific topical choices are different, sometimes radically so. Choice is good! For people who really prefer dead trees, I recommend the textbooks by Dasgupta, Papadimitriou, and Vazirani; by Kleinberg and Tardos; and (especially for stunning oxen) by Cormen, Leiserson, Rivest, and Stein. An increasing amount of basic algorithmic material can be found at the Source of All Lies. Many more references are listed in the cover material for the lecture notes.

Drawing tools. Most of the figures were drawn with OmniGraffle, but a few very old figures were drawn with xfig, and a few particularly complex figures were drawn with either Freehand or Illustrator. The map on the first page of the maxflow/mincut notes was copied from Lex Schrijver's excellent survey "On the history of combinatorial optimization (till 1960)"; the original map is from a US Government work in the public domain.

Am I writing a textbook? No. All textbooks suck. (Partly that's because of the unethical rapacious profitable business practices of (most) textbook publishers—these notes will always be freely available. But also, I've never seen a textbook on any topic that I'd be willing to teach from for more than a few weeks; that's why I wrote these notes in the first place.) In particular, if these notes ever became a textbook, they would immediately suck. (Determining whether they already suck is an illuminating exercise for the reader.) Besides, have you ever talked to someone who's actually written a textbook? Do you realize how much work is involved?! No way, man. Not for me.


No comments:

Aug 26, 2009

Continued Fraction -- from Wolfram MathWorld

http://mathworld.wolfram.com/ContinuedFraction.html

Continued Fraction
DOWNLOAD Mathematica Notebook EXPLORE THIS TOPIC IN the MathWorld ClassroomContribute to this entry

A "general" continued fraction representation of a real number x is one of the form

x=a_0+(b_1)/(a_1+(b_2)/(a_2+(b_3)/(a_3+...))),
(1)

where a_0, a_1, ... and b_1, b_2 are integers. Such representations are sometimes written in the form

x=a_0+(b_1)/(a_1+)(b_2)/(a_2+)...
(2)

for compactness.

Wallis first used the term "continued fraction" in his Arithmetica infinitorum of 1653 (Havil 2003, p. 93), although other sources list the publication date as 1655 or 1656. An archaic word for a continued fraction is anthyphairetic ratio.

While continued fractions are not the only possible representation of real numbers in terms of a sequence of integers (others include the decimal expansion and the so-called Engel expansion), they are a very common such representation that arises most frequently in number theory.

The simple continued fraction representation (which is usually what is meant when the term "continued fraction" is used without qualification) of a number x is given by

x=a_0+1/(a_1+1/(a_2+1/(a_3+...))),
(3)

where a_0, a_1, a_2, ... are again integers and a_1,a_2,...>0. Simple continued fractions can be written in a compact abbreviated notation as

x=[a_0,a_1,a_2,a_3,...].
(4)

Some care is needed, since some authors begin indexing the terms at a_1 instead of a_0, causing the parity of certain fundamental results in continued fraction theory to be reversed. The first n terms of the simple continued fraction of a number x can be computed in Mathematica using the command ContinuedFraction[x, n].

Continued fractions with closed forms are given in the following table (cf. Euler 1775).

continued fraction value approximate Sloane
0+1/(1+1/(2+1/(3+1/(4+...)))) (I_1(2))/(I_0(2)) 0.697774... A052119
1+2/(3+4/(5+6/(7+8/(9+...)))) (sqrt(e)-1)^(-1) 1.541494... A113011
1/(1+2/(2+3/(3+4/(4+...)))) (e-1)^(-1) 0.581976... A073333

Starting the indexing of a continued fraction with a_0,

a_0=|_x_|
(5)

is the integer part of x, where |_x_| is the floor function,

a_1=|_1/(x-a_0)_|
(6)

is the integral part of the reciprocal of x-a_0,

a_2=|_1/(1/(x-a_0)-a_1)_|
(7)

is the integral part of the reciprocal of the remainder, etc. Writing the remainders according to the recurrence relation

r_0 = x
(8)
r_n = 1/(r_(n-1)-a_(n-1))
(9)

gives the concise formula

a_n=|_r_n_|.
(10)

The quantities a_n are called partial quotients, and the quantity obtained by including n terms of the continued fraction

c_n = (p_n)/(q_n)
(11)
= [a_0,a_1,...,a_n]
(12)
= a_0+1/(a_1+1/(a_2+1/(...+1/(a_n))))
(13)

is called the nth convergent. For example, consider the computation of the continued fraction of pi, given by pi=[3,7,15,1,292,1,1,...].

term value PQs convergent value
a_0 |_pi_|=3 [3] 3 3.00000
a_1 |_1/(pi-3)_|=7 [3,7] (22)/7 3.14286
a_2 |_1/(1/(pi-3)-7)_|=15 [3,7,15] (333)/(106) 3.14151

Continued fractions provide, in some sense, a series of "best" estimates for an irrational number. Functions can also be written as continued fractions, providing a series of better and better rational approximations. Continued fractions have also proved useful in the proof of certain properties of numbers such as e and pi (pi). Because quadratic surds have periodic continued fractions (e.g., Pythagoras's constant sqrt(2)=1.41421356... has continued fraction [1, 2, 2, 2, 2, ...]), an exact representation for a tabulated numerical value can sometimes be found if it is suspected to represent an unknown quadratic surd.

Continued fractions are also useful for finding near commensurabilities between events with different periods. For example, the Metonic cycle used for calendrical purposes by the Greeks consists of 235 lunar months which very nearly equal 19 solar years, and 235/19 is the sixth convergent of the ratio of the lunar phase (synodic) period and solar period (365.2425/29.53059). Continued fractions can also be used to calculate gear ratios, and were used for this purpose by the ancient Greeks (Guy 1990).

Let the continued fraction for x be written [a_0,a_1,...,a_n]. Then the limiting value is almost always Khinchin's constant

K=lim_(n->infty)(a_1a_2...a_n)^(1/n)=2.68545...
(14)

(Sloane's A002210).

Similarly, taking the nth root of the denominator q_n of the nth convergent as n->infty almost always gives the Khinchin-Lévy constant

lim_(n->infty)q_n^(1/n)=e^(pi^2/(12ln2))=3.275823...
(15)

(Sloane's A086702).

Let P_n/Q_n be convergents of a nonsimple continued fraction. Then

P_(-1)=1 Q_(-1)=0
(16)
P_0=a_0 Q_0=1
(17)

and subsequent terms are calculated from the recurrence relations

P_j=a_jP_(j-1)+b_jP_(j-2)
(18)
Q_j=a_jQ_(j-1)+b_jQ_(j-2)
(19)

for j=1, 2, ..., n. It is also true that

P_nQ_(n-1)-P_(n-1)Q_n=(-1)^(n-1)product_(k=1)^nb_k.
(20)

The error in approximating a number by a given convergent is roughly the multiplicative inverse of the square of the denominator of the first neglected term.

A finite simple continued fraction representation terminates after a finite number of terms. To "round" a continued fraction, truncate the last term unless it is +/-1, in which case it should be added to the previous term (Gosper 1972, Item 101A). To take one over a continued fraction, add (or possibly delete) an initial 0 term. To negate, take the negative of all terms, optionally using the identity

[-a,-b,-c,-d,...]=[-a-1,1,b-1,c,d,...].
(21)

A particularly beautiful identity involving the terms of the continued fraction is

([a_0,a_1,...,a_n])/([a_0,a_1,...,a_(n-1)])=([a_n,a_(n-1),...,a_1,a_0])/([a_n,a_(n-1),...,a_1]).
(22)

Finite simple fractions represent rational numbers and all rational numbers are represented by finite continued fractions. There are two possible representations for a finite simple fraction:

[a_0,...,a_n]={[a_0,...,a_(n-1),a_n-1,1] for a_n>1; [a_0,...,a_(n-2),a_(n-1)+1] for a_n=1.
(23)

On the other hand, an infinite simple fraction represents a unique irrational number, and each irrational number has a unique infinite continued fraction.

Consider the convergents c_n=p_n/q_n of a simple continued fraction, and define

p_(-2)=0 q_(-2)=1
(24)
p_(-1)=1 q_(-1)=0
(25)
p_0=a_0 q_0=1.
(26)

Then subsequent terms can be calculated from the recurrence relations

p_n=a_np_(n-1)+p_(n-2)
(27)
q_n=a_nq_(n-1)+q_(n-2).
(28)

The continued fraction fundamental recurrence relation for simple continued fractions is

p_nq_(n-1)-p_(n-1)q_n=(-1)^(n+1).
(29)

It is also true that if a_0!=0,

(p_n)/(p_(n-1)) = [a_n,a_(n-1),...,a_0]
(30)
(q_n)/(q_(n-1)) = [a_n,...,a_1].
(31)

Furthermore,

(p_n)/(q_n)=(p_(n+1)-p_(n-1))/(q_(n+1)-q_(n-1)).
(32)

Also, if a convergent c_n=p_n/q_n>1, then

(q_n)/(p_n)=[0,a_0,a_1,...,a_n].
(33)

Similarly, if c_n=p_n/q_n<1, then a_0=0 and

(q_n)/(p_n)=[a_1,...,a_n].
(34)

The convergents c_n=p_n/q_n also satisfy

c_n-c_(n-1) = ((-1)^(n+1))/(q_nq_(n-1))
(35)
c_n-c_(n-2) = (a_n(-1)^n)/(q_nq_(n-2)).
(36)
CFConvergents

Plotted above on semilog scales are c_n-pi (n even; left figure) and pi-c_n (n odd; right figure) as a function of n for the convergents of pi. In general, the even convergents c_(2n) of an infinite simple continued fraction for a number x form an increasing sequence, and the odd convergents c_(2n+1) form a decreasing sequence (so any even convergent is less than any odd convergent). Summarizing,

c_0<c_2<c_4<...<c_(2n-2)<c_(2n)<...<x
(37)
x<...<c_(2n+1)<c_(2n-1)<c_5<c_3<c_1.
(38)

Furthermore, each convergent for n>=3 lies between the two preceding ones. Each convergent is nearer to the value of the infinite continued fraction than the previous one. In addition, for a number x=[a_0,a_1,...],

1/((a_(n+1)+2)q_n^2)<|x-(p_n)/(q_n)|<1/(a_(n+1)q_n^2).
(39)

The square root of a squarefree integer has a periodic continued fraction of the form

sqrt(n)=[a_0,a_1,...,a_n,2a_0^_]
(40)

(Rose 1994, p. 130). Furthermore, if D is not a square number, then the terms of the continued fraction of sqrt(D) satisfy

0<a_n<2sqrt(D).
(41)

Logarithms log_(b_1)b_0 can be computed by defining b_2, ... and the positive integer n_1, ... such that

b_1^(n_1)<b_0<b_1^(n_1+1) b_2=(b_0)/(b_1^(n_1))
(42)
b_2^(n_2)<b_1<b_2^(n_2+1) b_3=(b_1)/(b_2^(n_2))
(43)

and so on. Then

log_(b_1)b_0=[n_1,n_2,n_3,...].
(44)
ContinuedFractionLattice

A geometric interpretation for a reduced fraction y/x consists of a string through a lattice of points with ends at (1,0) and (x,y) (Klein 1896, 1932; Steinhaus 1999, p. 40; Gardner 1984, pp. 210-211, Ball and Coxeter 1987, pp. 86-87; Davenport 1992). This interpretation is closely related to a similar one for the greatest common divisor. The pegs it presses against (x_i,y_i) give alternate convergents y_i/x_i, while the other convergents are obtained from the pegs it presses against with the initial end at (0,1). The above plot is for e-2, which has convergents 0, 1, 2/3, 3/4, 5/7, ....

Continued fractions can be used to express the positive roots of any polynomial equation. Continued fractions can also be used to solve linear Diophantine equations and the Pell equation. Euler showed that if a convergent series can be written in the form

c_1+c_1c_2+c_1c_2c_3+...,
(45)

then it is equal to the continued fraction

(c_1)/(1-(c_2)/(1+c_2-(c_3)/(1+c_3-...)))
(46)

(Borwein et al. 2004, p. 30).

Gosper has invented an algorithm for performing analytic addition, subtraction, multiplication, and division using continued fractions. It requires keeping track of eight integers which are conceptually arranged at the polyhedron vertices of a cube. Although this algorithm has not appeared in print, similar algorithms have been constructed by Vuillemin (1987) and Liardet and Stambul (1998).

Gosper's algorithm for computing the continued fraction for (ax+b)/(cx+d) from the continued fraction for x is described by Gosper (1972), Knuth (1998, Exercise 4.5.3.15, pp. 360 and 601), and Fowler (1999). (In line 9 of Knuth's solution, X_k<-|_A/C_| should be replaced by X_k<-min(|_A/C_|,|_(A+B)/(C+D)_|).) Gosper (1972) and Knuth (1981) also mention the bivariate case (axy+bx+cy+d)/(Axy+Bx+Cy+D).

SEE ALSO: Continued Fraction Constant, Decimal Expansion, Engel Expansion, Gaussian Brackets, Hurwitz's Irrational Number Theorem, Khinchin's Constant, Khinchin-Lévy Constant, Lagrange's Continued Fraction Theorem, Lamé's Theorem, Lehmer Continued Fraction, Lochs Theorem, Padé Approximant, Partial Quotient, Periodic Continued Fraction, Pi, Quadratic Surd, Quotient-Difference Algorithm, Ramanujan Continued Fractions, Rogers-Ramanujan Continued Fraction, Segre's Theorem, Trott's Constant

REFERENCES:

Abramowitz, M. and Stegun, I. A. (Eds.). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 19, 1972.

Acton, F. S. "Power Series, Continued Fractions, and Rational Approximations." Ch. 11 in Numerical Methods That Work, 2nd printing. Washington, DC: Math. Assoc. Amer., 1990.

Adamchik, V. "Limits of Continued Fractions and Nested Radicals." Mathematica J. 2, 54-57, 1992.

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 54-57 and 86-87, 1987.

Berndt, B. C. and Gesztesy, F. (Eds.). Continued Fractions: From Analytic Number Theory to Constructive Approximation, A Volume in Honor of L. J. Lange. Providence, RI: Amer. Math. Soc., 1999.

Beskin, N. M. Fascinating Fractions. Moscow: Mir Publishers, 1980.

Borwein, J.; Bailey, D.; and Girgensohn, R. Experimentation in Mathematics: Computational Paths to Discovery. Wellesley, MA: A K Peters, 2004.

Brezinski, C. History of Continued Fractions and Padé Approximants. New York: Springer-Verlag, 1980.

Conway, J. H. and Guy, R. K. "Continued Fractions." In The Book of Numbers. New York: Springer-Verlag, pp. 176-179, 1996.

Courant, R. and Robbins, H. "Continued Fractions. Diophantine Equations." §2.4 in Supplement to Ch. 1 in What Is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed. Oxford, England: Oxford University Press, pp. 49-51, 1996.

Cuyt, A.; Petersen, A. B.; Verdonk, B.; Waadeland, H.; and Jones, W. B. Handbook of Continued Fractions for Special Functions. New York: Springer, 2008.

Davenport, H. §IV.12 in The Higher Arithmetic: An Introduction to the Theory of Numbers, 6th ed. New York: Cambridge University Press, 1992.

Dunne, E. and McConnell, M. "Pianos and Continued Fractions." Math. Mag. 72, 104-115, 1999.

Euler, L. "On the Formulation of Continued Fractions." Delivered to the St. Petersburg Academy, Sept. 4, 1775. Published as Euler, L. "De formatione fractionum continuarum." Acta Academiae Scientarum Imperialis Petropolitinae 3, 3-29, 1782. Republished in Euler, L. Opera Omnia, Ser. 1: Opera mathematica, Vol. 15. Basel, Switzerland: Birkhäuser, 1992. http://arxiv.org/abs/math.HO/0508227/.

Euler, L. Introduction to Analysis of the Infinite, Book I. New York: Springer-Verlag, 1980.

Fowler, D. H. The Mathematics of Plato's Academy: A New Reconstruction, 2nd ed. Oxford, England: Oxford University Press, 1999.

Fowler, D. "Wallis and Number Columns by David Fowler." http://mathforum.org/epigone/math-history-list/sterbloirerm.

Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 210-211, 1984.

Gosper, R. W. "Continued fractions query." math-fun@cs.arizona.edu posting, Dec. 27, 1996.

Gosper, R. W. Item 101a in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 37-39, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/cf.html#item101a.

Gosper, R. W. Item 101b in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, pp. 39-44, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/cf.html#item101b.

Graham, R. L.; Knuth, D. E.; and Patashnik, O. "Continuants." §6.7 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 301-309, 1994.

Guy, R. K. "Continued Fractions" §F20 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, p. 259, 1994.

Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, 2003.

Jacobson, M. J. Jr.; Lukes, R. F.; and Williams, H. C. "An Investigation of Bounds for the Regulator of Quadratic Fields." Experiment. Math. 4, 211-225, 1995.

Khinchin, A. Ya. Continued Fractions. New York: Dover, 1997.

Kimberling, C. "Continued Fractions." http://faculty.evansville.edu/ck6/integer/contfr.html.

Klein, F. Ausgewählte Kapitel der Zahlentheorie I. Göttingen, Germany: n.p., 1896.

Klein, F. Elementary Number Theory. New York, p. 44, 1932.

Kline, M. Mathematical Thought from Ancient to Modern Times. Oxford, England: Oxford University Press, 1990.

Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, p. 316, 1998.

Liardet, P. and Stambul, P. "Algebraic Computation with Continued Fractions." J. Number Th. 73, 92-121, 1998.

Liberman, H. Simple Continued Fractions: An Elementary to Research Level Approach. SMD Stock Analysts, 2003.

Lorentzen, L. and Waadeland, H. Continued Fractions with Applications. Amsterdam, Netherlands: North-Holland, 1992.

Moore, C. D. An Introduction to Continued Fractions. Washington, DC: National Council of Teachers of Mathematics, 1964.

Olds, C. D. Continued Fractions. New York: Random House, 1963.

Perron, O. Die Lehre von den Kettenbrüchen, 3. verb. und erweiterte Aufl. Stuttgart, Germany: Teubner, 1954-57.

Pettofrezzo, A. J. and Bykrit, D. R. Elements of Number Theory. Englewood Cliffs, NJ: Prentice-Hall, 1970.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Evaluation of Continued Fractions." §5.2 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 163-167, 1992.

Riesel, H. "Continued Fractions." Appendix 8 in Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 327-342, 1994.

Rockett, A. M. and Szüsz, P. Continued Fractions. New York: World Scientific, 1992.

Rose, H. E. A Course in Number Theory, 2nd ed. Oxford, England: Oxford University Press, 1994.

Rosen, K. H. Elementary Number Theory and Its Applications. New York: Addison-Wesley, 1980.

Schur, I. "Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche." Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Klasse, pp. 302-321, 1917.

Sloane, N. J. A. Sequences A000037/M0613, A002210/M1564, A013943, A052119, A086702, and A113011 in "The On-Line Encyclopedia of Integer Sequences."

Steinhaus, H. Mathematical Snapshots, 3rd ed. New York: Dover, pp. 39-42, 1999.

Van Tuyl, A. L. "Continued Fractions." http://archives.math.utk.edu/articles/atuyl/confrac/.

Vuillemin, J. "Exact Real Computer Arithmetic with Continued Fractions." INRIA Report 760. Le Chesnay, France: INRIA, Nov. 1987. http://www.inria.fr/RRRT/RR-0760.html.

Wagon, S. "Continued Fractions." §8.5 in Mathematica in Action. New York: W. H. Freeman, pp. 263-271, 1991.

Wall, H. S. Analytic Theory of Continued Fractions. New York: Chelsea, 1948.

Wallis, J. Arithmetica Infinitorum. Oxford, England, 1656.

Weisstein, E. W. "Books about Continued Fractions." http://www.ericweisstein.com/encyclopedias/books/ContinuedFractions.html.

Williams, H. C. "A Numerical Investigation into the Length of the Period of the Continued Fraction Expansion of sqrt(D)." Math. Comput. 36, 593-601, 1981.




CITE THIS AS:

Weisstein, Eric W. "Continued Fraction." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ContinuedFraction.html


No comments:
Subscribe to: Posts (Atom)