Project Euler – Problem 25


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

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?

My Solution:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Oyster.Math;

namespace Euler
{
    class Problem25 : IProblemBase
    {

        //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?

        public Problem25()
        {
        }

        public string GetAnswer()
        {
            string result = "2";
            string runningTotal = "0";
            string sequenceOne = "1";
            string sequenceTwo = "2";
            int terms = 2;//starting at 2nd term

            while (sequenceOne.Length < 1000)
            {
                runningTotal = Util.BigAdd(sequenceOne ,sequenceTwo);
                sequenceOne = sequenceTwo;
                sequenceTwo = runningTotal;

                result = Util.BigAdd(result,sequenceTwo);
                terms++;

            }

            return terms.ToString();

        }

    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: