Problem 25 "1000-digit Fibonacci number"

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 index of the first term in the Fibonacci sequence to contain 1000 digits?

問 25 「1000桁のフィボナッチ数」

フィボナッチ数列は以下の漸化式で定義される:

最初の12項は以下である.

12番目の項, F12が3桁になる最初の項である.

1000桁になる最初の項の番号を答えよ.

fn main() {
    let constant_1 = (1f64 + 5f64.sqrt()).log10() - 2f64.log10();
    let constant_2 = 5f64.log10() / 2f64;
    let digits_of_nth_fibonacci = |nth: f64| -> f64 { nth * constant_1 - constant_2 };

    let ratio = (1f64 + 5f64.sqrt()) / 2f64;
    let iteration = 10f64.log(ratio);
    let estimation = iteration * 999f64;
    println!("estimation: {} th Fibonacci number would have 1000 digits", estimation);
    let mut n = (estimation - iteration).floor(); // rollback to 999 digits
    assert!(digits_of_nth_fibonacci(n) < 999f64);
    while digits_of_nth_fibonacci(n) < 999f64 {
        n += 1f64;
    }

    println!("{}", n);
    assert_eq!(n as u32, 4782);
}