Yan Cui

I help clients go faster for less using serverless technologies.

#### Problem

The Fibonacci sequence is defined by the recurrence relation:

F_{n}= F_{n-1}+ F_{n-2}, where F_{1}= 1 and F_{2}= 1.

Hence the first 12 terms will be:

F_{1}= 1

F_{2}= 1

F_{3}= 2

F_{4}= 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

let fibonacciSeq = Seq.unfold (fun (current, next) -> Some(current, (next, current + next))) (0I, 1I) |> Seq.filter (fun f -> f > 0I) let answer = (Seq.findIndex (fun f -> f.ToString().Length >= 1000) fibonacciSeq) + 1

In my solution here I first created a Fibonacci sequence which starts with 1, 1, … all the way to infinity, and the second expression gives us the answer to the problem by using Seq.findIndex to find the index (zero-based) of the first element which contains 1000 digits. The ‘+ 1’ at the end simply converts the zero-based index to the one-based index which the problem is asking for.

**Whenever you’re ready, here are 4 ways I can help you:**

**Production-Ready Serverless**: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for**quickly levelling up your serverless skills**.- Do you want to know
**how to test serverless architectures**with a fast dev & test loop? Check out my latest course,**Testing Serverless Architectures**and learn the smart way to test serverless. - I help clients
**launch product ideas**,**improve their development processes**and**upskill their teams**. If you’d like to work together, then let’s**get in touch**. **Join my community on Discord**, ask questions, and join the discussion on all things AWS and Serverless.

Nikolay ArtamonovInstead of ineffective counting of length of every next Fibonacci number with String.Length property, you may compare every next number with number 10^999 (10 powered by 999). So you drop all Fibonacci numbers are strictly less than 10^999 (N < 10^999) and next number will be the answer.

Omucan’t resist the force

let p25 =

let rec loop i n1 n2 =

match n2 with

|n when n > 10I**999 -> (i, n2)

|n -> loop (i+1I) n2 (n1+n2)

loop 2I 1I 1I;

runs instantly