# Truncate continued fractions

Related: Cleaning up decimal numbers

## Background

A continued fraction is a way to represent a real number as a sequence of integers in the following sense:

$$x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}} = [a_0; a_1,a_2,\cdots,a_n]$$

Finite continued fractions represent rational numbers; infinite continued fractions represent irrational numbers. This challenge will focus on finite ones for the sake of simplicity.

Let's take $$\\frac{277}{642}\$$ as an example. It has the following continued fraction:

$$\frac{277}{642} = 0 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{6 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{3}}}}}} = [0;2, 3, 6, 1, 3, 3]$$

If we truncate the continued fraction at various places, we get various approximations of the number $$\\frac{277}{642}\$$:

$$\begin{array}{c|c|c|c} \style{font-family:inherit}{\text{Continued Fraction}} & \style{font-family:inherit}{\text{Fraction}} & \style{font-family:inherit}{\text{Decimal}} & \style{font-family:inherit}{\text{Relative error}}\\\hline [0] & 0/1 & 0.0\dots & 1 \\\hline [0;2] & 1/2 & 0.50\dots & 0.15 \\\hline [0;2,3] & 3/7 & 0.428\dots & 0.0067 \\\hline [0;2,3,6] & 19/44 & 0.4318\dots & 0.00082 \\\hline [0;2,3,6,1] & 22/51 & 0.43137\dots & 0.00021 \\\hline [0;2,3,6,1,3] & 85/197 & 0.431472\dots & 0.000018 \\\hline [0;2,3,6,1,3,3] & 277/642 & 0.4314641\dots & 0 \end{array}$$

These are called convergents of the given number. In fact, the convergents are the best approximations among all fractions with the same or lower denominator. This property was used in a proposed machine number system of rational numbers to find the approximation that fits in a machine word of certain number of bits.

(There are some subtle points around "best approximation", but we will ignore it and just use the convergents. As a consequence, if your language/library has a "best rational approximation" built-in, it is unlikely to correctly solve the following task.)

Given a rational number $$\r\$$ given as a finite continued fraction and a positive integer $$\D\$$, find the best approximation of $$\r\$$ among its convergents so that its denominator does not exceed $$\D\$$.

The continued fraction is guaranteed to be a finite sequence of integers, where the first number is non-negative, and the rest are strictly positive. You may output the result as a built-in rational number or two separate integers. The output fraction does not need to be reduced.

Standard rules apply. The shortest code in bytes wins.

## Test cases

[0, 2, 3, 6, 1, 3, 3], 43 => 3/7
[0, 2, 3, 6, 1, 3, 3], 44 => 19/44
[5, 6, 7], 99 => 222/43

• I've edited the Mathjax slightly to use \cfrac, the recommended usage for continued fractions Apr 6, 2021 at 12:42

# JavaScript (ES6),  72 68   67 bytes

Expects (max_denominator)(seq). Returns [numerator, denominator].

m=>g=([v,...a],n=0,d=1,N=1,D=0)=>(d+=D*v)<=m?g(a,N,D,N*v+n,d):[N,D]


Try it online!

### Commented

m =>             // outer function taking m = maximum denominator
g = (            // inner recursive function taking:
[v,            //   v = next term from the continued fraction
...a],     //   a[] = remaining terms
n = 0,         //   n = previous numerator
d = 1,         //   d = previous denominator
N = 1,         //   N = current numerator
D = 0          //   D = current denominator
) =>             //
(d += D * v)   // we compute the new denominator d = D * v + d
// this results in NaN if v is undefined,
// which forces the comparison to fail
<= m ?         // if it's less than or equal to m:
g(           //   do a recursive call:
a,         //     pass the remaining terms of the continued fraction
N, D,      //     pass the current numerator and denominator
N * v + n, //     pass the new numerator
d          //     pass the new denominator
)            //   end of recursive call
:              // else:
[N, D]       //   we're done: return [N, D]


# J, 25 23 bytes

(]{:@#~0#.>:)2 x:(+%)/\


Try it online!

-2 thanks to Bubbler

## how

We'll use 43 f 0, 2, 3, 6, 1, 3, 3x as an example...

• (+%)/\ For each prefix \, reduce from the right / using the J hook (+%), which adds its left arg to the inverse of its right argument. This returns rational numbers:

0 1r2 3r7 19r44 22r51 85r197 277r642

• 2 x: Convert to pairs:

0   1
1   2
3   7
19  44
22  51
85  197
277 642

• ]...#~... Filter that list for valid denominators with the following mask:

• >: Is each number less than or equal to the left arg:

1 1
1 1
1 1
1 0
1 0
0 0
0 0

