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

use crate::Solution;
use pmath::sequences::{OddNaturalNumbersSeq, OddNaturalNumbersSquaredSeq, Sequence};

problem!(Problem0028, 28, "Number Spiral Diagonals");

impl Solution for Problem0028 {
    fn solve(&self) -> String {
        // the size of the spiral (it is always odd)
        const SPIRAL_SIZE: u64 = 1001;

        // calculate top-right of every "layer" of spiral -> it is square of layer's side length -> calculate other corners by subtracting length of layer sides
        // formula for each "layer" simplifies to 4x^2 - 6x + 6
        // we can handle the first layer (1) as a special case
        // for x we can plug in numbers 3, 5, 7, 9, ... 1001
        // now the formula looks like this:
        // 1 + 4 * (3^2 + 5^2 + 7^2 + 9^2 + ... + 1001^2) - 6 * (3 + 5 + 7 + 9 + ... + 1001) + 6 * floor(1001 / 2)
        // or shorter:
        // 1 + 4 * (sum_of_squares_of_first_n_odd_numbers(floor(1001 / 2) + 1) - 1) - 6 * (sum_of_first_n_odd_numbers(floor(1001 / 2) + 1) - 1) + 6 * floor(1001 / 2)
        // we will be using predefined functions for sum of first n odd numbers and sum of squares of first n odd numbers, but if we expand them, we get:
        // 1 + 4 * ((floor(1001 / 2) + 1) * (2 * (floor(1001 / 2) + 1) + 1) * (2 * (floor(1001 / 2) + 1) - 1) / 3 - 1) - 6 * ((floor(1001 / 2) + 1)^2 - 1) + 6 * floor(1001 / 2)
        // note that these formulas are valid only for odd numbers, but that is ok because spiral size is always odd

        let result = 1 + 4
            * (OddNaturalNumbersSquaredSeq::<u64>::new()
                .sum_next_n((SPIRAL_SIZE / 2 + 1) as usize)
                - 1)
            - 6 * (OddNaturalNumbersSeq::<u64>::new().sum_next_n((SPIRAL_SIZE / 2 + 1) as usize)
                - 1)
            + 6 * (SPIRAL_SIZE / 2);

        result.to_string()
    }
}