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

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   0m35.286s
user   0m35.284s
sys    0m0.000s