## Question

Consider the fraction, $\frac{n}{d}$, where $n$ and $d$ are positive integers. If $n \lt d$ and $\mathrm{HCF}(n,d)=1$, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for $d \leq 8$ in ascending order of size, we get:

$\displaystyle \frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{2}{7}, \frac{1}{3}, \frac{3}{8}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}$

It can be seen that there are 3 fractions between $\frac{1}{3}$ and $\frac{1}{2}$.

How many fractions lie between $\frac{1}{3}$ and $\frac{1}{2}$ in the sorted set of reduced proper fractions for $d \leq 12,000$?

import qualified Data.Set as Set

primes :: [Int]
primes = 2 : sieve primes [3,5..] where
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
where (h, t) = span (< p*p) xs

factorize :: Int -> [Int]
factorize n = primeFactors n primes where
primeFactors 1 _ = []
primeFactors _ [] = []
primeFactors m (p:ps) | m < p * p = [m]
| r == 0 = p : primeFactors q (p:ps)
| otherwise = primeFactors m ps
where (q, r) = quotRem m p

uniq :: Ord a => [a] -> [a]
uniq xs = uniq' Set.empty xs where
uniq' _ [] = []
uniq' set (y:ys) | Set.member y set = uniq' set ys
| otherwise = y : uniq' (Set.insert y set) xs

mobius :: Int -> Int
mobius n | not squarefree = 0
| otherwise = (-1)^r
where factors = factorize n
uniqFactors = uniq factors
r = length uniqFactors
squarefree = r == length factors

f :: Int -> Int
f m = sum [((n - 1) quot 2) - (n quot 3) | n <- [1..m]]

r :: Int -> Int
r limit = sum [(mobius m) * f (limit quot m) | m <- [1..limit]]

main :: IO ()
main = print $r 12000 $ ghc -O2 -o fraction-range fraction-range.hs
$time ./fraction-range real 0m0.009s user 0m0.008s sys 0m0.000s ## Python #!/usr/bin/env python from fractions import gcd print(sum(1 for d in range(2, 12001) for n in range(1, d) if (n*3 > d) and (n*2 < d) and gcd(n, d) == 1)) $ time python3 fraction-range.py
real   0m47.171s
user   0m46.848s
sys    0m0.012s