nyar-collatz 0.1.0

Collatz lib for Nyar
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

use crate::CollatzType;

pub type Collatz64 = CollatzType<u64>;

impl From<u64> for Collatz64 {
    fn from(n: u64) -> Collatz64 {
        if n == 0 {panic!("Input must be a positive integer!")}
        Collatz64 { start: n }
    }
}

impl Iterator for Collatz64 {
    type Item = u64;
    fn next(&mut self) -> Option<Self::Item> {
        if self.start % 2 == 0 {
            self.start = self.start / 2;
            return Some(self.start);
        }
        if self.start == 1 {
            return None;
        }
        self.start = self.start * 3 + 1;
        Some(self.start)
    }
}

pub fn count_collatz(n: u32, lengths: &mut [u16; 500_000]) -> u16 {
    if n < 500_000 && lengths[n as usize] > 0 {
        lengths[n as usize]
    } else {
        if n == 1 {
            return 1;
        } else {
            let val = 1 +
                match n % 2 {
                    0 => count_collatz(n / 2, lengths),
                    _ => count_collatz(n * 3 + 1, lengths),
                };
            if n < 500_000 {
                lengths[n as usize] = val;
            }
            val
        }
    }
}

pub fn longest_collatz_memo(highest: u32) -> u32 {
    let mut max_length = 0;
    let mut lengths: [u16; 500_000] = [0; 500_000];
    let mut cause = 0;
    for i in 1..highest + 1 {
        let length = count_collatz(i, &mut lengths);
        if length > max_length {
            cause = i;
            max_length = length;
        }
    }
    cause
}

pub fn longest_collatz(highest: usize) -> usize {
    let mut max_length = 0;
    let mut cause = 0;
    for i in 1..highest + 1 {
        let mut length = 1;
        let mut n = i;
        loop {
            if n == 1 {
                break;
            }
            n = match n % 2 {
                0 => n / 2,
                _ => n * 3 + 1,
            };
            length += 1;
        }
        if length > max_length {
            max_length = length;
            cause = i;
        }
    }
    cause
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    #[should_panic]
    fn collatz_0() {
        let mut collatz = Collatz64::from(0u64);
        assert_eq!(collatz.next(), None);
    }

    #[test]
    fn collatz_13() {
        let mut collatz = Collatz64::from(13u64);
        assert_eq!(collatz.next(), Some(40));
        assert_eq!(collatz.next(), Some(20));
        assert_eq!(collatz.next(), Some(10));
        assert_eq!(collatz.next(), Some(5));
        assert_eq!(collatz.next(), Some(16));
        assert_eq!(collatz.next(), Some(8));
        assert_eq!(collatz.next(), Some(4));
        assert_eq!(collatz.next(), Some(2));
        assert_eq!(collatz.next(), Some(1));
        assert_eq!(collatz.next(), None);
    }

    #[test]
    fn test_longest_collatz() {
        assert_eq!(longest_collatz(1), 1);
        assert_eq!(longest_collatz(2), 2);
        assert_eq!(longest_collatz(3), 3)
    }

    #[test]
    fn test_longest_collatz_memo() {
        assert_eq!(longest_collatz_memo(1), 1);
    }
}