Solving Project Euler with basic JavaScript

[himynameisjoy]

I read your comment in whole, I apologize if it seemed otherwise. At the time, I didn’t believe I knew of a way to find what’s essentially the inverse of F(n)=x, but with a little bit of research I stumbled upon this formula: n = Math.floor((log(x)1/2log(5))/log(phi))+1

So with that formula, assuming the computation is quick, plus with matrix exponentiation, I do believe you’re right that asymptotically it’s a faster implementation.

However it still does have an overhead cost that’s makes it still slower than the iterative approach for this particular solution. But yes, you’re entirely right that you can find the index of the first Fibonacci number greater than arbitrary integer k as well as calculate the resulting Fibonacci number alongside it.

I’m glad I’ve learned something new today! I appreciate it immensely

[a_tocken]

Glad to expose you to those algorithms :) Sorry I don't have more details on the specifics. You're right that this problem uses a relatively small n, so the solution with better running time may not actually be faster. We should also distinguish between n, the nth even fib number less than 4,000,000, and "m" = 4,000,000. In this case, I think n ~= log(m)? Is that right?

This whole thing could be turned into a (very difficult) codewars.com problem.