1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include <iostream>
#include <vector>
#include <utility>
using namespace std;
struct Rational{ unsigned n, d; };
bool operator <= ( Rational a, Rational b ){ return a.n * b.d <= a.d * b.n; }
ostream & operator << ( ostream &out, Rational a ){ return out << a.n << '/' << a.d; }
Rational next( Rational x, unsigned N )
{
bool found = false;
Rational best{ 0, 0 }; // signifies undefined
for ( unsigned r = N; r; r ) // letting it go all the way to r=1 saves a gcd call later
{
Rational trial{ r * x.n / x.d + 1, r };
if ( trial.n > N ) continue;
if ( !found  trial <= best ) best = trial;
found = true;
}
return best;
}
int main()
{
vector< pair<Rational,unsigned> > tests = { {{2,3},7}, {{5,8},12}, {{65,31},73}, {{7,1},7} };
for ( auto pr : tests )
{
Rational R = next( pr.first, pr.second );
cout << "Next " << pr.second << "bounded rational after " << pr.first << " is ";
if ( R.d == 0 ) cout << " ... naah!\n";
else cout << R << '\n';
}
}
 