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
30
31
32
33
34
35
36
37
38
39
40
41
42
43

use crate::Solution;

problem!(Problem0001, 1, "Multiples of 3 or 5");

impl Solution for Problem0001 {
    fn solve(&self) -> String {
        const UPPER_LIMIT: i32 = 1000;

        // sum of multiples of 3 looks like this:
        // 1*3 + 2*3 + 3*3 + 4*3 + 5*3 + ... + n*3
        // n*3 is the last multiple of 3 that is less than UPPER_LIMIT (1000)
        // we can find this n by dividing (UPPER_LIMIT - 1) (because we don't actually want to include UPPER_LIMIT) by 3 and rounding down
        // so n = (UPPER_LIMIT - 1) / 3
        // we can rewrite this sum as:
        // 3 * (1 + 2 + 3 + 4 + 5 + ... + n)
        // or:
        // 3 * n * (n + 1) / 2
        // similarly for multiples of 5:
        // 5 * (1 + 2 + 3 + 4 + 5 + ... + m)
        // or:
        // 5 * m * (m + 1) / 2
        // where m = (UPPER_LIMIT - 1) / 5
        // if we sum these expressions we will get the result that is higher than expected
        // that is because we are actually counting numbers that are multiples of both 3 and 5 twice
        // so we need to subtract the sum of multiples of 15 (multiples of 3 and 5)
        // for 15 we have:
        // 15 * (1 + 2 + 3 + 4 + 5 + ... + k)
        // or:
        // 15 * k * (k + 1) / 2
        // where k = (UPPER_LIMIT - 1) / 15
        // now we can solve the problem

        let n = (UPPER_LIMIT - 1) / 3;
        let m = (UPPER_LIMIT - 1) / 5;
        let k = (UPPER_LIMIT - 1) / 15;

        let sum_3 = 3 * n * (n + 1) / 2;
        let sum_5 = 5 * m * (m + 1) / 2;
        let sum_15 = 15 * k * (k + 1) / 2;

        (sum_3 + sum_5 - sum_15).to_string()
    }
}