extra/project-euler/073/073.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math project-euler.common ;
   4 IN: project-euler.073
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=73
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Consider the fraction, n/d, where n and d are positive integers. If n<d and
  12 ! HCF(n,d) = 1, it is called a reduced proper fraction.
  13
  14 ! If we list the set of reduced proper fractions for d <= 8 in ascending order of
  15 ! size, we get:
  16
  17 !     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,
  18 !     2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
  19
  20 ! It can be seen that there are 3 fractions between 1/3 and 1/2.
  21
  22 ! How many fractions lie between 1/3 and 1/2 in the sorted set of reduced
  23 ! proper fractions for d <= 10,000?
  24
  25
  26 ! SOLUTION
  27 ! --------
  28
  29 ! Use the properties of a Farey sequence and mediants to recursively generate
  30 ! the next fraction until the denominator is as close to 1000000 as possible
  31 ! without going over.
  32
  33 <PRIVATE
  34
  35 :: (euler073) ( counter limit lo hi -- counter' )
  36     lo hi mediant :> m
  37     m denominator limit <= [
  38         counter 1 +
  39         limit lo m (euler073)
  40         limit m hi (euler073)
  41     ] [ counter ] if ;
  42
  43 PRIVATE>
  44
  45 : euler073 ( -- answer )
  46     0 10000 1/3 1/2 (euler073) ;
  47
  48 ! [ euler073 ] 10 ave-time
  49 ! 20506 ms ave run time - 937.07 SD (10 trials)
  50
  51 SOLUTION: euler073