Counting fractions in a range
Problem 073: Counting fractions in a range
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 there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 12,000?
Solution:
XX ????
# ... #
. . . .
. . .
. . . .
# ... #
>"}`"*11p051p0v
vp12*"(2" < v+1 < <
>1+:1+2/61p:71p:3/1+>:61g\`!#v_:21g%71g3+g!|>81g11g`91g11g`+#^_081g21gv
|-g11: >#$ #< ^p19+g19g17p18+g18:p+3g19%<
>$51g.@ ^p19g17p18:p15+1g15<
Explanation:
Here we brute-force through every possible denominator d (from 1 to 12000).
For every denominator the valid numerators are between floor(d/3) and ceil(d/2).
The only problem is that we don't know if a fraction is proper.
To solve this we use a 12000x12000 array where we mark the already found fractions and every multiple of them.
When we now find a new one we can test if we have already found the fraction (in a reduced form).
But a 12000x12000 array is quite big, the resulting b93-file was 140MB big.
But we know that most of the array will never be accessed,
only the columns between d/3 and d/2 are important and the biggest range is in the last row (LIMIT/3 - LIMIT/2).
So in each array-acess we modulo the x coordinate by LIMIT/3 - LIMIT/2 (= 2000).
Now our array has only a size of 12000x2000 and the befunge-file is only 23MB big.
The program is not that fast, but that's mostly because of it's raw size, the algorithm is quite good (200ms when I implement it in C#)
| Interpreter steps: | 1 281 174 401 |
| Execution time (BefunExec): | 3min 22s (6.33 MHz) |
| Program size: | 2000 x 12010 |
| Solution: | 7295372 |
| Solved at: | 2015-08-21 |