Category: Linux

Hits: 6

The programming assignment about the Collatz Conjecture I give to my students is getting old. The Collatz Conjecture is a prediction about an algorithm. To state it,

• • • You have a number n, a positive whole number
      • if n is even, divide n by 2
      • Otherwise, apply the formula 3n + 1
    • With this new value, repeat the above steps again

The conjecture predicts that whatever the value of n, the series will sooner or later decay down to the sequence 1, then 4, then 2, then 1. Once you reach 1, you will enter a loop that repeats the sequence 1, 4, 2, 1 forever. The repeating “1, 4, 2, 1” sequence is called a cycle. I don’t want to go into the Collatz Conjecture in detail, but you can play with some numbers and satisfy yourself that this is the case for any numbers you can do on paper, and in your head. There are also many videos on YouTube about it, where people both explain it and demonstrate it for some numbers.

It is a conjecture because it has never been proven for all integers. It had been checked computationally for integers as high as $5.7 \times 10^{18}$. Such checking might be furnished as “strong evidence” in support of Collatz, but it falls short of a convincing proof. It remains one of Mathematics’ unsolved problems.

Meanwhile, there are other sequences that have their own conjectured cycles. Dr. N. J. Wildberger (2013) has found in his research that replacing 2 and 3 in the algorithm with 2 and 5 has 1, 6, 3, 16, 8, 4, 2, 1 as one of its cycles. But if you start with n = 5 with the latter scheme, you get another cycle immediately after the first term: 26, 13, 66, 33, 166 83, 416, 208, 104, 52, 26, repeating forever. Things get haywire pretty soon however, when n=7, numbers shoot up to the higher reaches of unsigned int in my C++ program, but after 18,613,331 iterations with no repetition or any other kind of end in sight, I hit Control+C and stopped execution.

I changed the integer type to int1024_t, and by the 20,000th term, the numbers have been hovering around 308 digits for some time, and have likely reached the limitation of the widest integer type I could find. But early on as it proceeded into the thousands of terms, you could see it going down a little, but overall, the numbers swelled.

But was it a high-flying numerical cycle? Repetition was checked by running the program under UNIX’s script program, then checking the typesript file for the numbers it captured. I examined it in vi, and checked to see if the last number in the file was repeated anywhere. It wasn’t. The  same appears to happen with n = 9.

We can change the algorithm slightly to:

• • • • You have a number n, a positive whole number
        • if n is even, divide n by 2
        • if 5 divides n, divide n by 5
        • Otherwise, apply the formula 7n + 1
      • With this new value, repeat the above steps again

This produces a cycle when n = 6: 3, 22, 11, 78, 39, 274, 137, 960, 480, 240, 120, 60, 30, 15, 3, pretty much from the second term. I’ve observed the same cycle when n =12, 15, 17, 19, for example. The doubles and quintuples of these numbers would also be infinite. Also, members of the aforementioned cylcle would predictably also produce the same cycle. n = 13 goes as high as 26,374,440 before coming down to 1. When the cycle terminates in my program, it is because the old pattern of 4, 2, 1 was observed.

The listing for the latter code is shown below:

#include <iostream>
 
int main() {
  unsigned long n;
  unsigned long highest = 0;
  unsigned long terms = 1;
  std::cout << "Enter a number: ";
  std::cin >> n;
 
  while (n > 1) {
    std::cout << n << "\n";
    if (n > highest) { highest = n; }
    terms++;
    if (n % 2 == 0) {
      n = n / 2;
    } else if (n % 5 == 0) {
      n = n / 5;
    } else {
      n = 7*n + 1;
    }
  }
  std::cout << "There are " << terms << " terms in the sequence.\n";
  std::cout << "The maximum term is: " << highest << ".\n";
}