Rust Implementation of Problem 25

View source code here on GitHub!

Problem Solution

pub fn problems::p0025::p0025() -> utils::Answer
 1/*
 2Project Euler Problem 25
 3
 4Problem:
 5
 6The Fibonacci sequence is defined by the recurrence relation:
 7
 8    Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
 9
10Hence the first 12 terms will be:
11
12    F1 = 1
13    F2 = 1
14    F3 = 2
15    F4 = 3
16    F5 = 5
17    F6 = 8
18    F7 = 13
19    F8 = 21
20    F9 = 34
21    F10 = 55
22    F11 = 89
23    F12 = 144
24
25The 12th term, F12, is the first term to contain three digits.
26
27What is the index of the first term in the Fibonacci sequence to contain 1000
28digits?
29*/
30use crate::include::utils::Answer;
31
32pub fn p0025() -> Answer {
33    let mut answer: u64 = 0;
34    let mut a: Vec<u64> = vec![0];
35    let mut b: Vec<u64> = vec![1];
36    loop {
37        answer += 1;
38        let mut overflow: bool = false;
39        let mut result: u64;
40//        println!("{:?} + {:?}", a, b);
41        for i in 0..b.len() {
42            (result, overflow) = b[i].overflowing_add(a[i] + overflow as u64);
43            a[i] = b[i];
44            b[i] = result;
45        }
46        if overflow {
47            b.push(1);
48            a.push(0);
49        }
50        // below approximates log10(a) >= 999
51        if a.len() >= 52 && a[a.len() - 1] > (1 << 54) + (1 << 53) {
52            break;
53        }
54    }
55    return Answer::Int(answer.into());
56}

Tags: permutation, lexicographic-ordering, combinatorics