Find a fraction with the smallest denominator

Question

Input

Two non-negative floating point numbers \$x < y\$. You can assume they are close enough to each other that there is no integer between \$x\$ and \$y\$.

Output

A fraction with the smallest possible denomination that lies strictly between \$x\$ and \$y\$.

Examples

Input: 1 and 2

Output: 3/2

Input: 0 and 0.33

Output: 1/4

Input: 0.4035 and 0.4036

Output: 23/57

• xnor: How do we deal with float imprecision? Say we're given the float representing 1/3 which actually equals 0.3333333333333333148..., is the fraction 1/3 greater than that?
• Simd: @xnor The input is a float so if it just has 3s in its decimal expansion, it is less than 1/3. Is this going to cause a difficulty?
• Wheat Wizard: I'm pretty sure this is a duplicate, but I can't find the original.
• Dingus: @WheatWizard Are you thinking of In between fractions? The only difference in that challenge is that \$x\$ and \$y\$ are fractions instead of floats.

Answer 1

JavaScript (Node.js), 42 bytes

x=>g=(y,d)=>(p=-~(x*d))<y*d?[p,d]:g(y,-~d)

Try it online!

If \$ \left \lfloor xd \right \rfloor +1 < yd \$, then \$ \left \lfloor xd \right \rfloor +1 \$ is an answer

• Neil: Which is fortunate since ⌈xd⌉<yd is the wrong test.

Answer 2

JavaScript (ES6), 47 bytes

Expects (x)(y), returns [numerator, denominator].

(x,p=q=1)=>g=y=>p<y*q++&&p++>x*--q?[--p,q]:g(y)

Try it online!

Commented

( x, // x = first number
 p = // p = numerator
 q = 1 // q = denominator
) => //
g = y => // y = second number
p < y * q++ // we test whether p/q < y
 // and increment q afterwards in case it's not
&& // if truthy,
p++ > x * --q // we restore q, test whether p/q > x
 // and increment p afterwards in case it's not
? // if truthy again:
 [--p, q] // we restore p and return [p, q]
: // else:
 g(y) // we try again with either p or q incremented

• Simd: But how does it work?
• Arnauld: @Simd I've added a commented version. This is a really simple algorithm, but written in a slightly convoluted way.

Answer 3

Charcoal, 33 bytes

×ばつηζζ

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

NθNη

Input x and y.

×ばつθι2ζ

Find d such that ⌈yd⌉-⌊xd⌋=2. d is never more than ⌊1+1/(y-x)⌋, but I have to add 2 due to 0-indexing.

×ばつηζζ

Output ⌈yd⌉-1 and d.

Answer 4

Jelly, 18 bytes

×ばつḞĊƭ€r/ḊṖ
1ç1#Ḣṭç\

Try it online!

A pair of links which is called as a monad with a pair of floats and returns a pair of [numerator, denominator].

Explanation

×ばつḞĊƭ€r/ḊṖ | Helper link: takes a denominator as the left argument and a pair of floats as the right and returns a valid numerator, if an×ばつ | Multiply (denominator with floats)
 ḞĊƭ€ | Floor first, ceiling second
 r/ | Reduce using range
 ḊṖ | Remove first and last
1ç1#Ḣṭç\ | Main link
1ç1# | Starting with one, find first denominator where there’s a valid numerator (will be wrapped in a list)
 Ḣ | Head (to unwrap the list)
 ṭç\ | Tag this onto the result of running the helper link again to find the numerator
```

Answer 5

Python 2, 95 bytes

(a,b),(c,d)=[input().as_integer_ratio()for m in 0,0]
while(m*d/c+1)*a>=m*b:m+=1
print m,m*d/c+1

Try it online!

Not a math guy, basically uses the formula of this answer.

The input should be in decimal format: 1.0 instead of just 1.

-2 bytes: replace // with /

-4 bytes: inlining m

Answer 6

R, 47 bytes

\(x,y){while((p=(x*F)%/%1+1)>=y*F)F=F+1
c(p,F)}

Attempt This Online!

Port of @l4m2's JavaScript answer.