# Background

Sometimes in calculus you're expected to calculate the sum of an infinite series. Sometimes these series are very friendly, like a geometric series, but add anything else onto it and it can quickly get complicated to solve by hand.

Sometimes I like to be lazy - a lot of sums can be found simply by adding the first few terms then making an approximation. Say the sum of the first ten terms is 0.199999983, and the future terms are approaching zero. We can say with a fair degree of certainty that our final answer will be 0.2, or 1/5.

# The Challenge

Given a decimal number and an integer as inputs, calculate the best (fully simplified) fractional approximation of the decimal number for all fractions up to a denominator of the given integer. The best fractional approximation will be that which is closest to the decimal number in absolute value.

You may take these inputs any way you like and you may output the numerator and denominator any way you like. The numerator and denominator must always be integers, and you may assume we will deal with only positive numbers because adding a negative sign is trivial.

# Test Cases

Input | Output

1.21, 8 | 6/5

3.14159265359, 1000000 | 3126535/995207

19.0, 10000000 | 19/1

3.14159265359, 12 | 22/7

2.7182818, 100 | 193/71

0.8193927511, 22 | 9/11

0.2557463559, 20 | 1/4

0.2557463559, 100 | 11/43

0.0748947977, 225 | 14/187


# Scoring

This is . Shortest code wins!

• Decimal is a radix. Do you mean numbers with fractional parts? Jul 22 '20 at 2:25
• @MarquisofLorne when I say decimal numbers I'm referring to what people would commonly call decimal numbers (i.e. numbers with digits after the decimal point). Although technically calling them decimal numbers because they are in the decimal system would also be correct Jul 22 '20 at 11:22
• This reminded me that 22/7 is a well-known rational approximation of pi... And another really good one is 355/113, which is VERY easy to remember if you memorize it as "split 113355 in half and make a fraction with it". (These 2 come from the continued fraction of pi, in case you are wondering)
– RGS
Jul 22 '20 at 14:21
• @RGS I actually included the 22/7 example for this very reason Jul 22 '20 at 14:25

# Python 3, 66 61 bytes

lambda x:Fraction(x).limit_denominator
from fractions import*


Try it online!

The above function takes a floating point number and returns a bound function Fraction.limit_denominator which, in turn, takes the upper bound for the denominator to return a simplified, approximated fraction as requested.

As you can tell, I’m more of an API reader than a golfer.

• Nice find! You can make this a little shorter by currying the function: Try it online!
– ovs
Jul 22 '20 at 18:25
• @ovs Thanks! I didn’t even know that is an option in Code Golf. Jul 22 '20 at 20:46

# Python 3.8 (pre-release), 77 71 bytes

-6 bytes thanks to @ovs !

lambda x,n:min([abs(x-(a:=round(x*b))/b),a,b]for b in range(1,n+1))[1:]


Try it online!

Simply try all denominators from 1 to n, saving all results into a list where each element has the form [error, numerator, denominator]. By taking the min of the list, the fraction with the smallest error is selected.

• You can make this a little shorter and lot faster with min.
– ovs
Jul 22 '20 at 7:29
• @ovs I totally missed that, thanks for pointing out! Jul 22 '20 at 8:43

# Python 2, 168, 135, 87 bytes

z=i=1
def f(x,y):exec"r=round(x*i);q=abs(r/i-x)\nif q<z:z=q;t=r;u=i\ni+=1;"*y;print t,u


Try it online!

Thank you all for your recommendations on my first golf!

• Welcome to the site, and nice first answer! I'd recommend you check out our Tips for golfing in Python in order to find some neat golfing tricks Jul 21 '20 at 16:49
• Here some more improvements by putting the duplicated code in for(2) loop: 135 bytes. PS: tips for golfing in 'all languages' might also be interesting to read through. And great first answer! Welcome. Jul 21 '20 at 17:10
• for _ in[1]*2 basically means to loop twice without using the _. A more readable alternative with the same byte-count in this case could be for q in[0,1]. The [1]*2 will basically make the list [1,1]. And then the for _ in[1,1] will loop over this. There might be a shorter way to execute the code twice perhaps, but I'm not too skilled with Python. I know exec("some_code;"*2) would work for one-liners, but I don't think it will work for the multiple indented lines in this case. Jul 21 '20 at 17:35
• You can get rid of the second for loop using r=round(...) instead of int(...). z can starts at 1, since the error cannot exceed 1. Try it online! Jul 22 '20 at 0:33
• @Third-party'Chef' I don't think you can remove abs, since r/i can be greater than x. For example, with test 1.19, 8 | 6/5, your solution returns 4/3. Jul 22 '20 at 6:33

