# In between fractions

Given two positive integer fractions $$\x\$$ and $$\y\$$ such that $$\x < y\$$, give the fraction $$\z\$$ with the smallest positive integer denominator such that it is between $$\x\$$ and $$\y\$$.

For example $$\x=2/5\$$, $$\y=4/5\$$, the answer is $$\1/2\$$. Other fractions such as $$\3/5\$$ are also in between the two, but $$\1/2\$$ has a denominator of $$\2\$$ which is smaller.

As input you will receive 4 positive integers, the numerators and the denominators of $$\x\$$ and $$\y\$$, you may assume these fractions are fully reduced. You should output the numerator and the denominator of $$\z\$$.

If there are multiple valid numerators, you may output any or all of them.

This is so the goal is to minimize the size of your source code as measured in bytes.

### Test cases

2/5 4/5 -> 1/2
1/1 2/1 -> 3/2
3/5 1/1 -> 2/3
5/13 7/18 -> 12/31
12/31 7/18 -> 19/49


• May I take input as a list of two fractions? May 22 at 14:09
• @alephalpha Sure. Really anything within reason is fine. May 22 at 14:10
• Are errors due to floating-point inaccuracies acceptable? May 22 at 14:15
• @pxeger For all their faults, floats are monotonic on division, so floating point inaccuracies beyond errors you would encounter using limited precision ints are rather unlikely for this problem using normal methods. May 22 at 14:21
• @Steffan Most fractions don't have a finite decimal representation, so mathematically no, you can't take input as a decimal. May 22 at 19:09

# Husk, 2012 11 bytes

ḟ<⁰MS/ȯ→⌊*N


Try it online!

Generates an infinite list of fractions by going through each integer N as denominator in turn and constructing the numerator floor(N*x)+1.
Then searches for the first one that is <y.

ḟ<⁰MS/ȯ→⌊*N
M      N  # map over all integers starting at 1:
*   # multiply it by (implicit input) x
⌊    # get the floor
→     # and increment it,
S/ȯ      # and now divide all of that by itself;
ḟ            # finally, get the first result that
<⁰          # is less than y


# PARI/GP, 38 bytes

f(a,b)=d=0;until(b*d++>n=a*d\1+1,);n/d

Attempt This Online!

Takes two fractions and outputs a fraction.

For inputs $$\a,b\$$, let $$\d\$$ loops over all positive integers until $$\b\ d>\lfloor a\ d\rfloor+1\$$, and returns $$\(\lfloor a\ d\rfloor+1)/d\$$.

# Python 2, 61 bytes

a,p,b,q=input();r=c=0
while r*b<=q*c:r+=1;c=r*a/p+1
print c,r

Attempt This Online!

Rather naïve.

# Python with fractions, 57 bytes

