collatz/
lib.rs

1/// Struct representing a sequence of Collatz steps for a given number
2/// The number will not be part of the list. The list will always end with
3/// the values 4, 2, 1 unless you found a mathematic breakthrough ;-)
4struct CollatzSequence<T>
5where
6    T: num::Integer + Copy,
7{
8    next: T,
9}
10
11impl<T> CollatzSequence<T>
12where
13    T: num::Integer + Copy,
14{
15    /// Create a new CollatzSequence for the specified number
16    fn new(number: T) -> CollatzSequence<T> {
17        CollatzSequence { next: number }
18    }
19}
20
21impl<T> Iterator for CollatzSequence<T>
22where
23    T: num::Integer + Copy,
24{
25    type Item = T;
26
27    fn next(&mut self) -> Option<Self::Item> {
28        if self.next <= T::one() {
29            return None;
30        }
31        self.next = if self.next % (T::one() + T::one()) == T::zero() {
32            self.next / (T::one() + T::one())
33        } else {
34            (T::one() + T::one() + T::one()) * self.next + T::one()
35        };
36        Some(self.next)
37    }
38}
39
40/// Return a list of containing the collatz steps for the specified number
41/// The initial number will not be part of the list. The list will always end with
42/// the values 4, 2, 1 unless you found a mathematic breakthrough ;-)
43/// The length of the list will be the same as the number returned by count_steps:
44/// get_steps(N).len() == count_steps(N)
45/// For zero the function will return an empty list
46pub fn get_steps<T>(number: T) -> Vec<T>
47where
48    T: num::Integer + Copy,
49{
50    let c = CollatzSequence::new(number);
51    c.collect()
52}
53
54/// Count the number of collatz steps for the specified number
55/// All the steps required to reach 1 will be counted.
56/// For zero the function will return 0
57pub fn total_stopping_time<T>(number: T) -> usize
58where
59    T: num::Integer + Copy,
60{
61    let c = CollatzSequence::new(number);
62    c.count()
63}
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_count_steps() {
71        let numbers = [
72            0,
73            1,
74            2,
75            4,
76            9,
77            97,
78            871,
79            6171,
80            77_031,
81            837_799,
82            8_400_511,
83            931_386_509_544_713_451,
84        ];
85        let steps = [0, 0, 1, 2, 19, 118, 178, 261, 350, 524, 685, 2283];
86        for (i, n) in numbers.iter().enumerate() {
87            assert_eq!(steps[i], total_stopping_time::<u128>(*n));
88            assert_eq!(steps[i], get_steps(*n).len());
89        }
90    }
91
92    #[test]
93    fn test_get_steps() {
94        let steps = vec![
95            58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1,
96        ];
97        assert_eq!(steps, get_steps(19));
98
99        let steps = vec![
100            82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91,
101            274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186,
102            593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425,
103            1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644,
104            1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866,
105            433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80,
106            40, 20, 10, 5, 16, 8, 4, 2, 1,
107        ];
108        assert_eq!(steps, get_steps(27));
109    }
110}
collatz/lib.rs

collatz/
lib.rs