# 05AB1E, 11 bytes

î*LãΣ/¹α}н


Try it online or verify all test cases (except for the two 1000000 test cases, which take too long).

Explanation:

î          # Ceil the (implicit) input-decimal
*         # Multiply it by the (implicit) input-integer
L        # Pop and push a list in the range [1, ceil(decimal)*int]
ã       # Create all possible pairs of this list by taking the cartesian product
Σ      # Sort this list of pairs by:
#  Pop and push both values separated to the stack
/    #  Divide them by one another
¹α  #  Get the absolute difference with the first input-decimal
}н     # After the sort: leave only the first pair
# (after which it is output implicitly as result)


# Python 3.8, 169 bytes

Maybe the reason why there was no submissions using Farey sequences is that the code appears rather lengthy.

In short, every proper fraction $$\\frac{m}{k}\$$ in lowest terms appears in Farey sequence of order $$\d\$$ if and only if $$\k\le d\$$.
Farey sequences are constructed by taking mediant of neighboring terms of lower order: $$\\left(\frac ab,\frac cd\right)\to\frac{a+c}{b+d}\$$, starting from $$\\left(\frac 01,\frac 11\right)\$$. And the target number is within one of the intervals $$\\left[\frac ab,\frac{a+c}{b+d}\right]\$$, $$\\left[\frac{a+c}{b+d},\frac cd\right]\$$, then we take the interval as a current one.

So the algorithm is:

1. Take $$\\left(\frac ab,\frac cd\right):=\left(\frac 01,\frac 11\right)\$$.
2. Take $$\\frac{m}{k}:=\frac{a+c}{b+d}\$$ and compare with target.
3. If $$\\frac{m}{k}>\$$ target, replace $$\\frac{a}{b}\$$ by $$\\frac{m}{k}\$$,
4. Else replace $$\\frac{c}{d}\$$ by $$\\frac{m}{k}\$$.
5. If the next denominator $$\b+d\$$ is no more than denominator limit, repeat from 2.
6. Else return nearest from $$\\frac ab,\frac cd\$$ to the target.
def f(e,n,g,j):
if n==0:return e,1
x=[(0,1),(1,1)]
while True:
(a,b),(c,d)=x
if b+d>j:break
m,k=a+c,b+d
x[m*g>n*k]=(m,k)
m,k=x[2*n/g-a/b>c/d]
return m+e*k,k


Try it online!

Eats (entire_part,proper_numerator,proper_denominator,denominator_limit) and produces (numerator,denominator), like

>>> f(3,141592653589793,10**len('141592653589793'),57)
(179, 57)

P.S. Recursive version is nothing but shorter, even with all whitespace removed:

f=(lambda e,n,g,j,a=0,b=1,c=1,d=1:
n and(
b+d>j and(lambda x,y:(x+e*y,y))(*([(a,b),(c,d)][2*n/g-a/b>c/d]))
or((m:=a+c)*g>n*(k:=b+d))and f(e,n,g,j,a,b,m,k)or f(e,n,g,j,m,k,c,d)
)or(e,1)
)


Try it online!

# Charcoal, 31 bytes

Ｎθ⪫…⮌⌊ＥＥＮ⌊⁺·⁵×θ⊕κ⟦↔⁻θ∕ι⊕κ⊕κι⟧²/


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

