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[0] + 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![1]);
    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 {
    far.sum_vec(&addition);
    addition.sum_vec(&far);
    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 {
        far.sum_vec(&addition);
        addition.sum_vec(&far);
        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 {
        far.sum_vec(&addition);
        addition.sum_vec(&far);
        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.

55545352515049484746454443424140393837363534333231302928272625242322212019181716151413121110987654321