Project Euler with Befunge
Problem 071: Ordered fractions
Consider the fraction,
d are positive integers. If
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
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
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.@ ^ < <
For every denominator from
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
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)|