def f(x,y,d=0):
while(n:=x*d//1+1)>=y*d:d+=1
return n,d

Attempt This Online!

# C (clang), 67 62 bytes

n;d;f(*i,*j,k,l){for(d=n=0;*i*d<=*j*n;)n=++d*k/l+1;*i=n;*j=d;}


Try it online!

Inputs the two fractions as $$\2\$$ pointers to integers for the numerator and denominator of the second fraction. And then $$\2\$$ integers as the numerator and denominator of the first fraction.
Returns the in between fraction through the two pointers.

# Vyxal, 17 bytes

ƒ/Þ∞*⌊›Þ∞/'⁰ƒ/<;h


Try it Online!

• Taking input as fractions would probabbly save a byte or three May 22 at 19:48
• @emanresuA but it doesn't work. it treats it as a string, although it would save four bytes May 22 at 19:57

# Charcoal, 35 bytes

ＮθＮηＮζＮεＩ§ΦＥ⊕⁺ηε⟦⊕÷×θκηκ⟧›×ζκ×§ι⁰ε⁰


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

Ｎθ                                  Numerator of x as an integer
Ｎη                                Denominator of x as an integer
Ｎζ                              Numerator of y as an integer
Ｎε                            Denominator of y as an integer
η                     Denominator of x
⁺                      Plus
ε                    Denominator of y
⊕                       Incremented
Ｅ                        Map over implicit range
θ               Numerator of x
×                Multiplied by
κ              Current index
÷                 Integer divided by
η             Denominator of x
⊕                  Incremented
κ            Current index
⟦       ⟧           Make into list
Φ                         Filtered where
ζ        Numerator of y
×         Multiplied by
κ       Current index
›          Is greater than
§ ⁰   First index of
ι    Current list
×      Multiplied by
ε  Denominator of y
§                        ⁰ First element
Ｉ                           Cast to string
Implicitly print


The sum of the denominators is a sufficient limit since $$\ \frac a b < \frac { a + b } { c + d } < \frac c d \$$ if $$\ \frac a b < \frac c d \$$.

# JavaScript (ES6), 50 bytes

Expects $$\p/q\$$ and $$\P/Q\$$ as (p,q,P)(Q) and returns $$\m/n\$$ as [m,n].

Based on alephalpha's method.

(p,q,P,n=0)=>g=Q=>++n*P>(m=-~(n*p/q))*Q?[m,n]:g(Q)


Try it online!

# Wolfram Language (Mathematica), 36 bytes

n&@For[d=1,(n=⌊d#+1⌋/d++)>=#2,]&


Try it online!

Port of alephalpha's PARI/GP solution.

# 05AB1E, 24 bytes

∞ε¹.E*ï>y‚D¿÷'/ý}.Δ‚.E›


Port of @DominicVanEssen's Husk answer, but without implicit fraction support.

Explanation:

∞           # Push an infinite positive list: [1,2,3,...]
ε          # Map over each value:
¹         #  Push the first input
.E       #  Evaluate it as Elixir
*      #  Multiply it to the current value
ï     #  Floor it
>    #  Increase it by 1
y‚        #  Pair it with the current value
D       #  Duplicate this pair
¿      #  Pop and push the gcd (greatest common divisor)
÷     #  Integer-divide the pair by this gcd
'/ý '#  Join the pair with "/"-delimiter to a string
}.Δ        # After the map: find the first value which is truthy for:
‚       #  Pair it with the (implicit) second input
.E     #  Evaluate both strings as Elixir
#  Pop and push both values to the stack
›   #  Check that the first is larger than the second
# (after which the found fraction-string is output implicitly)


# Japt, 24 bytes

Settled with a port of Arnauld's solution for now.

T=°Y*U/VW*Y§X*ÒT?ß:[ÒTY]


Try it

# TI-Basic, 30 bytes

Prompt A,B
Repeat BAns>1+int(AAns
Ans+1
End
1/Ans(1+int(AAns


Port of alealpha's answer. Takes input as 2 fractions and output a fraction. The / symbol represents the fraction slash.

# x86_64 assembly, 48 bytes

This routine expects arguments eax/ebx, ecx/edx and returns the result in r9/r11 (and registers r8 and r10 are clobbered).

    .text
.globl f
f:
xor %r8, %r8
xor %r9, %r9
xor %r10, %r10
inc %r8
mov %r8, %r11
.Lloop:
cmp %rdx, %rcx
ja  .L1
# a/b < c/d <= 1: return 1 / f(d/c,b/a)
xchg    %rax, %rdx
xchg    %rbx, %rcx
# 1/ matrix to multiply on right is [0 1; 1 0]
xchg    %r8, %r9
xchg    %r10, %r11
jmp .Lloop
.L1:
# 1+ matrix to multiply on right is [1 1; 0 1]
# 1 <= a/b < c/d: return 1 + f(a/b-1, c/d-1)
sub %rdx, %rcx
sub %rbx, %rax
jae .Lloop
# a/b < 1 < c/d:
# return 0/1 (which becomes a return of 1/1 with the 1+ matrix
# merged between this case and the previous one)
ret


C test driver (requires GCC):

#include <stdio.h>

void f_wrap(unsigned long a,
unsigned long b,
unsigned long c,
unsigned long d,
unsigned long *e,
unsigned long *f) {
register unsigned long r9 __asm__("r9");
register unsigned long r11 __asm__("r11");
__asm__("call f" :
"=a"(a), "=b"(b), "=c"(c), "=d"(d), "=r"(r9), "=r"(r11) :
"0"(a), "1"(b), "2"(c), "3"(d) :
"r8", "r10");
*e = r9;
*f = r11;
}

void test_f(unsigned long a,
unsigned long b,
unsigned long c,
unsigned long d) {
unsigned long e;
unsigned long f;
f_wrap(a, b, c, d, &e, &f);
printf("%lu/%lu %lu/%lu -> %lu/%lu\n", a, b, c, d, e, f);
}

int main() {
test_f(2, 5, 4, 5);
test_f(1, 1, 2, 1);
test_f(3, 5, 1, 1);
test_f(5, 13, 7, 18);
test_f(12, 31, 7, 18);
test_f(2, 5, 1, 2);
test_f(3, 7, 1, 2);
// 3.14 = 314/100 = 157/50; 3.15 = 315/100 = 63/20
test_f(157, 50, 63, 20);
// 3.1415 = 31415/10000 = 6283/2000; 3.1416 = 31416/10000 = 3927/1250
test_f(6283, 2000, 3927, 1250);
return 0;
}


And disassembly of the code as it ended up in the executable:

0000000000001229 <f>:
1229:       4d 31 c0                xor    %r8,%r8
122c:       4d 31 c9                xor    %r9,%r9
122f:       4d 31 d2                xor    %r10,%r10
1232:       49 ff c0                inc    %r8
1235:       4d 89 c3                mov    %r8,%r11
1238:       48 39 d1                cmp    %rdx,%rcx
123b:       77 0d                   ja     124a <f+0x21>
123d:       48 92                   xchg   %rax,%rdx
123f:       48 87 d9                xchg   %rbx,%rcx
1242:       4d 87 c1                xchg   %r8,%r9
1245:       4d 87 d3                xchg   %r10,%r11
1248:       eb ee                   jmp    1238 <f+0xf>
124a:       4d 01 c1                add    %r8,%r9
124d:       4d 01 d3                add    %r10,%r11
1250:       48 29 d1                sub    %rdx,%rcx
1253:       48 29 d8                sub    %rbx,%rax
1256:       73 e0                   jae    1238 <f+0xf>
1258:       c3                      ret


The basic idea in pseudocode behind this implementation is inspired by continued fractions:

f(x,y):
if y <= 1
return 1 / f(1/y, 1/x)
else if x >= 1
return 1 + f(x-1, y-1)
else
return 1/1


(Do note, however, that in certain cases, this makes a recursive call to f with y = 1 / 0 where we treat that as infinity.)

Now, the biggest optimization I made was to note that at any point, the transformations on the stack to the return value form a projective linear transformation. So, in the assembly version, instead of maintaining a call stack, I maintain a 2x2 matrix representing the required projective linear transformation so far in registers [r8 r9; r10 r11].

Aside from that, and some usual optimizations, there was a folding of common code between the second and third cases: both involve taking the sum of the two columns of the transformation matrix.

(However, I didn't make any effort to try different register allocations, and see if others might end up saving a couple bytes.)