Ordered fractions
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/8It 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:
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.@ ^ < <
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 |