use_collatz/
lib.rs

1#![forbid(unsafe_code)]
2#![doc = include_str!("../README.md")]
3
4//! Collatz trajectory utilities for `RustUse`.
5
6#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
7/// The parity of a positive integer in a Collatz trajectory.
8pub enum CollatzParity {
9    /// The value is divisible by `2`.
10    Even,
11    /// The value is not divisible by `2`.
12    Odd,
13}
14
15#[derive(Clone, Debug, Eq, PartialEq)]
16/// Summary information for an inclusive range checked with [`verify_range`].
17///
18/// `max_total_stopping_time` stores `(input, total_stopping_time)`.
19///
20/// `max_trajectory_value` stores `(input, max_value_in_trajectory)`.
21pub struct CollatzRangeSummary {
22    /// The inclusive lower bound that was requested.
23    pub start: u64,
24    /// The inclusive upper bound that was requested.
25    pub end: u64,
26    /// The number of positive inputs checked in the inclusive range.
27    pub checked: u64,
28    /// The number of checked inputs whose trajectories reached `1` without overflow.
29    pub reached_one: u64,
30    /// The number of checked inputs whose odd-step arithmetic overflowed.
31    pub overflowed: u64,
32    /// The input with the largest total stopping time, if any values were checked.
33    pub max_total_stopping_time: Option<(u64, u64)>,
34    /// The input with the largest peak trajectory value, if any values were checked.
35    pub max_trajectory_value: Option<(u64, u64)>,
36}
37
38#[derive(Clone, Copy, Debug, Eq, PartialEq)]
39struct TrajectoryMetrics {
40    stopping_time: u64,
41    total_stopping_time: u64,
42    max_value: u64,
43}
44
45const fn is_even(n: u64) -> bool {
46    (n & 1) == 0
47}
48
49const fn checked_odd_step(n: u64) -> Option<u64> {
50    match n.checked_mul(3) {
51        Some(value) => value.checked_add(1),
52        None => None,
53    }
54}
55
56fn trajectory_metrics(n: u64) -> Option<TrajectoryMetrics> {
57    if n == 0 {
58        return None;
59    }
60
61    let start = n;
62    let mut current = n;
63    let mut stopping_time = if n == 1 { Some(0) } else { None };
64    let mut total_stopping_time = 0_u64;
65    let mut max_value = n;
66
67    while current != 1 {
68        current = collatz_next(current)?;
69        total_stopping_time = total_stopping_time.checked_add(1)?;
70        max_value = max_value.max(current);
71
72        if stopping_time.is_none() && current < start {
73            stopping_time = Some(total_stopping_time);
74        }
75    }
76
77    Some(TrajectoryMetrics {
78        stopping_time: stopping_time.unwrap_or(total_stopping_time),
79        total_stopping_time,
80        max_value,
81    })
82}
83
84fn update_max_pair(slot: &mut Option<(u64, u64)>, input: u64, value: u64) {
85    if slot.is_none_or(|(_, current_max)| value > current_max) {
86        *slot = Some((input, value));
87    }
88}
89
90/// Returns the next value in the Collatz trajectory for a positive integer.
91///
92/// Returns `None` when `n == 0` or when the checked odd step `3 * n + 1`
93/// overflows `u64`.
94///
95/// # Examples
96///
97/// ```rust
98/// use use_collatz::collatz_next;
99///
100/// assert_eq!(collatz_next(1), Some(4));
101/// assert_eq!(collatz_next(2), Some(1));
102/// assert_eq!(collatz_next(3), Some(10));
103/// assert_eq!(collatz_next(0), None);
104/// ```
105#[must_use]
106pub const fn collatz_next(n: u64) -> Option<u64> {
107    if n == 0 {
108        return None;
109    }
110
111    if is_even(n) {
112        Some(n / 2)
113    } else {
114        checked_odd_step(n)
115    }
116}
117
118/// Returns the full Collatz trajectory from `n` down to `1`.
119///
120/// Returns `None` when `n == 0` or when a checked odd step overflows.
121///
122/// # Examples
123///
124/// ```rust
125/// use use_collatz::collatz_sequence;
126///
127/// assert_eq!(collatz_sequence(6), Some(vec![6, 3, 10, 5, 16, 8, 4, 2, 1]));
128/// assert_eq!(collatz_sequence(0), None);
129/// ```
130#[must_use]
131pub fn collatz_sequence(n: u64) -> Option<Vec<u64>> {
132    if n == 0 {
133        return None;
134    }
135
136    let mut current = n;
137    let mut sequence = vec![current];
138
139    while current != 1 {
140        current = collatz_next(current)?;
141        sequence.push(current);
142    }
143
144    Some(sequence)
145}
146
147/// Returns the number of steps needed to first reach a value smaller than `n`.
148///
149/// Returns `Some(0)` for `n == 1`.
150///
151/// Returns `None` when `n == 0` or when a checked odd step overflows.
152///
153/// # Examples
154///
155/// ```rust
156/// use use_collatz::stopping_time;
157///
158/// assert_eq!(stopping_time(1), Some(0));
159/// assert_eq!(stopping_time(6), Some(1));
160/// assert_eq!(stopping_time(3), Some(6));
161/// ```
162#[must_use]
163pub fn stopping_time(n: u64) -> Option<u64> {
164    trajectory_metrics(n).map(|metrics| metrics.stopping_time)
165}
166
167/// Returns the number of steps needed to reach `1`.
168///
169/// Returns `None` when `n == 0` or when a checked odd step overflows.
170///
171/// # Examples
172///
173/// ```rust
174/// use use_collatz::total_stopping_time;
175///
176/// assert_eq!(total_stopping_time(1), Some(0));
177/// assert_eq!(total_stopping_time(6), Some(8));
178/// ```
179#[must_use]
180pub fn total_stopping_time(n: u64) -> Option<u64> {
181    trajectory_metrics(n).map(|metrics| metrics.total_stopping_time)
182}
183
184/// Returns the full trajectory length including the starting value and terminal `1`.
185///
186/// Returns `None` when `n == 0` or when a checked odd step overflows.
187///
188/// # Examples
189///
190/// ```rust
191/// use use_collatz::trajectory_len;
192///
193/// assert_eq!(trajectory_len(1), Some(1));
194/// assert_eq!(trajectory_len(6), Some(9));
195/// ```
196#[must_use]
197pub fn trajectory_len(n: u64) -> Option<u64> {
198    total_stopping_time(n)?.checked_add(1)
199}
200
201/// Returns the largest value reached in the trajectory from `n` to `1`.
202///
203/// Returns `None` when `n == 0` or when a checked odd step overflows.
204///
205/// # Examples
206///
207/// ```rust
208/// use use_collatz::max_value_in_trajectory;
209///
210/// assert_eq!(max_value_in_trajectory(1), Some(1));
211/// assert_eq!(max_value_in_trajectory(6), Some(16));
212/// ```
213#[must_use]
214pub fn max_value_in_trajectory(n: u64) -> Option<u64> {
215    trajectory_metrics(n).map(|metrics| metrics.max_value)
216}
217
218/// Returns `true` when the trajectory reaches `1` without overflow.
219///
220/// Returns `false` for `n == 0` or when a checked odd step overflows.
221///
222/// # Examples
223///
224/// ```rust
225/// use use_collatz::reaches_one;
226///
227/// assert!(reaches_one(6));
228/// assert!(!reaches_one(0));
229/// ```
230#[must_use]
231pub fn reaches_one(n: u64) -> bool {
232    trajectory_metrics(n).is_some()
233}
234
235/// Returns the parity of a positive input.
236///
237/// Returns `None` when `n == 0`.
238///
239/// # Examples
240///
241/// ```rust
242/// use use_collatz::{CollatzParity, parity};
243///
244/// assert_eq!(parity(8), Some(CollatzParity::Even));
245/// assert_eq!(parity(9), Some(CollatzParity::Odd));
246/// assert_eq!(parity(0), None);
247/// ```
248#[must_use]
249pub const fn parity(n: u64) -> Option<CollatzParity> {
250    if n == 0 {
251        return None;
252    }
253
254    if is_even(n) {
255        Some(CollatzParity::Even)
256    } else {
257        Some(CollatzParity::Odd)
258    }
259}
260
261/// Returns the parity pattern for the trajectory from `n` to `1`.
262///
263/// The returned vector includes the starting value and every nonterminal value
264/// in the trajectory, but it excludes the final `1`. For `n == 1`, this means
265/// the parity vector is empty.
266///
267/// Returns `None` when `n == 0` or when a checked odd step overflows.
268///
269/// # Examples
270///
271/// ```rust
272/// use use_collatz::{CollatzParity, parity_vector};
273///
274/// assert_eq!(
275///     parity_vector(6),
276///     Some(vec![
277///         CollatzParity::Even,
278///         CollatzParity::Odd,
279///         CollatzParity::Even,
280///         CollatzParity::Odd,
281///         CollatzParity::Even,
282///         CollatzParity::Even,
283///         CollatzParity::Even,
284///         CollatzParity::Even,
285///     ])
286/// );
287/// assert_eq!(parity_vector(1), Some(vec![]));
288/// ```
289#[must_use]
290pub fn parity_vector(n: u64) -> Option<Vec<CollatzParity>> {
291    if n == 0 {
292        return None;
293    }
294
295    let mut current = n;
296    let mut parities = Vec::new();
297
298    while current != 1 {
299        parities.push(parity(current)?);
300        current = collatz_next(current)?;
301    }
302
303    Some(parities)
304}
305
306/// Verifies the inclusive range `[start, end]` with bounded Collatz exploration.
307///
308/// The function skips `0`, counts the number of positive inputs checked, counts
309/// how many trajectories reach `1`, counts how many overflow during checked odd
310/// steps, tracks the input with the largest total stopping time, and tracks the
311/// input with the largest peak trajectory value.
312///
313/// When `start > end`, the returned summary is empty and no values are checked.
314///
315/// # Examples
316///
317/// ```rust
318/// use use_collatz::verify_range;
319///
320/// let summary = verify_range(1, 10);
321///
322/// assert_eq!(summary.checked, 10);
323/// assert_eq!(summary.reached_one, 10);
324/// assert_eq!(summary.overflowed, 0);
325/// assert_eq!(summary.max_total_stopping_time, Some((9, 19)));
326/// assert_eq!(summary.max_trajectory_value, Some((7, 52)));
327/// ```
328#[must_use]
329pub fn verify_range(start: u64, end: u64) -> CollatzRangeSummary {
330    let mut summary = CollatzRangeSummary {
331        start,
332        end,
333        checked: 0,
334        reached_one: 0,
335        overflowed: 0,
336        max_total_stopping_time: None,
337        max_trajectory_value: None,
338    };
339
340    if start > end {
341        return summary;
342    }
343
344    for input in start..=end {
345        if input == 0 {
346            continue;
347        }
348
349        summary.checked += 1;
350
351        if let Some(metrics) = trajectory_metrics(input) {
352            summary.reached_one += 1;
353            update_max_pair(
354                &mut summary.max_total_stopping_time,
355                input,
356                metrics.total_stopping_time,
357            );
358            update_max_pair(&mut summary.max_trajectory_value, input, metrics.max_value);
359        } else {
360            summary.overflowed += 1;
361        }
362    }
363
364    summary
365}
366
367#[cfg(test)]
368mod tests {
369    use super::{
370        CollatzParity, CollatzRangeSummary, collatz_next, collatz_sequence,
371        max_value_in_trajectory, parity, parity_vector, reaches_one, stopping_time,
372        total_stopping_time, trajectory_len, verify_range,
373    };
374
375    #[test]
376    fn computes_next_values() {
377        assert_eq!(collatz_next(1), Some(4));
378        assert_eq!(collatz_next(2), Some(1));
379        assert_eq!(collatz_next(3), Some(10));
380        assert_eq!(collatz_next(0), None);
381    }
382
383    #[test]
384    fn detects_checked_overflow_for_odd_steps() {
385        assert_eq!(collatz_next(u64::MAX), None);
386    }
387
388    #[test]
389    fn builds_full_sequences() {
390        assert_eq!(collatz_sequence(6), Some(vec![6, 3, 10, 5, 16, 8, 4, 2, 1]));
391        assert_eq!(collatz_sequence(0), None);
392    }
393
394    #[test]
395    fn computes_total_stopping_times() {
396        assert_eq!(total_stopping_time(1), Some(0));
397        assert_eq!(total_stopping_time(6), Some(8));
398    }
399
400    #[test]
401    fn computes_trajectory_lengths() {
402        assert_eq!(trajectory_len(1), Some(1));
403        assert_eq!(trajectory_len(6), Some(9));
404    }
405
406    #[test]
407    fn computes_trajectory_maxima() {
408        assert_eq!(max_value_in_trajectory(6), Some(16));
409        assert_eq!(max_value_in_trajectory(1), Some(1));
410    }
411
412    #[test]
413    fn computes_stopping_times() {
414        assert_eq!(stopping_time(1), Some(0));
415        assert_eq!(stopping_time(6), Some(1));
416        assert_eq!(stopping_time(3), Some(6));
417    }
418
419    #[test]
420    fn reports_reachability_without_panicking() {
421        assert!(reaches_one(6));
422        assert!(!reaches_one(0));
423    }
424
425    #[test]
426    fn classifies_parity_helpers() {
427        assert_eq!(parity(8), Some(CollatzParity::Even));
428        assert_eq!(parity(9), Some(CollatzParity::Odd));
429        assert_eq!(parity(0), None);
430    }
431
432    #[test]
433    fn builds_parity_vectors_without_terminal_one() {
434        assert_eq!(
435            parity_vector(6),
436            Some(vec![
437                CollatzParity::Even,
438                CollatzParity::Odd,
439                CollatzParity::Even,
440                CollatzParity::Odd,
441                CollatzParity::Even,
442                CollatzParity::Even,
443                CollatzParity::Even,
444                CollatzParity::Even,
445            ])
446        );
447        assert_eq!(parity_vector(1), Some(vec![]));
448        assert_eq!(parity_vector(0), None);
449    }
450
451    #[test]
452    fn verifies_bounded_ranges() {
453        assert_eq!(
454            verify_range(1, 10),
455            CollatzRangeSummary {
456                start: 1,
457                end: 10,
458                checked: 10,
459                reached_one: 10,
460                overflowed: 0,
461                max_total_stopping_time: Some((9, 19)),
462                max_trajectory_value: Some((7, 52)),
463            }
464        );
465    }
466
467    #[test]
468    fn skips_zero_and_allows_empty_ranges() {
469        assert_eq!(
470            verify_range(0, 0),
471            CollatzRangeSummary {
472                start: 0,
473                end: 0,
474                checked: 0,
475                reached_one: 0,
476                overflowed: 0,
477                max_total_stopping_time: None,
478                max_trajectory_value: None,
479            }
480        );
481
482        assert_eq!(
483            verify_range(10, 1),
484            CollatzRangeSummary {
485                start: 10,
486                end: 1,
487                checked: 0,
488                reached_one: 0,
489                overflowed: 0,
490                max_total_stopping_time: None,
491                max_trajectory_value: None,
492            }
493        );
494    }
495}
use_collatz/lib.rs

use_collatz/
lib.rs
