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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

use crate::Solution;

problem!(Problem0029, 29, "Distinct Powers");

impl Solution for Problem0029 {
    fn solve(&self) -> String {
        // let a and b be integers such that 2 <= a <= 100 and 2 <= b <= 100
        // let's define function f(a, b) = a^b
        // and function g(x) = log x
        // g(f(a, b)) = b * log a
        // since f is monotonic (increasing) for a,b >= 2, and g is monotonic (increasing) for x >= 0
        // f . g is also monotonic (increasing) for a,b >= 2
        // (composition of 2 strictly increasing functions is strictly increasing)
        // so f . g is injective for a,b >= 2
        // that means that we can find different values that f . g can take for a,b >= 2
        // the number of those values is the answer to the problem

        // the base for the logarithm doesn't matter as long as it is > 1

        let mut values = Vec::new();

        for a in 2..101 {
            let log_a = (a as f64).log2();
            for b in 2..101 {
                values.push(b as f64 * log_a);
            }
        }

        // now we need to determine how many of these values are distinct
        // since those are floating point numbers, we can't just test them for equality
        // because they have some error
        // we start by sorting the values
        // for every element we will check if the element before it is within 1e-7 of it
        // if it is, it is not distinct and we don't count it

        values.sort_by(|a, b| a.partial_cmp(b).unwrap());
        let mut distinct = 1;
        for i in 1..values.len() {
            if (values[i] - values[i - 1]).abs() > 1e-7 {
                distinct += 1;
            }
        }

        distinct.to_string()
    }
}

// this is slow, manual solution that actually calculates the powers
// fn solve() {
//     let mut powers: Vec<Vec<u64>> = vec![];
//
//     for a in 2..101 {
//         for b in 2..101 {
//             powers.push(power(a, b));
//         }
//     }
//
//     powers.sort();
//     let mut distinct: u64 = 1;
//
//     for i in 1..powers.len() {
//         if powers[i] != powers[i - 1] {
//             distinct += 1;
//         }
//     }
//
//     println!("{}", distinct);
// }
//
// fn power(base: u64, exp: u64) -> Vec<u64>{
//     let mut working_num: Vec<u64> = vec![1];
//
//     for _ in 0..exp {
//         let mut factoring: Vec<Vec<u64>> = vec![];
//         let mut factoring_num: u64 = base;
//
//         while factoring_num != 0 {
//             let mut current_product: Vec<u64> = vec![];
//
//             let mut transfer: u64 = 0;
//             for j in (0..working_num.len()).rev() {
//                 let working_product: u64 = (working_num[j] * (factoring_num % 10)) + transfer;
//                 current_product.insert(0, working_product % 10);
//                 transfer = working_product / 10;
//             }
//             while transfer != 0 {
//                 current_product.insert(0, transfer % 10);
//                 transfer /= 10;
//             }
//
//             factoring.push(current_product);
//
//             factoring_num /= 10;
//         }
//
//         for i in 0..factoring.len() {
//             for _  in 0..i {
//                 factoring[i].push(0)
//             }
//         }
//
//         let mut longest: usize = 0;
//
//         for i in 0..factoring.len() {
//             if factoring[i].len() > longest {
//                 longest = factoring[i].len();
//             }
//         }
//
//         for i in 0..factoring.len() {
//             for _ in 0..(longest - factoring[i].len()) {
//                 factoring[i].insert(0, 0);
//             }
//         }
//
//         let mut result: Vec<u64> = vec![];
//         let mut transfer: u64 = 0;
//         for j in (0..longest).rev() {
//             let mut working_sum: u64 = transfer;
//             for i in 0..factoring.len() {
//                 working_sum += factoring[i][j];
//             }
//             result.insert(0, working_sum % 10);
//             transfer = working_sum / 10;
//         }
//         while transfer != 0 {
//             result.insert(0, transfer % 10);
//             transfer /= 10;
//         }
//
//         working_num = result;
//
//     }
//     working_num
// }