peuler 0.1.0

A Rust crate with solutions to the Project Euler problems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

use crate::Solution;

problem!(Problem0073, 73, "Counting Fractions in a Range");

impl Solution for Problem0073 {
    fn solve(&self) -> String {
        // this is Farey sequence
        // for every pair of fractions a/b and c/d, we can find some fraction between them using the formula:
        // (a+c)/(b+d)
        // if b+d <= 12_000, we count the number of fractions between a/b and (a+c)/(b+d) and (a+c)/(b+d) and c/d, and add 1
        // this is recursive process, so we just continue until b+d > 12_000 in which case we return 0

        frac_between(1, 3, 1, 2).to_string()
    }
}

const MAX_DEN: u16 = 12_000; // maximum denominator

/// Count the number of reduced proper fractions between `a/b` and `c/d` whose denominator does not exceed `MAX_DEN`.
fn frac_between(a: u16, b: u16, c: u16, d: u16) -> u32 {
    let new_den = b + d;

    if new_den > MAX_DEN {
        0
    } else {
        let new_num = a + c;
        1 + frac_between(a, b, new_num, new_den) + frac_between(new_num, new_den, c, d)
    }
}