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