extra/project-euler/057/057.factor

   1 ! Copyright (c) 2008 Samuel Tardieu
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions math.parser math.ranges project-euler.common
   4     sequences ;
   5 IN: project-euler.057
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=57
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! It is possible to show that the square root of two can be expressed
  13 ! as an infinite continued fraction.
  14
  15 !     √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
  16
  17 ! By expanding this for the first four iterations, we get:
  18
  19 !     1 + 1/2 = 3/2 = 1.5
  20 !     1 + 1/(2 + 1/2) = 7/5 = 1.4
  21 !     1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
  22 !     1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
  23
  24 ! The next three expansions are 99/70, 239/169, and 577/408, but the
  25 ! eighth expansion, 1393/985, is the first example where the number of
  26 ! digits in the numerator exceeds the number of digits in the
  27 ! denominator.
  28
  29 ! In the first one-thousand expansions, how many fractions contain a
  30 ! numerator with more digits than denominator?
  31
  32 ! SOLUTION
  33 ! --------
  34
  35 : longer-numerator? ( seq -- ? )
  36     >fraction [ number>string length ] bi@ > ; inline
  37
  38 : euler057 ( -- answer )
  39     0 1000 <iota> [ drop 2 + recip dup 1 + longer-numerator? ] count nip ;
  40
  41 ! [ euler057 ] 100 ave-time
  42 ! 1728 ms ave run time - 80.81 SD (100 trials)
  43
  44 SOLUTION: euler057