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
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 there are 3 fractions between
How many fractions lie between
1/2 in the sorted set of reduced proper fractions for
d <= 12,000?
# ... #
. . . .
. . .
. . . .
# ... #
vp12*"(2" < v+1 < <
|-g11: >#$ #< ^p19+g19g17p18+g18:p+3g19%<
Here we brute-force through every possible denominator
d (from 1 to 12000).
For every denominator the valid numerators are between
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).
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/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 (=
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|