The many ways of, um, … conjecturing about Collatz

Hits: 6

Article attached to this image is at:

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 =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; }
    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";

Ubuntu on Windows 10

Hits: 26

For some years now, Windows and Ubuntu have been coexisting to a degree, if you enable the Linux subsystem on windows and download the Ubuntu for Windows package from the Windows App store.

It makes it possible to muck about with Windows drivers and the Windows kernel from within a UNIX environment. Even make your own drivers that can send direct commands to the Windows kernel and even the TCP/IP stack. So long as you like the command line, there are some pretty cool tools and languages, such as C/C++, python, perl, and many of the other usual suspects at your disposal. It doesn’t really have support for Java, except as a runtime envirnonment. That shouldn’t stop you from installing JDK manually. You can install the one for Linux or the one for MS-Windows. Your choice. Also, there is no support at all for X-Windows.

The /mnt directory is used to house all of the drive letters that are visible to Windows. Here they are mounted as folders each named after their drive letter.

I can’t run MS-Windows commands like Notepad from the shell; but it turns out the Windows paths are not set by default in Ubuntu. Typing /mnt/c/Windows/notepad.exe allowed it to run. In fact, it can run any windows command, if you take the time to fix the $PATH variable. In addition, the Ubuntu subsystem doesn’t yet support the reading of ext3 filesystems, although it has no problem reading NTFS filesystems. An EXT3 driver I tried was able to identify and mount EXT3 filesystems (assigning it a drive letter) from within Windows, but no files were visible. I was offered to format the drive, but I declined. So, I wasn’t sure of the rationale for even having this driver if I can’t see any files.

Apart from that, it appears as if the main architect of the ext2 driver project, Matt Wu, has abandoned the project and has reduced his website to a blank webpage. I don’t see any updates on SourceForge later than 2015.

Compiling The Linux Kernel Docs

Hits: 61

In the last article, I said that compiling and installing source versions of software was akin to “going rogue”. I must confess that I have compiled from source and installed software that wasn’t in my distribution, most recently TexStudio, as being one of the larger projects, requiring tons of other libraries and whatnot to also be installed (or quite often, compiled from source on the side), since it wasn’t a part of the linux distro I was using at the time. It also wasn’t a part of Cygwin, and I compiled for that too. It was a great way to kill an afternoon.

But there was a time that I had compiled the kernel from source. It was necessary for me, as speed was an issue and I had slow hardware at the time. What I also had was a mixture of hardware pulled from different computers at different times. I researched specs on sound cards, network cards, video cards and the motherboard chipsets, and knew what specs to tweak on the kernel compilation dialogs, so I could get the kernel to do the right thing: which is to be fast and recognize all my hardware. I was doing this before the days of modules, with the version 1.x kernel. It worked, and it was noticeably faster than the stock kernels. X-Windows on my 80486 PC ran quite well with these compiled kernels, but was sluggish to the point of un-useable with a stock kernel running. Every few versions of the kernel, I would re-compile a new kernel for my PC, and pretty soon using the tcl/tk dialogs they had made things pretty easy, and I could answer all the questions from memory.

But then that all ended with version 2. Yes, I compiled a version 2 kernel from source, and yes, it ran OK. But it also had modules. The precompiled kernels were now stripped down and lean, and the modules would only be added as needed when the kernel auto-detected the presence of the appropriate hardware. After compiling a few times, I no longer saw the point from a performance standpoint, and today we are well into kernel version 5.3, and I haven’t compiled my own kernel for a very long time.

For the heck of it, I downloaded the 5.3 kernel, which uncompressed into nearly 1 gigabyte of source code. I studied the config options and the Makefile options, and saw that I could just run “make” to create only the documentation. So that’s what I did.

It created over 8,500 pages of documentation across dozens of PDF files. And 24 of them are zero-length PDFs, which presumably didn’t compile properly, otherwise the pagecount would have easily tipped the scales at 10,000. The pages were generated quickly, the 8,500 or more pages were generated with errors in about 3 minutes. The errors seemed to be manifest in the associated PDFs not showing up under the Documentation directory. I have a fast-ish processor, an Intel 4770k (a 4th generation i7 processor), which I never overclocked, running on what is now a fast-ish gaming motherboard (an ASUS Hero Maximus VI) with 32 gigs of fast-ish RAM. The compilation, even though it was only documentation, seemed to go screamingly fast on this computer, much faster than I was accustomed to (although I guess if I am using 80486’s and early Pentiums as a comparison …). The generated output to standard error of the LaTeX compilation was a veritable blur of underfull hbox’es and page numbers.

For the record, the pagecount was generated using the following code:

#! /bin/bash
list=`ls *.pdf`
for i in $list ; do
        # if the PDF is of non-zero length then ...
        if [ -s "${i}" ] ; then 
                j=`pdfinfo ${i} | grep ^Pages`
                j=`awk '{gsub("Pages:", "");print}' <<< ${j}`
                # give a pagecount/filename/running total
                echo ${j}	    ${i}    ${tot}
                # tally up the total so far
                tot=$(($tot + $j))

echo Total page count: ${tot}