18
\$\begingroup\$

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 

Sample implementation in Haskell

\$\endgroup\$
13
  • \$\begingroup\$ May I take input as a list of two fractions? \$\endgroup\$
    – alephalpha
    May 22 at 14:09
  • 1
    \$\begingroup\$ @alephalpha Sure. Really anything within reason is fine. \$\endgroup\$
    – Wheat Wizard
    May 22 at 14:10
  • \$\begingroup\$ Are errors due to floating-point inaccuracies acceptable? \$\endgroup\$
    – pxeger
    May 22 at 14:15
  • \$\begingroup\$ @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. \$\endgroup\$
    – Wheat Wizard
    May 22 at 14:21
  • 3
    \$\begingroup\$ @Steffan Most fractions don't have a finite decimal representation, so mathematically no, you can't take input as a decimal. \$\endgroup\$
    – Wheat Wizard
    May 22 at 19:09

12 Answers 12

7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Vyxal, 17 bytes

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

Try it Online!

Port of Husk answer.

\$\endgroup\$
2
  • \$\begingroup\$ Taking input as fractions would probabbly save a byte or three \$\endgroup\$
    – emanresu A
    May 22 at 19:48
  • \$\begingroup\$ @emanresuA but it doesn't work. it treats it as a string, although it would save four bytes \$\endgroup\$
    – Steffan
    May 22 at 19:57
1
\$\begingroup\$

Charcoal, 35 bytes

NθNηNζNεI§ΦE⊕⁺ηε⟦⊕÷×θκηκ⟧›×ζκקι⁰ε⁰

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

Nθ                                  Numerator of `x` as an integer
  Nη                                Denominator of `x` as an integer
    Nζ                              Numerator of `y` as an integer
      Nε                            Denominator of `y` as an integer
              η                     Denominator of `x`
             ⁺                      Plus
               ε                    Denominator of `y`
            ⊕                       Incremented
           E                        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
        I                           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 \$.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 36 bytes

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

Try it online!

Port of alephalpha's PARI/GP solution.

\$\endgroup\$
0
\$\begingroup\$

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)
\$\endgroup\$
0
\$\begingroup\$

Japt, 24 bytes

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

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

Try it

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.