“I was told there would be no math.” Chevy Chase
This challenge pitted us against the dreaded “3n Problem” that has perplexed mathematicians since Lothar Collatz first proposed it in 1937. We were supposed to analyze data that we produced using a MicroWorlds EX program that Professor Stager wrote. The software functioned as the machine into which one could input numbers; the machine did the necessary calculations on the number until it completed the number of generations necessary to get the number to produce the “4 2 1” repeating pattern.
I started by entering a series of numbers and watching them crank through the generations until they reached the repeating pattern.
Number Generations 2600 25 2061 175 2062 35 2063 35 2064 123 2065 123 2066 154 2067 154 2068 123 2069 123 2070 123 2071 123 2072 123 2073 35
Admittedly this was too small a sample to recognize much except for the fact that sequential numbers would sometimes have the same number of generations, as shown above with 2068-2072.
DIssatisfied with needing to sit in front of the computer and manually enter numbers, I downloaded the 3nToolsEX one of which is a program that will run numbers for you, starting with a number you specify and keeping track of any number that has at least as many generations as a number you also specify.
I started by running the numbers 3-1003 with 23 as the minimum number of generations to track. An interesting visual pattern emerged when I entered the data into an Excel spreadsheet.
As the numbers increased from 3 towards 1003, it seemed that with some exceptions the number of generations decrease, resulting in the gentle arcs shown above in the graphed data. I also found that using a small generation number and starting with a small number gave a lot of data, which was useful in seeing a general pattern.
Intrigued, I let the overnight program run overnight, starting at 1004 with 50 generations as the minimum to track. In the morning I stopped it at 20,004.
The same visual pattern emerged with this much larger sample. I posted all of my data to Blackboard, where Brad made good use of it and sorted the data for 1004-20,004 by the number of generations.
Brad’s grouping by generation graph reveals the same gentle arc that shows generations decrease as the numbers increase
Finally, I ran 20,005-45,005 with 50 generations.
The same visual pattern remained in this data. Now it was time to interpret the data and make a hypothesis.
Interpretation and Hypothesizing
I traded some ideas on Blackboard, mostly with Allen and Brad. As it happened, I went to a party that I knew a math teacher who works with my wife would also be attending, so I hauled along my pretty graphs and asked him to discuss the Collatz conjecture with me and make sense of what was happening. He was quite excited for the chance to talk math!
I brought along Professor Stager’s description of the Collatz conjecture and let him read it. We then looked at the graphs and I discussed what they were charting and how I had noticed the visual pattern persisting through my data.
With that we were ready to make a hypothesis about this problem.
I give Jim all the credit for this hypothesis; all arguments should be directed my way, however.
If we ever do find a number that does not eventually generate the “4 2 1” pattern it will be an odd number. We know that from the numbers 1-45,000 all the numbers generate down to the repeating pattern. If we go beyond 45,000 and consider more numbers, the first even number that we come to, 45,002, will be “cut in half” by the rules of the conjecture, to 22,501, which is back in the pool of numbers that we have already considered and know will generate down to the pattern. However, an odd number beyond 45,000, like 45,001, will by the rules of the conjecture be multiplied by 3 and 1 will be added to it, thereby making this number outside of the pool of considered numbers and potentially a number that does not generate down to the “4 2 1” repeating pattern. Let me elaborate a bit and provide an example.
Let us consider the number 1001. We know that 1-1000 all generate down to the repeating “4 2 1” pattern by the data that I processed.
• 1001 becomes 3003 + 1 = 3004.
• By the rules we then process this even number to be 1502
• 1502 is an even number, so we cut it in half to become 751
• 751 is below 1000, so we can deduce at this point that the number will eventually generate the pattern
It is impossible for the first number that does not generate the “4 2 1” repeating pattern to be multiplied by 3, have 1 added to it to make it an even number, then be divided by two: this will bring it back into the group of number that do generate down to the “4 2 1” repeating pattern.
Consider the number z as the number that does not degenerate. If we go through the procedure we have x numbers that generate down to the “4 2 1” repeating pattern. Defining z as the first number that does not generate the “4 2 1” repeating pattern, the first number to break the conjecture has to be odd because if it is even we have to divide it by 2, then we’re back below z and we know anything below z generates the “4 2 1” repeating pattern.
Generation Must Be 1 z odd 2 3z + 1 even 3 (3z +1) / 2 odd 4 (3(3z + 1)/2) + 1 even
As Jim explained it, the exercise becomes adding restrictions to z. Eventually and ideally you look at restrictions that conflict and prove that the number cannot exist. It will also show that if you find one such number you will find an infinite set of numbers, because every iteration will provide an infinite number of numbers. Interesting and heady stuff.
This was a frustrating and enlightening exercise. Like Brad I wish more people had participated in a dialogue about what we were seeing with the data we generated. However, I was very happy to have had my conversation with Jim where we were able to generate a hypothesis. Jim and I agreed that a student would need to know algebra, ideally, to undertake this exercise as it provided a way to represent unknown numbers. Overall, another interesting Learning Adventure, one that made me think in new ways and consider equally new concepts.