Project Euler – Problem 25 Solution

Problem

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

F5 = 5

F6 = 8

F7 = 13

F8 = 21

F9 = 34

F10 = 55

F11 = 89

F12 = 144

The 12th term, F12, 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.

Enjoy what you’re reading? Subscribe to my newsletter and get more content on AWS and serverless technologies delivered straight to your inbox.


Yan Cui

I’m an AWS Serverless Hero and the author of Production-Ready Serverless. I have run production workload at scale in AWS for nearly 10 years and I have been an architect or principal engineer with a variety of industries ranging from banking, e-commerce, sports streaming to mobile gaming. I currently work as an independent consultant focused on AWS and serverless.

You can contact me via Email, Twitter and LinkedIn.

Hire me.


Check out my new course, Complete Guide to AWS Step Functions.

In this course, we’ll cover everything you need to know to use AWS Step Functions service effectively. Including basic concepts, HTTP and event triggers, activities, design patterns and best practices.

Get Your Copy