(* 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 ¿ 10,000?
*)

let rec gcd a b =
	if ( b = 0 )
	then a
	else gcd b ( a mod b )
;;


let count =
  (* count x/y between 1/3 and 1/2 *)
  let rec count x y n =
    if(y<2) then n else
    if( 2*x >= y ) then (count 1 (y-1) n) else
    if( y >= 3*x ) then (count (x+1) y n) else
    count (x+1) y (if (gcd x y > 1) then n else (n+1))
  in
    count 1 10000 0
;;

Printf.printf "%d\n" count;;