classics.rs

1/// Returns the even numbers up to the limit.2pub fn evens(limit: usize) -> Vec<usize> {3    (0..=limit).step_by(2).collect()4}56/// Returns the odd numbers up to the limit.7pub fn odds(limit: usize) -> Vec<usize> {8    (1..=limit).step_by(2).collect()9}1011/// Returns the powers of two up to the limit.12pub fn binary(limit: usize) -> Vec<usize> {13    let mut out = Vec::new();14    let mut value = 1;15    while value <= limit {16        out.push(value);17        value *= 2;18    }19    out20}2122/// Returns the distinct Fibonacci numbers up to the limit.23pub fn fibonacci(limit: usize) -> Vec<usize> {24    let mut out = Vec::new();25    let (mut a, mut b) = (0usize, 1usize);26    while a <= limit {27        if !out.contains(&a) {28            out.push(a);29        }30        let next = a + b;31        a = b;32        b = next;33    }34    out35}3637/// Returns the distinct Catalan numbers up to the limit.38///39/// ```40/// assert_eq!(mrlynum::classics::catalan(50), vec![1, 2, 5, 14, 42]);41/// ```42pub fn catalan(limit: usize) -> Vec<usize> {43    let mut out = Vec::new();44    let mut value: u128 = 1;45    let mut index: u128 = 0;46    while value <= limit as u128 {47        if out.last() != Some(&(value as usize)) {48            out.push(value as usize);49        }50        value = value * 2 * (2 * index + 1) / (index + 2);51        index += 1;52    }53    out54}5556/// Returns the primes up to the limit by sieve.57///58/// ```59/// assert_eq!(mrlynum::classics::primes(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);60/// ```61pub fn primes(limit: usize) -> Vec<usize> {62    if limit < 2 {63        return Vec::new();64    }65    let mut sieve = vec![true; limit + 1];66    sieve[0] = false;67    sieve[1] = false;68    let mut p = 2;69    while p * p <= limit {70        if sieve[p] {71            let mut m = p * p;72            while m <= limit {73                sieve[m] = false;74                m += p;75            }76        }77        p += 1;78    }79    (2..=limit).filter(|&n| sieve[n]).collect()80}8182/// Returns the factorial of the number, the product of one through it, exact up to thirty-four.83pub fn factorial(number: usize) -> u128 {84    (1..=number as u128).product()85}8687/// Returns the greatest common divisor of two numbers by the Euclidean algorithm.88///89/// ```90/// assert_eq!(mrlynum::classics::gcd(12, 18), 6);91/// assert_eq!(mrlynum::classics::gcd(7, 0), 7);92/// ```93pub fn gcd(a: u128, b: u128) -> u128 {94    let (mut a, mut b) = (a, b);95    while b != 0 {96        (a, b) = (b, a % b);97    }98    a99}100101/// Reduces a fraction to its lowest terms, a zero numerator and denominator reading as zero over one.102///103/// ```104/// assert_eq!(mrlynum::classics::reduce(64, 128), (1, 2));105/// ```106pub fn reduce(numerator: u128, denominator: u128) -> (u128, u128) {107    match gcd(numerator, denominator) {108        0 => (0, 1),109        divisor => (numerator / divisor, denominator / divisor),110    }111}112113#[cfg(test)]114mod tests {115    use super::*;116    #[test]117    fn evens_and_odds() {118        assert_eq!(evens(8), vec![0, 2, 4, 6, 8]);119        assert_eq!(odds(8), vec![1, 3, 5, 7]);120    }121    #[test]122    fn binary_powers() {123        assert_eq!(binary(20), vec![1, 2, 4, 8, 16]);124        assert_eq!(binary(0), Vec::<usize>::new());125    }126    #[test]127    fn fibonacci_dedups_zero_one() {128        assert_eq!(fibonacci(13), vec![0, 1, 2, 3, 5, 8, 13]);129    }130    #[test]131    fn primes_to_twenty() {132        assert_eq!(primes(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);133        assert_eq!(primes(1), Vec::<usize>::new());134    }135    #[test]136    fn catalan_dedups_the_double_one() {137        assert_eq!(catalan(1500), vec![1, 2, 5, 14, 42, 132, 429, 1430]);138        assert_eq!(catalan(0), Vec::<usize>::new());139    }140    #[test]141    fn catalan_matches_the_binomial_form() {142        let list = catalan(40_000_000);143        for (n, &value) in list.iter().enumerate().skip(1) {144            let m = n + 1;145            let mut binom: u128 = 1;146            for i in 0..m {147                binom = binom * (2 * m - i) as u128 / (i + 1) as u128;148            }149            assert_eq!(value as u128, binom / (m as u128 + 1), "{m}");150        }151    }152}