Continued fraction convergents: Difference between revisions

Content added Content deleted

Inline

Revision as of 23:29, 31 January 2024

Given a positive real number, if we truncate its continued fraction representation at a certain depth, we obtain a rational approximation to the real number. The sequence of successively better such approximations is its convergent sequence.

Problem:

Given a positive rational number ${\frac {m}{n}}$ , specified by two positive integers $m,n$ , output its entire sequence of convergents.
Given a quadratic real number ${\frac {b{\sqrt {a}}+m}{n}}>0$ , specified by integers $a,b,m,n$ , where $a$ is not a perfect square, output the first $k$ convergents when given a positive number $k$ .

The output format can be whatever is necessary to represent rational numbers, but it probably should be a 2-tuple of integers.

For example, given $a=2,b=1,m=0,n=1$ , since

{\sqrt {2}}=1+{\cfrac {1}{2+{\cfrac {1}{2+{\cfrac {1}{2+\ddots }}}}}}

the program should output

(1,1),(3,2),(7,5),(17/12),(41/29),\dots

.

A simple check is to do this for the golden ratio ${\frac {{\sqrt {5}}-1}{2}}$ , that is, $a=5,b=1,m=-1,n=2$ , which would just output the Fibonacci sequence.

@@ Line 1: / Line 1: @@
 {{Task}}
-Given a positive real number, if we truncate its continued fraction representation at a certain depth, we obtain a rational approximation to the real number. The sequence of successively better such approximations is its convergent sequence.
+Given a positive real number, if we truncate its [[continued fraction]] representation at a certain depth, we obtain a rational approximation to the real number. The sequence of successively better such approximations is its convergent sequence.
 Problem:
 * Given a positive rational number <math>\frac mn</math>, specified by two positive integers <math>m, n</math>, output its entire sequence of convergents.
-* Given a quadratic real number <math>\frac{\sqrt{a} + m}{n}</math>, specified by three positive integers <math>a, m, n </math>, where <math>a</math> is not a perfect square, output the first <math>k</math> convergents when given a positive number <math>k</math>.
+* Given a quadratic real number <math>\frac{b\sqrt{a} + m}{n} > 0</math>, specified by integers <math>a, b, m, n </math>, where <math>a</math> is not a perfect square, output the first <math>k</math> convergents when given a positive number <math>k</math>.
+The output format can be whatever is necessary to represent rational numbers, but it probably should be a 2-tuple of integers.
+For example, given <math>a=2, b=1, m = 0, n = 1</math>, since<math display="block">\sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots}}}</math>the program should output <math>(1, 1), (3,2), (7,5), (17/12), (41/29), \dots</math>.
+A simple check is to do this for the golden ratio <math>\frac{\sqrt{5}-1}{2}</math>, that is, <math>a=5, b=1, m = -1, n = 2 </math>, which would just output the [[Fibonacci sequence]].