Ｎθ                              Input decimal as a number
Ｎ                       Input maximum denominator
Ｅ                        Map over implicit range
κ               Current index (0-indexed)
⊕                Increment (i.e. 1-indexed)
×                  Multiplied by
θ                 Input decimal
⌊⁺·⁵                   Round to nearest integer
Ｅ                         Map over results
ι         Current numerator
∕          Divided by
⊕κ       Current denominator
θ           Input decimal
↔⁻            Absolute difference
⊕κ     Current denominator
ι    Current numerator
⟦          ⟧   Make into list
⌊                          Take the minimum (absolute difference)
⮌                           Reverse the list
…                         ²  Take the first two entries
⪫                           / Join with literal /
Implicitly print


I'm not 100% sure that the algorithm is correct, so just in case, here's a 34-byte brute-force solution:

ＮθＦＮＦ⊕⌈×θ⊕ι⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧Ｉ⊟⌊υ/Ｉ⊟⌊υ


Try it online! Link is to verbose version of code. Very slow, so test case is limited to a denominator of 1000. Explanation:

Ｎθ


Input the decimal.

ＦＮ


Loop over the possible denominators (except 0-indexed, so all of the references to the loop variable have to be incremented).

Ｆ⊕⌈×θ⊕ι


Loop until the nearest numerator above.

⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧


Save the fraction difference and the denominator and numerator.

Ｉ⊟⌊υ/Ｉ⊟⌊υ


Print the numerator and denominator of the fraction with the minimum difference.

# Japt v2.0a0 -g, 15 bytes

mc ×õ ï ñ@ÎaXr÷


Try it

mc ×õ ï ñ@ÎaXr÷     :Implicit input of array U
m                   :Map
c                  :  Ceiling
×                :Reduce by multiplication
õ               :Range [1,result]
ï             :Cartesian product with itself
ñ           :Sort by
@          :Passing each pair X through the following function
Î         :  First element of U
a        :  Absolute difference with
Xr÷     :  X reduced by division
:Implicit output of first pair


# Zig 0.6.0, 149 bytes

fn a(e:f64,m:f64)[2]f64{var n:f64=1;var d=n;var b=d;var c=b;while(d<m){if(n/d>e)d+=1 else n+=1;if(@fabs(n/d-e)<@fabs(b/c-e)){b=n;c=d;}}return.{b,c};}


Try it

Formatted:

fn a(e: f64, m: f64) [2]f64 {
var n: f64 = 1;
var d = n;
var b = d;
var c = b;
while (d < m) {
if (n / d > e) d += 1 else n += 1;
if (@fabs(n / d - e) < @fabs(b / c - e)) {
b = n;
c = d;
}
}
return .{ b, c };
}


Variable declarations are annoying.

# Perl 5-p -MList::Util=min, 65, 61 bytes

-4 bytes thanks to DomHastings

/ /;$_=min map abs($-($-=.5+$_*$)/$_)." $-/$_",1..$';s;.* ;  Try it online! • Nice answer! You can save 4 bytes using $- instead of \$n (negates need for int) and using ; as the delimeter for your final s///: Try it online! Jul 24 '20 at 15:44
• Thanks, I forgot these tips Jul 24 '20 at 16:17

# R, 61 60 bytes

With a byte saved by Dominic van Essen.

function(x,d,n=round(1:d*x))c(m<-order((x-n/1:d)^2)[1],n[m])


Try it online!

• Nice! I saw you'd made an R answer so I didn't want to look at it until I'd tried myself. But I didn't think of round so my best attempt was 75 bytes. Well done. Jul 25 '20 at 8:21
• -1 byte by swapping which.min() for order()[1] Jul 25 '20 at 8:22

# Jelly, 11 bytes

Ċ×⁹p÷/ạ¥Þ⁸Ḣ


A dyadic Link accepting the decimal [evaluated as a float] on the left and the denominator limit on the right which yields a pair [numerator, denominator] representing the simplified fraction.

Try it online! Or see the test-suite (big denominator limit cases removed due to inefficiency.)

### How?

Ċ×⁹p÷/ạ¥Þ⁸Ḣ - Link: v, d
Ċ           - ceil (of the decimal value, v)
×⁹         - multiplied by chain's right argument (denominator limit, d)
p        - Cartesian power (d) -> all pairs [[1,1],...,[1,d],[2,1],...,[Ċ×⁹,d]]
(note that any pair representing a non-simplified fraction is to
the right of its simplified form)
Þ   - (stable) sort by:
/      -     reduce by:
÷       -       division (i.e. evaluate the fraction)
ạ  ⁸  -     absolute difference with the chain's left argument (v)


