## Project Euler: Problem 25 – 1000-digit Fibonacci number

#### Problem 25:

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?

#### Idea:

Since we don’t know which Fibonacci number we need to calculate to get 1000 digits, I immediately ruled out using a recursive function (although I probably could’ve used memoization to speed up the process). Since I don’t need to hold onto any of the previous Fibonacci numbers, however, there’s no point is saving them, all I really need are the previous 2 Fibonacci numbers to calculate the next one, then just check if the next one has at least 1000 digits.

```int answer = 0;

BigInteger first = BigInteger.ONE;
BigInteger second = BigInteger.ONE;

while(next.toString().length() < 1000) {
first = second;
second = next;
}

## Project Euler: Problem 2 – Even Fibonacci numbers

#### Problem 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

#### Idea:

Since we don’t need to keep track of any of the Fibonacci numbers we can just keep a running total of the even numbered Fibonacci numbers as we go, until the next number generated is greater than 4 million.

```long answer = 2; //starting on 3rd term = 3, previous even fib number = 2

long first = 1;
long second = 2;
long current = first+second;

while(current < 4000000) {
first = second;
second = current;
current = first+second;

if(current % 2 == 0) {