2015-08-21

# Problem 073: Counting fractions in a range

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 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:
v          // Project Euler - Problem 73
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<
This program is too big to display/execute here, click [download] to get the full program.

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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript