# Project Euler #25: 1000-digit Fibonacci number

This article is part of a series where I'll be diving head first into the Project Euler puzzles. I want to document the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that I mean I can't look up any other implementations online. After the implementation, I will validate the answer by using this document or a similar sheet.

In this article I'll be solving: Project Euler #25.

### Introduction

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

I’m going to use the code I used for “Even Fibonacci numbers”, the 2nd Euler puzzle. The code to generating the Fibonacci numbers I used is this one:

``````let mut far = vec![1, 2];

loop {
let n = far.remove(0);
let m = far + n;
far.push(m);
println!("{:?}", far);
}
``````

This will go on until infinity, except right now I need to stop when the number is 1000 digits long. Even with the biggest integer u128 I can’t store a 1000 digit integer, so I have to use my `int_to_vec()` and `sum_vec()` from “Power digit sum”. However, I need to tweak `sum_vec()` slightly because right now it can only sum up values that aren’t bigger than 2 digits.

### Fixing sum_vec()

To fix `sum_vec()` I’m going to write some tests which I know will fail:

``````#[test]
fn test_sum_vec() {
let mut start = vec![9,9,9,9];
start.sum_vec(vec!);
assert_eq!(start, vec![0,0,0,0,1]);
// currently returns [0,10,9,9]
}
``````

This is a relatively simple fix, the `prev_div` (or the remainder) needs to be added constantly to the next cycle of numbers and passed on until it finally will be added in the end, like this:

``````impl VecEx<u8> for Vec<u8> {
fn sum_vec(&mut self, total: &Vec<u8>) {
let mut prev_div = 0;

if self.len() < total.len() {
self.resize(total.len(), 0);
}

for (i, x) in self.iter_mut().enumerate() {
let subt = *x + total.get(i).unwrap_or(&0) + prev_div;
let (div, modulo) = (subt / 10, subt % 10);

*x = modulo;
prev_div = div;
}

if prev_div > 0 {
self.push(prev_div);
}
}
}
``````

Another minor tweak I made is for `total` to be a reference, instead of passing the full vector along.

### Fibonacci with int_to_vec()

While fiddling a little, I came up with this answer:

``````let mut far = 1.to_vec();
let mut addition = 2.to_vec();

loop {
println!("{:?}", far);

// An arbitrary break
if far.len() > 2 {
break;
}
}
``````

The funny thing is that this code skips 2 Fibonacci numbers ahead each time. So the output becomes {3,8,21,55,144}. Now, it could be that the number lies within an even index, or not. To get the other Fibonacci numbers {2,5,13,34,89,233} I have to change the `addition` variable to `1.to_vec()`. In theory, I can get to the answer now:

``````fn fibonacci_thousand(start: u128) -> u128 {
let mut far = 1.to_vec();
let mut addition = start.to_vec();
let mut index = 2 + start;

loop {
index += 2;

if far.len() > 1000 {
break index;
}
}
}

#[test]
fn test_problem_25() {
let odds = fibonacci_thousand(2);
let evens = fibonacci_thousand(1);
let mut result = 0;

if odds > evens {
result = evens;
} else {
result = odds;
}

assert_eq!(result, 4789);
}
``````

I’m remarkably close to the actual answer (4789) which is 4782. I’m 7 indexes off, so it seems. Upon debugging my code, I found a little bug with the indexing. I thought I needed to offset the index by 2, but it seems like I don’t have to do that. It still won’t give me the correct answer, because it still looks like I’m 5 indexes off the mark. After some head scratching I figured out what it is, namely the ancient old `>` vs `>=`. It needs to stop at length 1000 not 1001. The full working code:

``````fn fibonacci_thousand(start: u128, max: usize) -> u128 {
let mut far = 1.to_vec();
let mut addition = start.to_vec();
let mut index = start;

loop {
index += 2;

if far.len() >= max {
break index;
}
}
}

fn problem_25(max: usize) -> u128 {
let i = fibonacci_thousand(2, max);
let k = fibonacci_thousand(1, max);

if i > k {
k
} else {
i
}
}

#[test]
fn test_problem_25() {
assert_eq!(problem_25(1000), 4782);
}
``````

The full solution is available on GitHub.