## 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:

$\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$?

## Haskell

```
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.007s
user 0m0.000s
sys 0m0.007s
```