You are on the Home/Other Tutorials/Project Euler/Problem 25 page
Google
Web This Site

Project Euler - Problem 25

More about Project Euler.

Problem description

The Fibonacci sequence is defined by the recurrence relation:

Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.

Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F_(5) = 5
F_(6) = 8
F_(7) = 13
F_(8) = 21
F_(9) = 34
F_(10) = 55
F_(11) = 89
F_(12) = 144

The 12th term, F_(12), is the first term to contain three digits.

What is the first term in the Fibonacci sequence to contain 1000 digits?

Solution

I don't know of any way to finesse this.  So, brute force it is.  I used the LargeAdd function I developed for Large Number Arithmetic.  Of course, the problem is small enough that the code below solves it in about 0.4 seconds on my laptop.
Sub Euler25()
    Dim Fcurr As String, Fnext As String, I As Integer, ProcTime As Single
    ProcTime = Timer
    Fcurr = 1: Fnext = 1: I = 2
    Do
        Dim Fnew As String
        Fnew = LargeAdd(Fcurr, Fnext)
        Fcurr = Fnext: Fnext = Fnew
        I = I + 1
        Loop Until Len(Fnew) >= 1000
    Debug.Print I, Timer - ProcTime
    End Sub