Simple tool to brute force 3x+1 for a new loop.
1use std::ops::Mul;
2use std::process::exit;
3use tracing::{Level, instrument, event};
4use tracing_subscriber;
5use clap::Parser;
6
7/// Simple tool to brute force 3x+1 for a second loop. Only takes positive numbers
8#[derive(Parser, Debug)]
9#[clap(author, version, about, long_about = None)]
10struct Args {
11 /// Weather to output current number each time
12 #[clap(short, long)]
13 verbose: bool,
14
15 /// Weather to output current number every step of 3x+1
16 #[clap(short, long)]
17 double_verbose: bool,
18
19 /// Number of times to try
20 #[clap(short, long, default_value_t = 50000)]
21 count: u128,
22
23 /// Number to start at
24 #[clap(short, long, default_value_t = 195147905179352825856)]
25 start: u128,
26}
27
28#[instrument]
29fn main() {
30 tracing_subscriber::fmt::init();
31 let args = Args::parse();
32
33 let max_num = args.start + args.count;
34
35 event!(Level::INFO, "Starting 3x+1 process");
36 event!(Level::INFO, "Starting number: {}", args.start);
37 event!(Level::INFO, "Amount of numbers to try: {}", args.count);
38
39 if args.verbose & !args.double_verbose{
40 for current_num in args.start..max_num{
41 event!(Level::INFO, "Processing {}", current_num);
42 let (smallest_num, largest_num) = txpo(current_num);
43 event!(Level::INFO, "Loop found! Smallest number: {}, largest number: {}", smallest_num, largest_num);
44 }
45 } else if args.double_verbose {
46 for current_num in args.start..max_num{
47 event!(Level::INFO, "Processing {}", current_num);
48 let (smallest_num, largest_num) = verbose_txpo(current_num);
49 event!(Level::INFO, "Loop found! Smallest number: {}, largest number: {}", smallest_num, largest_num);
50 }
51 } else {
52 for current_num in args.start..max_num{
53 let (_smallest_num, _largest_num) = txpo(current_num);
54 }
55 }
56
57 event!(Level::INFO, "Finished trying {} numbers", args.count);
58}
59
60#[instrument]
61fn txpo(mut current_num: u128) -> (u128, u128) {
62 let mut largest_num = current_num;
63 let mut smallest_num = current_num;
64 let mut smallest_num_count = 1;
65 while smallest_num_count != 2{
66
67 // if odd
68 if current_num % 2 != 0 {
69 if current_num < smallest_num{
70 smallest_num = current_num;
71 }
72
73 if current_num > largest_num{
74 largest_num = current_num;
75 }
76
77 // For some reason using .mul() is faster then * but .add() is slightly slower then +.
78 // it was only a few ms slower to do all 50K but on an extremely large scale it matters.
79 current_num = current_num.mul(3) + 1;
80
81 } else {
82 if current_num < smallest_num{
83 smallest_num = current_num;
84 }
85
86 if current_num > largest_num{
87 largest_num = current_num;
88 }
89
90 // Writing this one line taught me about bit shifting.
91 // doing >> on an unsigned integer (u8-u16-u32-u64-u128) does something called
92 // Logical Right Shifting. This removes the least significant bit or the right most
93 // bit and places a 0 on the left. so the binary form of 8 is 1000, doing 8>>1 shifts
94 // the bits to the right once, this takes the last 0 and removes it making it 100, we
95 // then add a new 0 to the left making it 0100 which is binary for 4.
96 // This is more efficient then just trying to do division because there is no actual
97 // math involved and just a super quick bit operation.
98 //
99 // Another example:
100 // 69420 >> 1 == 34710
101 // 0001 0000 1111 0010 1100 >> 1
102 // 0001 0000 1111 0010 110
103 // 0000 1000 0111 1001 0110 == 34710
104 //
105 current_num = current_num >> 1;
106 }
107
108 if current_num == smallest_num {
109 smallest_num_count = smallest_num_count + 1;
110 }
111 }
112
113 if smallest_num != 1{
114 event!(Level::ERROR, "Found new loop!");
115 exit(1)
116 }
117
118 return(smallest_num, largest_num);
119}
120
121#[instrument]
122fn verbose_txpo(mut current_num: u128) -> (u128, u128) {
123 let mut largest_num = current_num;
124 let mut smallest_num = current_num;
125 let mut smallest_num_count = 1;
126 while smallest_num_count != 2{
127
128 if current_num % 2 != 0 {
129 if current_num < smallest_num{
130 smallest_num = current_num;
131 }
132
133 if current_num > largest_num{
134 largest_num = current_num;
135 }
136
137 event!(Level::INFO, "{} is odd. Smallest number: {}. Largest number: {}", current_num, smallest_num, largest_num);
138
139 current_num = current_num.mul(3) + 1;
140 } else {
141 if current_num < smallest_num{
142 smallest_num = current_num;
143 }
144
145 if current_num > largest_num{
146 largest_num = current_num;
147 }
148
149 event!(Level::INFO, "{} is even. Smallest number: {}. Largest number: {}", current_num, smallest_num, largest_num);
150
151 current_num = current_num >> 1;
152 }
153
154 if current_num == smallest_num {
155 smallest_num_count = smallest_num_count + 1;
156 }
157 }
158
159 if smallest_num != 1{
160 event!(Level::ERROR, "Found new loop!");
161 exit(1)
162 }
163
164 return(smallest_num, largest_num);
165}