Project Euler – Problem 25 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

This article is brought to you by

Hookdeck: The Serverless Event Gateway

Hookdeck is a reliable and scalable serverless event gateway for sending, receiving, authenticating, transforming, filtering, and routing events between services in your event-driven architecture.

Learn more

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.

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

  1. 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.
  2. 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.
  3. 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.
  4. Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.

2 thoughts on “Project Euler – Problem 25 Solution”

  1. Nikolay Artamonov

    Instead 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.

  2. can’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

Leave a Comment

Your email address will not be published. Required fields are marked *