# APL (Dyalog Unicode), 26 bytes

⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣


Try it online!

A dyadic tacit function that takes the decimal number on its left and the max denominator on its right, and gives a 2-element vector of [denominator, numerator].

### How it works

⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣  ⍝ Left: x, Right: d
∘÷∘⍳      ⍝ v←[1, 1/2, ..., 1/d]
(          |⍨)          ⍝ Remainder of x divided by each of v
|⍨⌊⊢-             ⍝ Min distance from x to some integer multiple of v
1+                  ⍝ Add 1 to treat close enough numbers as same
⍝ Otherwise it gives something like 5/20 due to FP error
⊃∘⍋                    ⍝ D←The index of minimum (the optimal denominator)
×1,⊣  ⍝ Exact fraction (D,Dx)
⌊.5+                        ⍝ Round both


• i don't understand the role of 1+. ⊃∘⍋ is the index of the smallest, right? so when we add 1 to the whole array, shouldn't ⊃∘⍋ remain the same?
– ngn
Jul 22 '20 at 14:29
• if leading spaces are ok: ⌊.5+ -> 0⍕
– ngn
Jul 22 '20 at 14:37
• @ngn Try the test case starting with 0.255... with 20. If you don't 1+, you get 5/20 due to floating point errors that are big enough that APL treats them as different even with CT. Jul 22 '20 at 14:42
• yeah, i saw that, but aren't rounding errors generally considered acceptable in golfing?
– ngn
Jul 22 '20 at 14:49
• (⊃∘⍋1+|⍨⌊⊢-|⍨) -> (⊃∘⍋1+|⌊⊣-|)⍨
– ngn
Jul 22 '20 at 15:00

# Io, 78 bytes

method(x,y,Range 1to(y)map(a,list((x-(b :=(a*x)round)/a)abs,b,a))min slice(1))


Try it online!

# Io, 93 bytes

method(x,y,list(((q :=(r :=Range 0to(y)map(a,(x-(a*x)round/a)abs))indexOf(r min))*x)round,q))


Try it online!

## Explanation (ungolfed):

method(x, y,                   // Take two operands
r := Range 0 to(y) map(a,  // Map in range 0..y (set to r):
(x-(a*x)round/a)abs    //     |x-round(a*x)/a|
)                          //     (Aka find the appropriate numerator)
q :=r indexOf(r min)       // Set q as the 0-index of the smallest number of r
list((q*x)round,q)         // Output [numerator,denominator]
)                              // End function

• Ugh, that's twice this week that someone's based their answer on an answer after mine that uses the same algorithm that mine does... how can I improve my explanations?
– Neil
Jul 23 '20 at 10:28
• @Neil I think one reason is that Python is way more readable than Charcoal for most people. :) A trick that might be useful is to include a TLDR at the top about the answer's big idea, since a lot of the time that's all people need/care about. E.g. when I skim through your answer, I'm mostly interested in the algorithm rather than the specific Charcoal commands, and thus I simply skip all the code block. The "loop through all denominator..." sentence is the most telling to me, yet it's buried in the middle of all the hard-to-understand Charcoal stuff. Jul 27 '20 at 15:00

# Wolfram Language (Mathematica), 60 bytes

(t=s=1;While[Denominator[s=Rationalize[#,1/t++]]<#2,j=s];j)&


Try it online!

# Julia, 66 bytes

r(x,m)=minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]


or

(x,m)->minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]


# R, 75 bytes

function(x,d)c((n=rep(0:1,e=d)+(1:d*x)%/%1)[f<-order((x-n/1:d)^2)[1]],f%%d)


Try it online!

Not a competitive answer as it's already beaten by Kirill, but posting for fun anyway.

I didn't think of the round() function, so this approach rounds down & then up to generate a double-length list of candidate numerators, and then finds the index of the closest fraction. Since the index might be in the second (rounded-up) part of the list, the denominator is the index mod the length of the single-length list.

I think it's fair to conclude that the round() function indeed serves a useful role...