Project Euler Problem 73 Solution

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