extra/project-euler/025/025.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.constants math.functions math.parser
   4 project-euler.common sequences ;
   5 IN: project-euler.025
   6
   7 ! https://projecteuler.net/problem=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
  34 ! 1000 digits?
  35
  36
  37 ! SOLUTION
  38 ! --------
  39
  40 ! Memoized brute force
  41
  42 MEMO: fib ( m -- n )
  43     dup 1 > [ [ 1 - fib ] [ 2 - fib ] bi + ] when ;
  44
  45 <PRIVATE
  46
  47 : (digit-fib) ( n term -- term )
  48     2dup fib number>string length > [ 1 + (digit-fib) ] [ nip ] if ;
  49
  50 : digit-fib ( n -- term )
  51     1 (digit-fib) ;
  52
  53 PRIVATE>
  54
  55 : euler025 ( -- answer )
  56     1000 digit-fib ;
  57
  58 ! [ euler025 ] 10 ave-time
  59 ! 5345 ms ave run time - 105.91 SD (10 trials)
  60
  61
  62 ! ALTERNATE SOLUTIONS
  63 ! -------------------
  64
  65 ! A number containing 1000 digits is the same as saying it's greater than 10**999
  66 ! The nth Fibonacci number is Phi**n / sqrt(5) rounded to the nearest integer
  67 ! Thus we need we need "Phi**n / sqrt(5) > 10**999", and we just solve for n
  68
  69 <PRIVATE
  70
  71 : digit-fib* ( n -- term )
  72     1 - 5 log10 2 / + phi log10 / ceiling >integer ;
  73
  74 PRIVATE>
  75
  76 : euler025a ( -- answer )
  77     1000 digit-fib* ;
  78
  79 ! [ euler025a ] 100 ave-time
  80 ! 0 ms ave run time - 0.17 SD (100 trials)
  81
  82 SOLUTION: euler025a