Closest fraction

Question

Task:

Your program is given a proper, positive simple fraction in the format <numerator>/<denominator>.

For this input, it must find two fractions.

1. A fraction that is less than the input.
2. A fraction that is greater than the input.

Both fractions must have a lower denominator than the input. Of all possible fractions, they should have the lowest difference to the input.

Output:

Your program's output must be:

• A fraction that is smaller than the input, in the format <numerator>/<denominator>.
• Followed by a space character (ASCII-code 32).
• Followed by a fraction that is greater than the input, in the format <numerator>/<denominator>.

As follows:

«fraction that is < input» «fraction that is > input»

Rules:

• All fractions outputted must be in lowest terms.
• All fractions outputted must be proper fractions.
• If there are no proper fractions possible that are allowed by the rules, you must output 0 instead of a fraction < input, and 1 instead of a fraction > input.
• You can choose whether you want to receive the fraction as a command-line argument (e.g. yourprogram.exe 2/5) or prompt for user input.
• You may assume your program won't receive invalid input.
• The shortest code (in bytes, in any language) wins.

• Any non-standard command-line arguments (arguments that aren't normally required to run a script) count towards the total character count.

• What your program must not do:

  • Depend on any external resources.
  • Depend on having a specific file name.
  • Output anything other than the required output.
  • Take exceptionally long to run. If your program runs over a minute for fractions with a 6-digit numerator and denominator (e.g. 179565/987657) on an average home user's computer, it's invalid.
  • Output fractions with 0 as the denominator. You can't divide by zero.
  • Output fractions with 0 as the numerator. Your program must output 0 instead of a fraction.
  • Reduce an inputted fraction. If the fraction given as input is reducible, you must use the fraction as it is inputted.
• Your program must not be written in a programming language for which there did not exist a publicly available compiler / interpreter before this challenge was posted.

Examples:

Input: 2/5
Output: 1/3 1/2

Input: 1/2
Output: 0 1

Input: 5/9
Output: 1/2 4/7

Input: 1/3
Output: 0 1/2

Input: 2/4
Output: 1/3 2/3

Input: 179565/987657
Output: 170496/937775 128779/708320

Answer 1

Python 2.7 - 138

x,y=n,d=map(int,raw_input().split('/'))
while y:x,y=y,x%y
def f(p,a=d):
 while(a*n+p)%d:a-=1
 print`(a*n+p)/d`+('/'+`a`)*(a>1),
f(-x);f(x)

I started with the obvious brute-force solution, but I realized that since the OP wanted to be able to solve instances with six digit numerators and denominators in under a minute, I need a better solution than trying a trillion possibilities. I found a handy formula on the Wikipedia page for the Farey sequence: If a/b, c/d are neighbors in one of the Farey sequences, with a/b<c/d, then b*c-a*b=1. The while loop inside f in my program extends this fact to non-reduced numbers, using the gcd, which the other while loop calculates.

I've golfed this pretty hard already, but I'd love to hear any suggestions.

Edits:

166->162: Removed a and b from the outer program. They were unnecessary.
162->155: str() -> ``
155->154: Added k.
154->152: Removed x from inside the function, passed it as an argument instead.
152->150: Gave a a default value instead of passing it as an argument.
150->146: Changed the initialization of x and y.
146->145: Removed k.
145->144: Changed ... and ... or ... to (...,...)[...], thereby saving a space.
144->138: Changed (...,...)[...] to ...+...*(...). Thanks to @mbomb007.

Test cases:

2/5
1/3 1/2

1/2
0 1

2/4
1/3 2/3

179565/987657
170496/937775 128779/708320

12345678/87654321
12174209/86436891 11145405/79132382

The second to last test took under a second on my computer, while the last one took about 5-10 seconds.

Answer 2

Mathematica, 163 bytes

{a,b}=FromDigits/@InputString[]~StringSplit~"/";r=Range[b-1];""<>Riffle[#~ToString~InputForm&/@(#@DeleteCases[#2[a/b*r]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}})," "]

This is severely limited by the input/output requirement as user input and strings. Dealing with strings is really cumbersome in Mathematica (at least when you want to golf). Doing this the natural way in Mathematica, (using just integers and rationals) I'd probably get this down to 50% of the size.

It can do 6-digit numbers in a few seconds on my machine.

Slightly more readable (not really ungolfed though):

{a, b} = FromDigits /@ InputString[]~StringSplit~"/";
r = Range[b - 1];
"" <> Riffle[#~ToString~
     InputForm & /@ (#[DeleteCases[#2[a/b*r]/r, a/b]] & @@@ {{Max, 
       Floor}, {Min, Ceiling}}), " "]

For the fun of it, doing this "the natural way", i.e. as a function taking numerator and denominator and returning two rationals, this is only 84 characters (so my 50% estimate was actually pretty close):

f[a_,b_]:=#@DeleteCases[#2[a/b*(r=Range[b-1])]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}}

Answer 3

Sage – 119 117

x,X=map(int,raw_input().split('/'))
a=0
A=c=C=1
while C<X:exec("ab,,AB"[c*X>C*x::2]+"=c,C");c=a+b;C=A+B
print a/A,b/B

