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
pub fn get_steps(number: u128) -> Vec<u128> {
let mut next = number;
let mut steps = vec![];
loop {
if next <= 1 {
break;
}
next = if next % 2 == 0 {
next / 2
} else {
3 * next + 1
};
steps.push(next);
}
steps
}
pub fn count_steps(number: u128) -> u128 {
let mut next = number;
let mut steps = 0;
loop {
if next <= 1 {
break;
}
next = if next % 2 == 0 {
steps += 1;
next / 2
} else {
steps += 2;
(3 * next + 1) / 2
};
}
steps
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_count_steps() {
let numbers = [
0,
1,
2,
4,
9,
97,
871,
6171,
77_031,
837_799,
8_400_511,
931_386_509_544_713_451,
];
let steps = [0, 0, 1, 2, 19, 118, 178, 261, 350, 524, 685, 2283];
for (i, n) in numbers.iter().enumerate() {
assert_eq!(steps[i], count_steps(*n));
assert_eq!(steps[i], get_steps(*n).len() as u128);
}
}
#[test]
fn test_get_steps() {
let steps = vec![
58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1,
];
assert_eq!(steps, get_steps(19));
let steps = vec![
82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91,
274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186,
593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425,
1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644,
1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866,
433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80,
40, 20, 10, 5, 16, 8, 4, 2, 1,
];
assert_eq!(steps, get_steps(27));
}
}