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

//! A collection of functions relating to the Collatz conjecture

#![deny(missing_docs, unused_imports)]

use std::fmt::{Debug, Display};

use no_panic::no_panic;
// use no_panic::no_panic;
use num::{FromPrimitive, Integer, PrimInt, Unsigned};

/// Types implementing this can be passed to the most if not all functions in this library
pub trait Collatz: Unsigned + Integer + PrimInt + FromPrimitive + Debug + Display {}

impl<T> Collatz for T where T: Unsigned + Integer + PrimInt + FromPrimitive + Debug + Display {}

#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]
/// Represents a single non-zero unsigned integer,
/// which can be used with the functions in this crate
pub struct NonZero<T: Collatz>(T);

impl<T: Collatz> NonZero<T> {
    /// Tries making a NonZero<T> from a T.
    /// Only returns None if N equals zero.
    pub fn try_new(n: T) -> Option<Self> {
        if n.is_zero() {
            None
        } else {
            Some(Self(n))
        }
    }
}

/// This has the effect of dividing a number by 2 until it is odd.
/// Odd numbers are simply returned.
pub fn divide_while_even<T: Collatz>(n: NonZero<T>) -> Option<NonZero<T>> {
    let n = n.0;
    let trailing_zeros: usize = n.trailing_zeros().try_into().ok()?;
    Some(NonZero(n >> trailing_zeros))
}

/// Returns all the numbers N becomes on its way to falling to one.
#[no_panic]
pub fn transformations<T: Collatz>(n: NonZero<T>) -> Option<Vec<T>> {
    let mut n = n;
    let mut trans: Vec<T> = vec![n.0];
    while !n.0.is_one() {
        n = rules::basic(n)?;
        trans.push(n.0);
    }
    Some(trans)
}

pub mod bouncy_numbers;
pub mod check_range;
pub mod fall;
pub mod rules;
pub mod steps;
pub mod steps_range;

mod tests {
    // Make sure the steps returned by steps::omega
    #[test]
    fn steps_range_conforms_to_oeis() {
        use crate::NonZero;

        // Number of steps to reach 1 for integers 1..=72
        let oeis_steps: Vec<u32> = vec![
            0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23,
            10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16,
            104, 11, 24, 24, 24, 11, 11, 112, 112, 19, 32, 19, 32, 19, 19, 107, 107, 6, 27, 27, 27,
            14, 14, 14, 102, 22,
        ];

        let r = 1..(oeis_steps.len() + 1);

        let step_counts: Vec<u32> = r
            .map(|n| crate::steps::omega(NonZero(n)).unwrap())
            .collect();

        for i in 0..oeis_steps.len() {
            println!(
                "{} => OEIS: {}, LIB: {}",
                i + 1,
                oeis_steps[i],
                step_counts[i]
            );
            assert_eq!(oeis_steps[i], step_counts[i]);
        }
    }
}