Project Euler #25: N-digit Fibonacci number

  • + 0 comments

    here is a true O(1) solution. No dp, no loops nothing, Just reverse engineering.

    ; Takes the length of fib return the (index of fib) + 1
    (defn fib-len-rev [l]
      (let [phi (-> (Math/sqrt 5) (+ 1) (/ 2))]
      (-> (+ (dec l)
             (* 1/2 (Math/log10 5)))
          (/ (Math/log10 phi))
          (Math/ceil)
          (int))))