extra/project-euler/025/025.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.constants math.functions math.parser memoize
   4     project-euler.common sequences ;
   5 IN: project-euler.025
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=25
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The Fibonacci sequence is defined by the recurrence relation:
  13
  14 !     Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
  15
  16 ! Hence the first 12 terms will be:
  17
  18 !     F1 = 1
  19 !     F2 = 1
  20 !     F3 = 2
  21 !     F4 = 3
  22 !     F5 = 5
  23 !     F6 = 8
  24 !     F7 = 13
  25 !     F8 = 21
  26 !     F9 = 34
  27 !     F10 = 55
  28 !     F11 = 89
  29 !     F12 = 144
  30
  31 ! The 12th term, F12, is the first term to contain three digits.
  32
  33 ! What is the first term in the Fibonacci sequence to contain 1000 digits?
  34
  35
  36 ! SOLUTION
  37 ! --------
  38
  39 ! Memoized brute force
  40
  41 MEMO: fib ( m -- n )
  42     dup 1 > [ 1- dup fib swap 1- fib + ] when ;
  43
  44 <PRIVATE
  45
  46 : (digit-fib) ( n term -- term )
  47     2dup fib number>string length > [ 1+ (digit-fib) ] [ nip ] if ;
  48
  49 : digit-fib ( n -- term )
  50     1 (digit-fib) ;
  51
  52 PRIVATE>
  53
  54 : euler025 ( -- answer )
  55     1000 digit-fib ;
  56
  57 ! [ euler025 ] 10 ave-time
  58 ! 5345 ms ave run time - 105.91 SD (10 trials)
  59
  60
  61 ! ALTERNATE SOLUTIONS
  62 ! -------------------
  63
  64 ! A number containing 1000 digits is the same as saying it's greater than 10**999
  65 ! The nth Fibonacci number is Phi**n / sqrt(5) rounded to the nearest integer
  66 ! Thus we need we need "Phi**n / sqrt(5) > 10**999", and we just solve for n
  67
  68 <PRIVATE
  69
  70 : digit-fib* ( n -- term )
  71     1- 5 log10 2 / + phi log10 / ceiling >integer ;
  72
  73 PRIVATE>
  74
  75 : euler025a ( -- answer )
  76     1000 digit-fib* ;
  77
  78 ! [ euler025a ] 100 ave-time
  79 ! 0 ms ave run time - 0.17 SD (100 trials)
  80
  81 MAIN: euler025a