jabba_lib/
jmath.rs

1//! math
2
3use crate::jvec;
4use num_bigint::BigInt;
5
6/// Returns `true` if the given number is palindrome.
7///
8/// # Examples
9///
10/// ```
11/// let number = 101;
12/// let answer = jabba_lib::jmath::is_palindrome(number);
13///
14/// assert_eq!(answer, true);
15/// ```
16pub fn is_palindrome(number: i32) -> bool {
17    let v = digits(number as u64);
18    jvec::is_palindrome(&v)
19}
20
21/// Returns `true` if the given number is prime.
22///
23/// Note that this solution is not efficient. If you want to test
24/// lots of and/or large numbers, use a more efficient solution.
25///
26/// # Examples
27///
28/// ```
29/// let number = 23;
30/// let answer = jabba_lib::jmath::is_prime(number);
31///
32/// assert_eq!(answer, true);
33/// ```
34pub fn is_prime(n: u64) -> bool {
35    if n < 2 {
36        return false;
37    }
38    if n == 2 {
39        return true;
40    }
41    if n % 2 == 0 {
42        return false;
43    }
44
45    let mut i: u64 = 3;
46    let maxi: f64 = (n as f64).sqrt() + 1.0;
47    while (i as f64) <= maxi {
48        if n % i == 0 {
49            return false;
50        }
51        i += 2;
52    }
53
54    true
55}
56
57//-------------------------------------
58
59#[derive(Debug)]
60pub struct Primes {
61    value: u64,
62}
63
64impl Primes {
65    pub fn new() -> Primes {
66        Primes { value: 1 }
67    }
68}
69
70impl Iterator for Primes {
71    type Item = u64;
72
73    // not efficient
74    fn next(&mut self) -> Option<u64> {
75        loop {
76            self.value += if self.value >= 3 { 2 } else { 1 };
77            if is_prime(self.value) {
78                return Some(self.value);
79            }
80        }
81    }
82}
83
84//-------------------------------------
85
86/// Returns the prime divisors of the given number.
87///
88/// # Examples
89///
90/// ```
91/// let number = 13195;
92/// let answer = jabba_lib::jmath::get_prime_divisors(number);
93///
94/// assert_eq!(answer, vec![5, 7, 13, 29]);
95/// ```
96pub fn get_prime_divisors(number: u64) -> Vec<u64> {
97    let mut result = vec![];
98
99    let mut n = number;
100    let mut primes = Primes::new();
101    while n != 1 {
102        let prime = primes.next().unwrap();
103        while n % prime == 0 {
104            n /= prime;
105            result.push(prime);
106        }
107    }
108
109    result
110}
111
112/// Returns the digits of the given number.
113///
114/// Similar to Julia's `digits()` function.
115///
116/// # Examples
117///
118/// ```
119/// let number = 1977;
120/// let answer = jabba_lib::jmath::digits(number);
121///
122/// assert_eq!(answer, vec![1, 9, 7, 7]);
123/// ```
124pub fn digits(number: u64) -> Vec<i32> {
125    if number == 0 {
126        return vec![0];
127    }
128    // else
129    let mut result = vec![];
130    let mut n = number;
131
132    while n > 0 {
133        let digit = n % 10;
134        result.push(digit as i32);
135        n /= 10;
136    }
137    result.reverse();
138
139    result
140}
141
142/// Returns the decimal digits inside a string.
143///
144/// Non-digit characters are discarded.
145///
146/// # Examples
147///
148/// ```
149/// assert_eq!(jabba_lib::jmath::digits_from_str("1977"), vec![1, 9, 7, 7]);
150/// assert_eq!(jabba_lib::jmath::digits_from_str("19abc77"), vec![1, 9, 7, 7]);
151/// assert_eq!(jabba_lib::jmath::digits_from_str("ee:ff:90:ac:de"), vec![9, 0]);
152/// ```
153pub fn digits_from_str(s: &str) -> Vec<i32> {
154    s.chars()
155        .filter(|c| c.is_ascii_digit())
156        .map(|c| char::to_digit(c, 10).unwrap() as i32)
157        .collect::<Vec<_>>()
158}
159
160/// Returns all the primes below the given number.
161///
162/// The method uses Aristotle's sieve algorithm.
163///
164/// # Examples
165///
166/// ```
167/// let primes = jabba_lib::jmath::get_primes_below(10);
168///
169/// assert_eq!(primes, vec![2, 3, 5, 7]);
170/// ```
171pub fn get_primes_below(size: usize) -> Vec<usize> {
172    let mut v = vec![true; size];
173    v[0] = false; // 0 is not prime
174    v[1] = false; // 1 is not prime
175
176    for i in 2..size {
177        if v[i] {
178            for pos in (i + i..size).step_by(i) {
179                v[pos] = false;
180            }
181        }
182    }
183
184    let mut result = vec![];
185    for (i, value) in v.into_iter().enumerate() {
186        if value {
187            result.push(i);
188        }
189    }
190
191    result
192}
193
194/// Returns the divisors of the given number.
195///
196/// # Examples
197///
198/// ```
199/// let number = 28;
200/// let answer = jabba_lib::jmath::get_divisors(number);
201///
202/// assert_eq!(answer, vec![1, 2, 4, 7, 14, 28]);
203/// ```
204pub fn get_divisors(number: u64) -> Vec<u64> {
205    assert!(number > 0);
206
207    let mut result = vec![1];
208
209    let half = number / 2;
210    for i in 2..half + 1 {
211        if number % i == 0 {
212            result.push(i);
213        }
214    }
215
216    if number > 1 {
217        result.push(number);
218    }
219
220    result
221}
222
223/// Returns the proper divisors of the given number `n`.
224///
225/// Proper divisors: numbers less than `n` which divide evenly into `n`.
226///
227/// # Examples
228///
229/// ```
230/// let number = 28;
231/// let answer = jabba_lib::jmath::get_proper_divisors(number);
232///
233/// assert_eq!(answer, vec![1, 2, 4, 7, 14]);
234/// ```
235pub fn get_proper_divisors(number: u64) -> Vec<u64> {
236    let mut result = get_divisors(number);
237    result.pop();
238    result
239}
240
241/// Returns the Collatz sequence of the given number.
242///
243/// # Examples
244///
245/// ```
246/// let number = 13;
247/// let answer = jabba_lib::jmath::get_collatz_sequence(number);
248///
249/// assert_eq!(answer, vec![13, 40, 20, 10, 5, 16, 8, 4, 2, 1]);
250/// ```
251pub fn get_collatz_sequence(number: u64) -> Vec<u64> {
252    assert!(number > 0);
253
254    let mut n = number;
255    let mut result = vec![n];
256
257    while n != 1 {
258        if n % 2 == 0 {
259            n /= 2;
260        } else {
261            n = 3 * n + 1;
262        }
263        result.push(n);
264    }
265    result
266}
267
268/// Returns the factorial of the given number.
269///
270/// # Examples
271///
272/// ```
273/// let number = 5;
274/// let answer = jabba_lib::jmath::factorial(number);
275///
276/// assert_eq!(answer, 5 * 4 * 3 * 2 * 1);
277/// ```
278pub fn factorial(n: u128) -> u128 {
279    let mut result = 1;
280    for i in 2..n + 1 {
281        result *= i;
282    }
283    result
284}
285
286/// Returns the factorial of the given number as a BigInt.
287///
288/// # Examples
289///
290/// ```
291/// assert_eq!(jabba_lib::jmath::factorial_bigint(33).to_string(), "8683317618811886495518194401280000000");
292/// assert_eq!(jabba_lib::jmath::factorial_bigint(10).to_string(), jabba_lib::jmath::factorial(10).to_string());
293/// ```
294pub fn factorial_bigint(n: u128) -> BigInt {
295    let mut result = BigInt::from(1);
296    for i in 2..n + 1 {
297        result *= i;
298    }
299    result
300}
301
302// ==========================================================================
303
304#[cfg(test)]
305mod tests {
306    use super::*;
307
308    #[test]
309    fn is_palindrome_test() {
310        assert!(is_palindrome(0));
311        assert!(is_palindrome(1));
312        assert!(is_palindrome(11));
313        assert!(is_palindrome(101));
314        assert!(is_palindrome(123454321));
315        //
316        assert_eq!(is_palindrome(10), false);
317        assert_eq!(is_palindrome(25), false);
318        assert_eq!(is_palindrome(2022), false);
319    }
320
321    #[test]
322    fn is_prime_test1() {
323        assert_eq!(is_prime(0), false);
324        assert_eq!(is_prime(1), false);
325        assert_eq!(is_prime(2), true);
326        assert_eq!(is_prime(3), true);
327        assert_eq!(is_prime(4), false);
328        assert_eq!(is_prime(5), true);
329        assert_eq!(is_prime(9), false);
330        assert_eq!(is_prime(11), true);
331        assert_eq!(is_prime(97), true);
332        assert_eq!(is_prime(100), false);
333    }
334
335    #[test]
336    fn generate_primes_below_100() {
337        let numbers = [
338            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
339            89, 97,
340        ];
341        let mut primes = Primes::new();
342        let result: Vec<u64> = (0..)
343            .map(|_| primes.next().unwrap())
344            .take_while(|&x| x < 100)
345            .collect();
346        assert_eq!(result, numbers);
347    }
348
349    #[test]
350    fn get_prime_divisors_test() {
351        assert_eq!(get_prime_divisors(4), [2, 2]);
352        assert_eq!(get_prime_divisors(3), [3]);
353        assert_eq!(get_prime_divisors(2), [2]);
354        assert_eq!(get_prime_divisors(13195), [5, 7, 13, 29]);
355    }
356
357    #[test]
358    fn digits_test() {
359        assert_eq!(digits(123), [1, 2, 3]);
360        assert_eq!(digits(1977), [1, 9, 7, 7]);
361        assert_eq!(digits(12), [1, 2]);
362        assert_eq!(digits(1), [1]);
363        assert_eq!(digits(0), [0]);
364        assert_eq!(digits(10), [1, 0]);
365        assert_eq!(digits(2022), [2, 0, 2, 2]);
366    }
367
368    #[test]
369    fn digits_from_str_test() {
370        assert_eq!(digits_from_str("123"), [1, 2, 3]);
371        assert_eq!(digits_from_str("1977"), [1, 9, 7, 7]);
372        assert_eq!(digits_from_str("12"), [1, 2]);
373        assert_eq!(digits_from_str("1"), [1]);
374        assert_eq!(digits_from_str("0"), [0]);
375        assert_eq!(digits_from_str("10"), [1, 0]);
376        assert_eq!(digits_from_str("2022"), [2, 0, 2, 2]);
377        //
378        assert_eq!(digits_from_str("202abc2"), [2, 0, 2, 2]);
379        assert_eq!(digits_from_str("abc"), []);
380        assert_eq!(digits_from_str("aa:bb:42:ee:ff"), [4, 2]);
381    }
382
383    #[test]
384    fn get_primes_below_test() {
385        assert_eq!(get_primes_below(2), []);
386        assert_eq!(get_primes_below(3), [2]);
387        assert_eq!(get_primes_below(4), [2, 3]);
388        assert_eq!(get_primes_below(10), [2, 3, 5, 7]);
389        assert_eq!(get_primes_below(13), [2, 3, 5, 7, 11]);
390        assert_eq!(get_primes_below(14), [2, 3, 5, 7, 11, 13]);
391        //
392        assert_eq!(get_primes_below(100).len(), 25);
393    }
394
395    #[test]
396    fn get_divisors_test() {
397        assert_eq!(get_divisors(1), [1]);
398        assert_eq!(get_divisors(3), [1, 3]);
399        assert_eq!(get_divisors(6), [1, 2, 3, 6]);
400        assert_eq!(get_divisors(10), [1, 2, 5, 10]);
401        assert_eq!(get_divisors(15), [1, 3, 5, 15]);
402        assert_eq!(get_divisors(21), [1, 3, 7, 21]);
403        assert_eq!(get_divisors(28), [1, 2, 4, 7, 14, 28]);
404    }
405
406    #[test]
407    fn get_proper_divisors_test() {
408        assert_eq!(get_proper_divisors(1), []);
409        assert_eq!(get_proper_divisors(3), [1]);
410        assert_eq!(get_proper_divisors(6), [1, 2, 3]);
411        assert_eq!(get_proper_divisors(10), [1, 2, 5]);
412        assert_eq!(get_proper_divisors(15), [1, 3, 5]);
413        assert_eq!(get_proper_divisors(21), [1, 3, 7]);
414        assert_eq!(get_proper_divisors(28), [1, 2, 4, 7, 14]);
415    }
416
417    #[test]
418    fn get_collatz_sequence_test() {
419        assert_eq!(get_collatz_sequence(1), [1]);
420        assert_eq!(
421            get_collatz_sequence(13),
422            [13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
423        );
424    }
425
426    #[test]
427    fn factorial_test() {
428        assert_eq!(factorial(0), 1);
429        assert_eq!(factorial(1), 1);
430        assert_eq!(factorial(2), 2);
431        assert_eq!(factorial(3), 6);
432        assert_eq!(factorial(4), 24);
433        assert_eq!(factorial(5), 120);
434    }
435
436    #[test]
437    fn factorial_bigint_test() {
438        let numbers = [2, 3, 5, 7, 11, 13];
439        for &n in numbers.iter() {
440            assert_eq!(factorial(n).to_string(), factorial_bigint(n).to_string());
441        }
442    }
443}
jabba_lib/jmath.rs

jabba_lib/
jmath.rs
