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;
answer++;
BigInteger second = BigInteger.ONE;
answer++;
BigInteger next = first.add(second);
answer++;

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

System.out.println("Answer: "+answer);

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) {
      answer += current;
   }
}

System.out.println("Answer: "+answer);