# Closest fraction

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:

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

• Your first example does not match the specification: Both fractions must have a lower denominator than the input. – Howard Apr 25 '14 at 9:59
• First example, output should be 1/3 1/2. – Heiko Oberdiek Apr 25 '14 at 10:02
• @HeikoOberdiek You're right. Fixed. – user2428118 Apr 25 '14 at 10:19
• Define "average home user's computer". Is 90 seconds on a 1.6GHz Intel Atom machine acceptable? – John Dvorak Apr 26 '14 at 6:02
• Your last example is incorrect. The input fraction equals the first of the output fractions. – DavidC Apr 15 '15 at 21:24

## 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

• I was already afraid that I wouldn't get any new submissions for this bounty. Great work. – user2428118 Oct 16 '14 at 16:06
• Nice trick with the exec! – xnor Oct 17 '14 at 8:43
• As the only answer submitted within the bounty period, I am hereby awarding you the bounty. Congratulations. – user2428118 Oct 18 '14 at 19:51
• I just fixed an error in one of the examples. You may want to correct your submission (even though it's been half a year since you submitted it). – user2428118 Jul 17 '15 at 9:45

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

• This k=1 is pure wickedness. – Evpok Apr 25 '14 at 13:32
• @Evpok: I was trying to get k=y=n to work, but apparently if you modify a variable inside a function, python wants it to be local. This was the only way to get a local variable in 4 characters. Also, since the fraction is positive and proper, the denominator can't be 1. – isaacg Apr 25 '14 at 13:36
• Command-line arguments are easy with Python, so they should have been used for input as instructed here. – Alex Thornton Apr 25 '14 at 20:45
• "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." – isaacg Apr 26 '14 at 5:58
• Save 6 chars: print(a*n+p)/d+('/'+a)*(a>1), – mbomb007 Apr 15 '15 at 20:28

## 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}}


# 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

• Testing with 55552/999999 gives me -396/920632 486/936509. – user2428118 May 22 '14 at 8:20
• @user2428118 - Are you on a 32 bit system (or using a 32 bit Julia)? I've used "int", which means that on a 32 bit system, it'll use Int32 rather than Int64. int32(55552*999999) gives -282630400. For me, with that test, I get 51143/920632 52025/936509 - note that the denominators are the same, and that 52025-51143 = 486-(-396). I'll add a note to mention this issue. – Glen O May 22 '14 at 9:54
• If you want to ensure that the code will work for all Int64 size inputs, you can replace "int" with "int128". With that change, inputting 1234567891234567/2145768375829475878 results in 869253326028691/1510825213275018197 365314565205876/634943162554457681. This change adds just 3 extra characters. – Glen O May 22 '14 at 10:19
• Yes, I'm using a 32-bit computer. I'll try it on a 64-bit machine sometime when I've got the time for it. – user2428118 Jun 2 '14 at 20:00
• Testing on a 64-bit computer gives the correct result, so I'm accepting this answer. – user2428118 Jun 7 '14 at 10:03

## 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  • too... much... eval. EEK – John Dvorak Apr 25 '14 at 11:35 • Testing with 2/6 gives 1/3 2/5, however 1/3 is not less than but equal to 2/6. – user2428118 Apr 25 '14 at 12:12 • @user2428118 fixed – Michael M. Apr 25 '14 at 12:21 • Why has this answer been accepted so early? – Evpok Apr 25 '14 at 13:33 • @user2428118: You know, you can allow a couple days to pass before accepting solutions. Also, this solution is no longer the shortest. – isaacg Apr 25 '14 at 13:37 # 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.

($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";