2015-08-19

# Problem 071: Ordered fractions

Description:

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

Solution:
v X X C
X X ????

>020p040p121p141p"}}@"**60pv
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.@               ^      <                            <
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

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