Sage is only needed in the last line, which takes care of the output. Everything else also works in Python.

Replace raw_input() with sys.argv[1] to have the input read from a command-line argument instead of a prompt. This does not change the character count. (Does not work in Python without importing sys first.)

This essentially recursively constructs the respective Farey sequence using mediants of the existing elements, but restricts itself to those elements closest to the input. From another point of view, it runs a nested-interval search on the respective Farey sequences.

It correctly processes all of the examples in less than a second on my machine.

Here is an ungolfed version:

x,X = map(Integer,sys.argv[1].split('/'))
x = x/X
a = 0
c = b = 1
while c.denominator() < X:
    if c > x:
        b = c
    else:
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b

Answer 4

Julia - 127 125 bytes

I've approached this from a mathematical perspective to avoid need for loops, so this code runs quite fast for large inputs (note: if a/b is the input, then a*b must fit within Int64 (Int32 on 32 bit systems), otherwise nonsense answers are generated - if a and b are both expressible in Int32 (Int16 on 32 bit systems), no problems occur).

UPDATE: There's no longer a need to overload backslash for div, by using ÷, a net saving 2 bytes.

a,b=int(split(readline(),"/"));k=gcd(a,b);f=b-invmod(a÷k,b÷k);d=2b-f-b÷k;print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1))

Ungolfed:

a,b=int(split(readline(),"/")) # Read in STDIN in form a/b, convert to int
k=gcd(a,b)           # Get the greatest common denominator
f=b-invmod(a÷k,b÷k)  # Calculate the denominator of the next biggest fraction
d=2b-f-b÷k           # Calculate the denominator of the next smallest fraction
print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1)) # Calculate numerators and print

Basic idea: find the largest d and f less than b that satisfies ad-bc=gcd(a,b) (next smallest) and be-af=gcd(a,b) (next largest), then calculate c and e from there. Resulting output is c/d e/f, unless either d or f is 1, in which case the /d or /f is omitted.

Interestingly, this means that the code also works for positive improper fractions, so long as the input is not an integer (that is, gcd(a,b)=a).

On my system, inputting 194857602/34512958303 takes no perceivable time to output 171085289/30302433084 23772313/4210525219

Answer 5

JavaScript, 131

With fat arrow notation and eval calls :

m=>{for(e=eval,n=e(m),i=p=0,q=1;++i</\d+$/.exec(m);)if(n*i>(f=n*i|0))g=f+1,p=f/i>e(p)?f+'/'+i:p,q=g/i<e(q)?g+'/'+i:q;return p+' '+q}

The 179565/987657 stress test is executed in approximately 35 seconds on Firefox, a lot more on Chrome (~ 6 minutes)

Faster method and without eval and fat arrow notation

for(n=eval(m=prompt(a=i=p=0,b=c=d=q=1));++i<m.match(/\d+$/);)if(n*i>(f=n*i|0))g=f+1,p=f*c>i*a?(a=f)+'/'+(c=i):p,q=g*d<i*b?(b=g)+'/'+(d=i):q;alert(p+' '+q)

The 179565/987657 stress test is executed in approximately 5 seconds.

Not golfed :

m=prompt(); //get input
a=0; c=1; //first fraction
b=1; d=1; //second fraction
n=eval(m); //evaluate input
for (i=1; i<m.match(/\d+$/); i++) { //loop from 1 to input denominator
  f=Math.floor(n*i);
  if (n*i > f) { //if fraction not equal to simplification of input
    g=f+1; // f/i and g/i are fractions closer to input
    if (f/i>a/c) a=f, c=i;
    if (g/i<b/d) b=g; d=i; 
  }
}
alert(a+'/'+c+' '+b+'/'+d); //output values handling 0 and 1 correctly

Answer 6

perl, 142 bytes (155 without CPAN)

use bare A..Z;$/="/";N=<>;D=<>;F=N/D;K=G=1;for$H(1..D){J<F&&J>E?(E,I):J>F&&J<G?(G,K):()=(J=$_/H,"$_/$H")for(Z=int F*H)..Z+1}print I||0," $K\n"

Or if CPAN modules are disallowed / 3-4 times faster code is needed:

$/="/";$N=<>;$D=<>;$F=$N/$D;$g=$G=1;for$d(1..$D){$f<$F&&$f>$E?($E,$e):$f>$F&&$f<$G?($G,$g):()=($f=$_/$d,"$_/$d")for($z=int$F*$d)..$z+1}print$e||0," $g\n"

The former version takes 9.55 seconds on my machine, the latter version 2.44 seconds.

Less unreadable:

($N, $D) = split(m[/], <>);
$F = $N / $D;
$G = 1;
foreach $d (1 .. $D) {
    $z = int $F * $d;
    foreach $_ ($z .. $z + 1) {
        $f = $_ / $d;
        ($f < $F && $f > $E ? ($E, $e) :
        ($f > $F && $f < $G ? ($G, $g) : ())) = ($f, "$_/$d");
    }
}
print $e || 0, ' ', $g || 1, "\n";