8
$\begingroup$

Say I have a reduced fraction where the numerator and denominator can only be integers:

$$ \frac{1071283}{28187739} $$

and I want to reduce it more, accepting the lose of precision.

I could just remove an equal numbers of integers from the right:

$$ \frac{107}{2818} $$

However playing around with it shows me that I can easily find a fraction that contains the same number of integers but has lost less precision compared to the original fraction:

$$ \frac{108}{2842} $$

How can I reduce a fraction of integers and lose the minimal amount of precision?

$\endgroup$
5
  • 7
    $\begingroup$ What you need are simple continued fractions. This gives you the best approximations with limitied size of denominator and numerator. $\endgroup$
    – Peter
    Feb 22, 2022 at 8:51
  • 3
    $\begingroup$ $16/421\,$ is even closer. Lookup continued fraction convergents. $\endgroup$
    – dxiv
    Feb 22, 2022 at 8:51
  • 1
    $\begingroup$ Just play with wolframalpha.com/… $\endgroup$
    – Claude Leibovici
    Feb 22, 2022 at 9:03
  • 1
    $\begingroup$ See math.stackexchange.com/a/2540421/589 $\endgroup$
    – lhf
    Feb 22, 2022 at 10:26
  • 2
    $\begingroup$ A binary search via Farey mediants is quick and easy to remember. $\endgroup$
    – Bill Dubuque
    Feb 22, 2022 at 21:00

2 Answers 2

Reset to default
7
$\begingroup$

As suggested in comments, use the continued fraction decomposition. $$\frac{1071283}{28187739} = \frac{1}{26+\frac{1}{3+\frac{1}{4+\frac{1}{1+\frac{1}{9+ \frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{1+\frac{1}{1+ \frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{14+\frac{1}{2+ \frac{1}{3}}}}}}}}}}}}}}}}$$ Halting the decomposition sooner will give you a good approximation, among the fractions with denominators less than the one of the fraction.This gives the approximations $$\left(\frac{1}{26} , \frac{3}{79} , \frac{13}{342} , \frac{16}{421} , \frac{157}{4131} , \frac{173}{4552} , \frac{676}{17787} , \frac{849}{22339} , \frac{1525}{40126},...\right)$$ So for example, $$\frac{157}{4131} = \frac{1}{26+\frac{1}{3+\frac{1}{4+\frac{1}{1+\frac{1}{9}}}}}$$

$\endgroup$
1
  • 2
    $\begingroup$ Let me add that the following maxima command gives the tex code for the big continued fraction: tex(cfdisrep(cf(1071283/28187739))); $\endgroup$
    – coudy
    Feb 22, 2022 at 15:24
5
$\begingroup$

The Stern-Brocot Tree gives a sequence of best rational approximations to a number in the sense that if $a/b$ is a rational approximation to $x$ which is not in the sequence, then the sequence contains a closer approximation to $x$ which has a denominator at most equal to $b$. The Stern-Brocot sequence includes the continued fraction convergents so it is in a sense more general; you have more choices. In the case of $1071283/28187739$, the sequence consists of $72$ numbers. The Wikipedia article includes an algorithm for generating this sequence.

$$\left\{1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5},\frac{1}{6},\frac{1}{7},\frac{1}{8} ,\frac{1}{9},\frac{1}{10},\frac{1}{11},\frac{1}{12},\frac{1}{13},\frac{1}{14},\frac{1}{15 },\frac{1}{16},\frac{1}{17},\frac{1}{18},\frac{1}{19},\frac{1}{20},\frac{1}{21},\frac{1}{ 22},\frac{1}{23},\frac{1}{24},\frac{1}{25},\frac{1}{26},\frac{1}{27},\frac{2}{53},\frac{3 }{79},\frac{4}{105},\frac{7}{184},\frac{10}{263},\frac{13}{342},\frac{16}{421},\frac{29}{ 763},\frac{45}{1184},\frac{61}{1605},\frac{77}{2026},\frac{93}{2447},\frac{109}{2868},\frac{125}{3289},\frac{141}{3710},\frac{157}{4131},\frac{173}{4552},\frac{330}{8683},\frac{5 03}{13235},\frac{676}{17787},\frac{849}{22339},\frac{1525}{40126},\frac{2374}{62465},\frac{3899}{102591},\frac{6273}{165056},\frac{10172}{267647},\frac{16445}{432703},\frac{26617 }{700350},\frac{36789}{967997},\frac{46961}{1235644},\frac{57133}{1503291},\frac{67305}{1 770938},\frac{77477}{2038585},\frac{87649}{2306232},\frac{97821}{2573879},\frac{107993}{2 841526},\frac{118165}{3109173},\frac{128337}{3376820},\frac{138509}{3644467},\frac{148681 }{3912114},\frac{158853}{4179761},\frac{307534}{8091875},\frac{456215}{12003989},\frac{76 3749}{20095864},\frac{1071283}{28187739}\right\} $$

$\endgroup$
6
  • 1
    $\begingroup$ See here for an easy way to generate these approximations via a binary search using Farey mediants (includes a worked example). $\endgroup$
    – Bill Dubuque
    Feb 22, 2022 at 21:09
  • $\begingroup$ There are several similarities between the Stern-Brocot tree and the Farey sequence, but one distinction worth noting is that the Stern-Brocot tree contains all positive rational numbers, whereas the Farey sequence is limited to the rationals in $[0,1]$. $\endgroup$
    – awkward
    Feb 23, 2022 at 12:49
  • $\begingroup$ The mediants used in the linked algorithm are not restricted to $[0,1]$ $\endgroup$
    – Bill Dubuque
    Feb 23, 2022 at 14:29
  • $\begingroup$ @BillDubuque Yes, I think the algorithm is the same as the one given in the Wikipedia article on Stern-Brocot. $\endgroup$
    – awkward
    Feb 23, 2022 at 14:40
  • $\begingroup$ Probably (didn't check). That's a very old algorithm. I've been emphasizing it in math forums long before Wikipedia existed (early days of sci.math a few decades ago), since it deserves to be much better known. $\endgroup$
    – Bill Dubuque
    Feb 23, 2022 at 14:56

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .