Ordered fractions

Fork me on GitHub

Problem 071: Ordered fractions


Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction. If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d <= 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

v X X C
  X X ????

v0                         <         >01+*v
>1+ :3*7%!#v_:61p:3*7/:71p7*61g3*-:0`|    >81p61g7*91p41g91g*21g81g*`#v_v
|-g06:     <                        <>01-*^v  p04g16p02g17p12g19p14g18<
>$20g."/ ",,55+,40g.@               ^      <                            <
Stack:   (0)


For every denominator from 1 to 1 000 000 we generate a possible fraction where the numerator is (d * 3) / 7. (Every other fraction is either greater than 3/7 or has a greater difference than the generated).

Now everything thats left is finding the fraction with the smallest difference to 3/7.

The difference of two fractions is calculated (without floating points) by:

n1/d1 - n2/d2  ==  (n1*d2 - n2*d1)/(d1*d2)

The rest is just iterating through all the possible fractions and in each step remembering the current best.

We don't even need to reduce the result to get a proper fraction. If it could be reduced we would have got the reduced version first. (Because it has an smaller denominator).

Interpreter steps: 77 428 679
Execution time (BefunExec): 11s (6.46 MHz)
Program size: 73 x 8 (fully conform befunge-93)
Solution: 428570
Solved at: 2015-08-19

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript