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.


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»


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


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

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

6 Answers 6


Python 2.7 - 138

while y:x,y=y,x%y
def f(p,a=d):

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.


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:

1/3 1/2

0 1

1/3 2/3

170496/937775 128779/708320

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.

  • \$\begingroup\$ This k=1 is pure wickedness. \$\endgroup\$
    – Evpok
    Commented Apr 25, 2014 at 13:32
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – isaacg
    Commented Apr 25, 2014 at 13:36
  • \$\begingroup\$ Command-line arguments are easy with Python, so they should have been used for input as instructed here. \$\endgroup\$ Commented Apr 25, 2014 at 20:45
  • 1
    \$\begingroup\$ "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." \$\endgroup\$
    – isaacg
    Commented Apr 26, 2014 at 5:58
  • \$\begingroup\$ Save 6 chars: print`(a*n+p)/d`+('/'+`a`)*(a>1), \$\endgroup\$
    – mbomb007
    Commented Apr 15, 2015 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):


Sage – 119 117

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
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b
  • \$\begingroup\$ I was already afraid that I wouldn't get any new submissions for this bounty. Great work. \$\endgroup\$ Commented Oct 16, 2014 at 16:06
  • \$\begingroup\$ Nice trick with the exec! \$\endgroup\$
    – xnor
    Commented Oct 17, 2014 at 8:43
  • \$\begingroup\$ As the only answer submitted within the bounty period, I am hereby awarding you the bounty. Congratulations. \$\endgroup\$ Commented Oct 18, 2014 at 19:51
  • \$\begingroup\$ 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). \$\endgroup\$ Commented Jul 17, 2015 at 9:45

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


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

  • \$\begingroup\$ Testing with 55552/999999 gives me -396/920632 486/936509. \$\endgroup\$ Commented May 22, 2014 at 8:20
  • \$\begingroup\$ @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. \$\endgroup\$
    – Glen O
    Commented May 22, 2014 at 9:54
  • \$\begingroup\$ 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. \$\endgroup\$
    – Glen O
    Commented May 22, 2014 at 10:19
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Jun 2, 2014 at 20:00
  • \$\begingroup\$ Testing on a 64-bit computer gives the correct result, so I'm accepting this answer. \$\endgroup\$ Commented Jun 7, 2014 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
  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
  • \$\begingroup\$ too... much... eval. EEK \$\endgroup\$ Commented Apr 25, 2014 at 11:35
  • 3
    \$\begingroup\$ Testing with 2/6 gives 1/3 2/5, however 1/3 is not less than but equal to 2/6. \$\endgroup\$ Commented Apr 25, 2014 at 12:12
  • \$\begingroup\$ @user2428118 fixed \$\endgroup\$
    – Michael M.
    Commented Apr 25, 2014 at 12:21
  • \$\begingroup\$ Why has this answer been accepted so early? \$\endgroup\$
    – Evpok
    Commented Apr 25, 2014 at 13:33
  • 1
    \$\begingroup\$ @user2428118: You know, you can allow a couple days to pass before accepting solutions. Also, this solution is no longer the shortest. \$\endgroup\$
    – isaacg
    Commented Apr 25, 2014 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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