extra/project-euler/071/071.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math project-euler.common sequences ;
   4 IN: project-euler.071
   5
   6 ! https://projecteuler.net/problem=71
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Consider the fraction, n/d, where n and d are positive
  12 ! integers. If n<d and HCF(n,d) = 1, it is called a reduced
  13 ! proper fraction.
  14
  15 ! If we list the set of reduced proper fractions for d <= 8 in
  16 ! ascending order of size, we get:
  17
  18 !     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,
  19 !     2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
  20
  21 ! It can be seen that 2/5 is the fraction immediately to the
  22 ! left of 3/7.
  23
  24 ! By listing the set of reduced proper fractions for d <=
  25 ! 1,000,000 in ascending order of size, find the numerator of
  26 ! the fraction immediately to the left of 3/7.
  27
  28
  29 ! SOLUTION
  30 ! --------
  31
  32 ! Use the properties of a Farey sequence by setting an upper
  33 ! bound of 3/7 and then taking the mediant of that fraction and
  34 ! the one to its immediate left repeatedly until the denominator
  35 ! is as close to 1000000 as possible without going over.
  36
  37 : euler071 ( -- answer )
  38     2/5 [ dup denominator 1000000 <= ] [ 3/7 mediant dup ] produce
  39     nip penultimate numerator ;
  40
  41 ! [ euler071 ] 100 ave-time
  42 ! 155 ms ave run time - 6.95 SD (100 trials)
  43
  44 SOLUTION: euler071