extra/project-euler/071/071.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math project-euler.common sequences ;
   4 IN: project-euler.071
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=71
   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 2/5 is the fraction immediately to the left of 3/7.
  21
  22 ! By listing the set of reduced proper fractions for d <= 1,000,000 in
  23 ! ascending order of size, find the numerator of the fraction immediately to the
  24 ! left of 3/7.
  25
  26
  27 ! SOLUTION
  28 ! --------
  29
  30 ! Use the properties of a Farey sequence by setting an upper bound of 3/7 and
  31 ! then taking the mediant of that fraction and the one to its immediate left
  32 ! repeatedly until the denominator is as close to 1000000 as possible without
  33 ! going over.
  34
  35 <PRIVATE
  36
  37 : penultimate ( seq -- elt )
  38     dup length 2 - swap nth ;
  39
  40 PRIVATE>
  41
  42 : euler071 ( -- answer )
  43     2/5 [ dup denominator 1000000 <= ] [ 3/7 mediant dup ] [ ] produce
  44     nip penultimate numerator ;
  45
  46 ! [ euler071 ] 100 ave-time
  47 ! 155 ms ave run time - 6.95 SD (100 trials)
  48
  49 MAIN: euler071