• 0#. Convert to a "base 0" number. This will be 1 only for pairs whose 2nd element (denominator) is 1:

1 1 1 0 0 0 0

• Our filtered list becomes:

0   1
1   2
3   7

• {:@ Return the last element.

• 2|&#. can be 0#.. Apr 6, 2021 at 5:43
• @Bubbler Ha! I love it. Apr 6, 2021 at 5:44

# Stax, 14 bytes

╪£pÇUßi⌂Ω♫M⌂░◘


Run and debug it

takes inputs as <max denominator>,<continued fraction>.

## Explanation

|[{r{su+km{Rn^<oH
|[{      m        for each prefix of the continued fraction
r               reverse
{   k          reduce by:
su+            swap, reciprocal and add
{    o  order by:
R       denominator
n^<    lesser than 2nd input + 1 ?
H last element


# Wolfram Language (Mathematica), 47 bytes

Last@*Cases[a_/;Denominator@a<=#]@*Convergents&


Try it online!

-25 bytes from @att

• 47 bytes taking [D][r] (FromContinuedFraction isn't necessary)
– att
Apr 6, 2021 at 5:47

# Charcoal, 38 bytes

ＦＬθ«≔⟦§θι¹⟧ζＦ⮌…θι≔⁺⁺⊟ζ×ζκζζ¿¬›§ζ¹ηＰ⪫ζ/


Try it online! Link is to verbose version of code. Explanation:

ＦＬθ«


Loop over the prefixes.

≔⟦§θι¹⟧ζ


Form a "fraction" of the current element.

Ｆ⮌…θι


Loop over the preceding elements.

≔⁺⁺⊟ζ×ζκζζ


Invert the fraction and add on the element. This is some decidedly tricky coding. The old denominator is popped from the fraction, leaving behind the old numerator as a list of one element. This is vectorised multiplied by the element and added to the denominator, thus making a list of just the new numerator. The old numerator, still in its list, is then list concatenated to it, where it becomes the new denominator.

¿¬›§ζ¹ηＰ⪫ζ/


If the denominator is still small enough, overprint the previous fraction (if any) with the current fraction.

# R, 88 80 bytes

function(x,y,~=cbind,z=1:0~0:1){for(i in x)z=z[,1]*i+z[,2]~z;z[,z[2,]<=y][,1]}


Try it online!

# Haskell, 70 69 bytes

x?m=last[y|y<-f x,y!!1<=m]
f(h:t)=[h,1]:[[a*h+b,a]|[a,b]<-f t]
f[]=[]


Try it online!

The relevant function is (?), which takes as input the continued fraction x (as a list of integers) and the maximum denominator m. The output is a list of integers [numerator,denominator].

## How?

x?m=            -- x=continued fraction, y=maximum denominator
last[         -- return the last
y|y<-f x,   --   convergent of x
y!!1        --   whose denominator (i.e. second element)
<=m       --     is at most m
]

f                   -- helper function for computing convergents
(h:t)=            --   h=first number, t=rest of the continued fraction
[h,1]:          --     the first convergent is h (i.e. h/1)
[[a*h+b,a]      --     the other convergents are h+b/a (i.e. (a*h+b)/a)
|[a,b]<-f t]  --       where a/b ranges over the convergents of t
f[]=[]              -- base case for the empty continued fraction


# Retina, 74 bytes

,
¶$%, ¶ /1¶ +\d+,(\d+)/(.+)$.($2*_$1**)/$1 N$r.*(\d+)
$1 L.+¶(?!.+/)  Try it online! Takes the continued fraction and denominator on separate lines, but link includes test suite that splits on ; for convenience. Explanation: , ¶$%,


Get all prefixes of the continued fraction.

¶
/1¶


Start each prefix with a denominator of 1.

+\d+,(\d+)/(.+)
$.($2*_$1**)/$1


Calculate each resulting rational number from right to left.

N$r.*(\d+)$1


Sort the desired denominator into the list of rational numbers.

L.+¶(?!.+/)


Output the rational number whose denominator is the largest that does not exceed the desired denominator.

# Python 3, 162 bytes

lambda x,y:min((abs(q-g(*x)),q)for q in[g(*x[:i+1])for i in range(len(x))]if q.denominator<=y)[1]
g=lambda v,*k:v+Fraction(*k and(1,g(*k)))
from fractions import*


Try it online!

-28 bytes thanks to ovs

• 179 bytes with a shorter g function.
– ovs
Apr 6, 2021 at 7:59
• 162 bytes by not using a key function and a shorter import.
– ovs
Apr 6, 2021 at 8:07
• @ovs Thanks for the golfs! Apr 6, 2021 at 23:53