The COLLATZ Conjecture

1//
2// Ron Bentley, Stafford UK
3// November 2021
4//
5// This  example and code is in the public domain and may be used without
6// restriction  and without warranty.
7//
8// Collatz Conjecture
9// ^^^^^^^^^^^^^^^^^^
10//
11//  A sketch to produce the Collatz sequence for a given positive integer.
12// The  Collatz sequence for any positive integer, N, is determined as follows:
13//
14//   if N is odd set  N = 3*N + 1 (which will then be even)
15//   if N is even set  N = N/2     (which will be either be an odd or an even number)
16//   repeat the  above until N converges to 1, ie N = 1.
17//
18// For any given positive integer  the Collatz squence will always converge to 1, although
19// this remains unproven.  The Collatz conjecture is also know as the 3N+1 conjecture.
20//
21
22uint32_t  collatz_num;  // the positive integer for which the Collatz sequence will be determined
23
24//
25//  The function implements/executes the Collatz 'rules' to determine the Collatz
26//  sequence for the given positive integer.
27// The function prints each number in  the Collatz sequence to the currently
28// selected output stream - the serial  monitor ot the serial polotter.
29//
30void collatz(uint32_t collatz_num) {
31  uint16_t convergence_steps; // records the number of steps performed before the  Collatz sequence reaches 1
32  convergence_steps = 0;      // count of the number  of steps to convergence
33  Serial.print("\
34Collatz sequence for ");
35  Serial.print(collatz_num);
36  Serial.println("...");
37  // apply the Collatz rules
38  while (collatz_num  > 1) {
39    convergence_steps++;
40    Serial.println(collatz_num);
41    if  (collatz_num & 1 == 1) {// test bottom bit
42      // odd number
43      collatz_num  = collatz_num * 3 + 1;
44    } else
45    {
46      // even number
47      collatz_num  = collatz_num >> 1; // divide by 2
48    }
49  }
50  // done, we have reached  convergence (1)
51  convergence_steps++;
52  Serial.println(collatz_num); // final  value in the Collatz sequence, which will be 1
53  Serial.print("Collatz convergence  steps = ");
54  Serial.println(convergence_steps);
55  Serial.flush();
56}
57
58uint32_t  read_collatz_num() {
59  int32_t collatz_num = 0;
60  while (!Serial.available());  // wait for input
61  while (collatz_num <= 0) {
62    collatz_num = Serial.parseInt();  // read next +ve integer in the current input stream
63  }
64  // input is a positive  integer, now flush out any following chars
65  delay(50); // this shouldnt be necessary  but it is!
66  while (Serial.available() > 0) {
67    // still more chars in the  input stream so read and discard
68    Serial.read();
69  }
70  return collatz_num;  // return the integer read
71}
72
73void setup() {
74  Serial.begin(9600);
75  Serial.println("Collatz Conjecture Examples");
76  Serial.println("^^^^^^^^^^^^^^^^^^^^^^^^^^^");
77  Serial.println("Enter any positive integer and press return/send");
78}
79
80void  loop() {
81  // keep reading user supplied values and determine their Collatz sequences
82  do {
83    collatz_num = read_collatz_num(); // read user input
84    collatz(collatz_num);
85  } while (true);
86}
87