In between fractions

Question

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 code-golf 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 

Sample implementation in Haskell

Answer 1

Husk, 20 12 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

Answer 2

PARI/GP, 36 bytes

f(a,b,d)=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\$.

Answer 3

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!

Port of alephalpha's PARI/GP answer.

Answer 4

Vyxal, 17 bytes

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

Try it Online!

Port of Husk answer.

Answer 5

C (clang), ⁶⁷ 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.

Answer 6

Wolfram Language (Mathematica), 36 bytes

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

Try it online!

Port of alephalpha's PARI/GP solution.

Answer 7

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 \$.

Answer 8

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!

Answer 9

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.

Answer 10

05AB1E, 24 bytes

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

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

Try it online or verify all test cases.

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)

Answer 11

Japt, 24 bytes

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

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

Try it

Answer 12

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]
    add %r8, %r9
    add %r10, %r11
# 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.)