oxilean_std/nat/
types.rs

1//! Auto-generated module
2//!
3//! 🤖 Generated with [SplitRS](https://github.com/cool-japan/splitrs)
4use super::functions::*;
5
6/// Fibonacci number utilities.
7#[allow(dead_code)]
8#[derive(Debug, Clone)]
9pub struct FibonacciUtil;
10#[allow(dead_code)]
11impl FibonacciUtil {
12    /// Compute the nth Fibonacci number iteratively.
13    pub fn fib(n: u64) -> u64 {
14        if n == 0 {
15            return 0;
16        }
17        if n == 1 {
18            return 1;
19        }
20        let mut a = 0u64;
21        let mut b = 1u64;
22        for _ in 2..=n {
23            let c = a.saturating_add(b);
24            a = b;
25            b = c;
26        }
27        b
28    }
29    /// Check if a number is a Fibonacci number.
30    pub fn is_fibonacci(n: u64) -> bool {
31        let check = |k: u64| -> bool {
32            let sqrt = (k as f64).sqrt() as u64;
33            sqrt * sqrt == k || (sqrt + 1) * (sqrt + 1) == k
34        };
35        let n5 = 5u64.saturating_mul(n.saturating_mul(n));
36        check(n5.saturating_add(4)) || (n5 >= 4 && check(n5 - 4))
37    }
38    /// Zeckendorf representation: every positive integer is uniquely
39    /// a sum of non-consecutive Fibonacci numbers.
40    pub fn zeckendorf(mut n: u64) -> Vec<u64> {
41        if n == 0 {
42            return vec![0];
43        }
44        let mut all_fibs = vec![1u64, 1];
45        while *all_fibs
46            .last()
47            .expect("all_fibs is non-empty: initialized with [1, 1]")
48            < n
49        {
50            let len = all_fibs.len();
51            all_fibs.push(all_fibs[len - 1].saturating_add(all_fibs[len - 2]));
52        }
53        all_fibs.retain(|&x| x <= n);
54        all_fibs.dedup();
55        let mut result = Vec::new();
56        for &fib in all_fibs.iter().rev() {
57            if fib <= n {
58                result.push(fib);
59                n -= fib;
60            }
61        }
62        result
63    }
64}
65/// Arithmetic function utilities.
66#[allow(dead_code)]
67#[derive(Debug, Clone)]
68pub struct ArithmeticFunctions;
69#[allow(dead_code)]
70impl ArithmeticFunctions {
71    /// Euler's totient function phi(n).
72    pub fn euler_totient(n: u64) -> u64 {
73        if n == 0 {
74            return 0;
75        }
76        let mut result = n;
77        let mut temp = n;
78        let mut p = 2u64;
79        while p * p <= temp {
80            if temp % p == 0 {
81                while temp % p == 0 {
82                    temp /= p;
83                }
84                result -= result / p;
85            }
86            p += 1;
87        }
88        if temp > 1 {
89            result -= result / temp;
90        }
91        result
92    }
93    /// Möbius function mu(n).
94    pub fn mobius(mut n: u64) -> i32 {
95        if n == 1 {
96            return 1;
97        }
98        let mut num_prime_factors = 0i32;
99        let mut p = 2u64;
100        while p * p <= n {
101            if n % p == 0 {
102                num_prime_factors += 1;
103                n /= p;
104                if n % p == 0 {
105                    return 0;
106                }
107            }
108            p += 1;
109        }
110        if n > 1 {
111            num_prime_factors += 1;
112        }
113        if num_prime_factors % 2 == 0 {
114            1
115        } else {
116            -1
117        }
118    }
119    /// Number of divisors d(n).
120    pub fn num_divisors(n: u64) -> u64 {
121        if n == 0 {
122            return 0;
123        }
124        (1..=n).filter(|&d| n % d == 0).count() as u64
125    }
126    /// Sum of divisors sigma(n).
127    pub fn sum_of_divisors(n: u64) -> u64 {
128        if n == 0 {
129            return 0;
130        }
131        (1..=n).filter(|&d| n % d == 0).sum()
132    }
133}
134/// Collatz conjecture utilities.
135#[allow(dead_code)]
136#[derive(Debug, Clone)]
137pub struct CollatzUtil;
138#[allow(dead_code)]
139impl CollatzUtil {
140    /// Collatz sequence starting from n.
141    pub fn sequence(mut n: u64) -> Vec<u64> {
142        let mut seq = vec![n];
143        while n != 1 {
144            n = if n % 2 == 0 { n / 2 } else { 3 * n + 1 };
145            seq.push(n);
146            if seq.len() > 10_000 {
147                break;
148            }
149        }
150        seq
151    }
152    /// Stopping time: number of steps to reach 1.
153    pub fn stopping_time(n: u64) -> Option<usize> {
154        let seq = Self::sequence(n);
155        if *seq
156            .last()
157            .expect("seq is non-empty: sequence(n) always includes n")
158            == 1
159        {
160            Some(seq.len() - 1)
161        } else {
162            None
163        }
164    }
165}
oxilean_std/nat/types.rs

oxilean_std/nat/
types.rs
