Algorithm notes on the back of used envelopes bound in a ring binder

• Q.5 Smallest multiple
• Q.26 Reciprocal cycles

struct Fraction {
    deno_prev: u64,
    deno: u64,
    nume: u64,
    n: u32,
}

impl Fraction {
    fn new() -> Self {
        let deno_prev = 2u64;
        let deno = 5u64;
        Self {
            deno_prev,
            deno,
            nume: deno_prev + deno,
            n: 2,
        }
    }
    fn increment(&mut self) {
        self.n += 1;
        self.deno_prev = self.deno;
        self.deno += self.nume;
        self.nume = self.deno_prev + self.deno;
        const THRESHOLD: u64 = {
            let mut threshold = 1u64;
            while threshold < u64::MAX / 100 {
                threshold *= 10;
            }
            threshold
        };
        if self.deno > THRESHOLD && self.nume > THRESHOLD {
            self.deno /= 10;
            self.nume /= 10;
        }
    }
    fn has_numerator_more_digits(&self) -> bool {
        let mut n = self.nume;
        let mut d = self.deno;
        while n > 0 && d > 0 {
            n /= 10;
            d /= 10;
        }
        n > d
    }
}

fn main() {
    let mut count = 0u32;
    let mut frac = Fraction::new();
    while {
        if frac.has_numerator_more_digits() {
            count += 1;
        }
        frac.increment();
        frac.n <= 1000
    } {}

    println!("{}", count);
    assert_eq!(count, 153);
}

• Q.13 Large sum
• Q.16 Power digit sum

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

impl BigNum {
    const TEN_MIL: u64 = 10_000_000_000;
    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;
        }
    }
    fn double(&mut self) -> &Self {
        let mut carry = 0u64;
        for con in self.v.iter_mut() {
            *con *= 2;
            *con += carry;
            if *con < Self::TEN_MIL {
                carry = 0;
                continue;
            }
            carry = 1;
            *con -= Self::TEN_MIL;
        }
        if carry != 0 {
            self.v.push(1u64);
        }
        self
    }
    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;
        }
    }
}

struct Fraction {
    deno: BigNum,
    nume: BigNum,
    n: u32,
}

impl Fraction {
    fn new() -> Self {
        Self {
            deno: BigNum::new(5),
            nume: BigNum::new(7),
            n: 2,
        }
    }
    fn increment(&mut self) {
        self.n += 1;
        let t = self.nume.clone();
        self.nume.add(self.deno.clone().double());
        self.deno.add(&t);
    }
    fn has_numerator_more_digits(&self) -> bool {
        if self.nume.v.len() != self.deno.v.len() {
            return self.nume.v.len() > self.deno.v.len();
        }
        let mut n = *self.nume.v.last().expect("BigNum must have a container");
        let mut d = *self.deno.v.last().expect("BigNum must have a container");
        while n > 0 && d > 0 {
            n /= 10;
            d /= 10;
        }
        n > d
    }
}

fn main() {
    let mut count = 0u32;
    let mut frac = Fraction::new();
    while {
        if frac.has_numerator_more_digits() {
            count += 1;
        }
        frac.increment();
        frac.n <= 1000
    } {}

    println!("{}", count);
    assert_eq!(count, 153);
}

• Q.2 Even Fibonacci numbers

• Convergence to √2, stackexchange

• How to solve linear recurrence relations with constant coefficients, stackexchange

• https://projecteuler.net/action=quote;post_id=10616

fn main() {
    let r1 = 1f64 + 2f64.sqrt();
    let r2 = 1f64 - 2f64.sqrt();
    let deno_c = 1.5f64 * 2f64.log10();
    let nume_c = 2f64.log10();
    let log10_r1 = r1.log10();
    let r2_over_r1 = r2 / r1;

    let mut count = 0u32;
    let mut pow = r2_over_r1.clone();
    for n in 2u32..=1001 {
        pow *= r2_over_r1;
        let nlog10r1 = n as f64 * log10_r1;
        let deno_digit = (nlog10r1 + (1f64 - pow).log10() - deno_c) as u32;
        let nume_digit = (nlog10r1 + (1f64 + pow).log10() - nume_c) as u32;
        if nume_digit > deno_digit {
            count += 1;
        }
    }

    println!("{}", count);
    assert_eq!(count, 153);
}

fn main() {
    let r1 = 1f64 + 2f64.sqrt();
    let deno_c = 1.5f64 * 2f64.log10();
    let nume_c = 2f64.log10();
    let log10_r1 = r1.log10();

    let mut count = 0u32;
    for n in 2u32..=1001 {
        let nlog10r1 = n as f64 * log10_r1;
        let deno_digit = (nlog10r1 - deno_c) as u32;
        let nume_digit = (nlog10r1 - nume_c) as u32;
        if nume_digit > deno_digit {
            count += 1;
        }
    }

    println!("{}", count);
    assert_eq!(count, 153);
}