Problem 65 "Convergents of e"

The square root of 2 can be written as an infinite continued fraction.

\[\sqrt{2} = 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + ...}}}}\]

The infinite continued fraction can be written, \(\sqrt{2} = [1; (2)]\), \((2)\) indicates that 2 repeats ad infinitum. In a similar way, \(\sqrt{23} = [4; (1, 3, 1, 8)]\).

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for \(\sqrt{2}\).

\[ 1 + \dfrac{1}{2} = \dfrac{3}{2}\\ 1 + \dfrac{1}{2 + \dfrac{1}{2}} = \dfrac{7}{5}\\ 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}} = \dfrac{17}{12}\\ 1 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2 + \dfrac{1}{2}}}} = \dfrac{41}{29} \]

Hence the sequence of the first ten convergents for \(\sqrt{2}\) are:

\[1, \dfrac{3}{2}, \dfrac{7}{5}, \dfrac{17}{12}, \dfrac{41}{29}, \dfrac{99}{70}, \dfrac{239}{169}, \dfrac{577}{408}, \dfrac{1393}{985}, \dfrac{3363}{2378}, ...\]

What is most surprising is that the important mathematical constant,
\[e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, ... , 1, 2k, 1, ...]\]

The first ten terms in the sequence of convergents for e are:

\[2, 3, \dfrac{8}{3}, \dfrac{11}{4}, \dfrac{19}{7}, \dfrac{87}{32}, \dfrac{106}{39}, \dfrac{193}{71}, \dfrac{1264}{465}, \dfrac{1457}{536}, ...\]

The sum of digits in the numerator of the 10th convergent is \(1 + 4 + 5 + 7 = 17\).

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for \(e\).

問 65 「e の近似分数」

2の平方根は無限連分数として書くことができる.

無限連分数である √2 = [1;(2)] と書くことができるが, (2) は2が無限に繰り返されることを示す. 同様に, √23 = [4;(1,3,1,8)].

平方根の部分的な連分数の数列から良い有理近似が得られることが分かる.√2の近似分数について考えよう.

従って, √2の近似分数からなる数列の最初の10項は：

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

もっとも驚くべきことに, 数学的に重要な定数,

e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

e の近似分数からなる数列の最初の10項は：

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

10項目の近似分数の分子の桁を合計すると1+4+5+7=17である.

e についての連分数である近似分数の100項目の分子の桁の合計を求めよ.

Big numbers

mod bignum {
    #[derive(Clone)]
    pub struct BigNum {
        v: Vec<u64>,
    }

    impl BigNum {
        const TEN_MIL: u64 = 10_000_000_000;
        pub fn new(n: u8) -> Self {
            Self { v: vec![n as u64] }
        }
        fn merge(&mut self, page: usize, n: u64, carry: &mut u64) {
            if self.v.get(page).is_none() {
                self.v.push(0u64)
            }
            if let Some(con) = self.v.get_mut(page) {
                *con += n + *carry;
                if *con < Self::TEN_MIL {
                    *carry = 0;
                    return;
                }
                *carry = 1;
                *con -= Self::TEN_MIL;
            }
        }
        pub fn add(&mut self, b: &BigNum) {
            let mut p = 0usize;
            let mut carry = 0u64;
            let mut ite = b.v.iter();
            while let Some(n) = ite.next() {
                self.merge(p, *n, &mut carry);
                p += 1;
            }
            while carry != 0 {
                self.merge(p, 0, &mut carry);
                p += 1;
            }
        }
        pub fn multiply(&mut self, n: u8) {
            let mut carry = 0u64;
            for con in self.v.iter_mut() {
                *con = *con * n as u64 + carry;
                if *con < Self::TEN_MIL {
                    carry = 0;
                    continue;
                }
                carry = *con / Self::TEN_MIL;
                *con %= Self::TEN_MIL;
            }
            if carry != 0 {
                self.v.push(carry);
            }
        }
        pub fn digit_sum(&self) -> u32 {
            let mut sum = 0u32;
            for &con in &self.v {
                let mut t = con;
                while t > 0 {
                    sum += (t % 10) as u32;
                    t /= 10;
                }
            }
            sum
        }
    }
}

struct EulerNumberNumerator {
    prev: bignum::BigNum,
    value: bignum::BigNum,
    term: u8,
}

fn main() {
    let mut enn = EulerNumberNumerator {
        prev: bignum::BigNum::new(3),
        value: bignum::BigNum::new(8),
        term: 3,
    };
    while enn.term < 100 {
        enn.term += 1;
        let t = enn.value.clone();
        if enn.term % 3 == 0 {
            let k = enn.term / 3;
            enn.value.multiply(2 * k);
        }
        enn.value.add(&enn.prev);
        enn.prev = t;
    }
    let sum = enn.value.digit_sum();
    println!("{}", sum);
    assert_eq!(sum, 272);
}