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
- You have a number n, a positive whole number
-
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
- You have a number n, a positive whole number
-
-
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"; }
at 
and tested ![A[i] > A[j]](https://www.pkjournal.net/wp-content/ql-cache/quicklatex.com-f77889e2bdbb5c5a09045451ed5d073b_l3.png "Rendered by QuickLaTeX.com")
. It was similar in that it used a nested for loop, comparison, and swap.![A[i] < A[j]](https://www.pkjournal.net/wp-content/ql-cache/quicklatex.com-5f9f5a8703e901dbecf61859f945fc2e_l3.png "Rendered by QuickLaTeX.com")
seems backward, yet the numbers end up in increasing order. This is becuase allowing both nested loops going to the array size allows for redundant comparisons and for additional swaps which can take place if 
, which he explains. Is it efficient? Hell, no. But it is still shares a similar efficiency to Bubble Sort, 
. Would anyone in their right mind offer this to students as a sorting algorithm? Nope. And yes, he does make these points also. It’s as close as I have seen to a sorting algorithm that appears “brute force”. In addition, he gives a proof of correctness of the algorithm to sort in ascending order.
, or all numbers N from 0 to infinity have a prime factorization. If it doesn’t have prime factors, then N is itself prime.
are missing (except those less than 9: 2, 3, 5, and 7). But there are a lot of repeated numbers, particularly the highly composite numbers 4, 6, 12, 24, 36, 48 as a consequence of how it was constructed. It would not past muster as magic in the way we have been expecting for this article series.
(the original 1248 square from the last post, not numbered)
magic squares, while being aware that many of them are rotations or reflections, possibly of the first 24. For example, squares 1 and 7 is a reflection; 2 and 13 is a rotation, as is 3 and 15. So, I am quite sure that 384 will not be anywhere close to the count when rotations and reflections are taken into consideration.
possible shufflings of its rows and columns to produce different squares. And thus, 
.
possible magic squares. And the larger the prime-ordered square, the greater the possibilities. By the time we get to 13×13, the number of squares becomes 
or over 38 quintillion. Counting to such a number would take more than 1.2 trillion years, hundreds of times longer than the age of the universe. And we are just getting warmed up. After all, 13×13 isn’t really that big. But I think by now I can impress on you what a “high-yielding” algorithm can do. It must be stated that there appear to be no magic squares beyond 5×5 that are pan-magic. The rest appear to be normal magic, which I will distinguish shortly.
, 
, 
, and 
represents a specific number, namely a power of 2. We get to decide which of 
, or 24 possible magic squares. So, it is not a great yield. Grogono tells us that even these squares boil down to the rotations or reflections of the same 3 pan-magic squares.
, for example. Adding the same 3 numbers will get the same total.
” so-called “controversy”, so I seem to feel better trolling my own blog about it.
“. But there is also a number pattern. It would have been better to use function notation. If 
represented an unknown formula, I would feel better if it were written this way:
, and if you know the pattern, you know the answer. Or do you?