Counting fractions in a range

Fork me on GitHub

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/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?

v          // Project Euler - Problem 73
 XX  ????

# ... #
. . . .
.  .  .
. . . .
# ... #

vp12*"(2"     <     v+1                    <                 <
|-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.


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