I enjoy looking at unsolved math problems with the boys. Although there aren’t too many of these problems that are accessible to kids, some of the ones that they can understand are pretty neat. Today I decided to return to the Collatz conjecture and present a “new to me” twist on the problem described by John Conway in his essay “On Unsettleable Arithmetical Problems.” I saw the essay in the book pictured below, which I cannot recommend highly enough:
We began by taking a fresh look at the Collatz Conjecture. The statement of this particular unsolved problem involves only a little bit of arithmetic and talking about this problem is a really great way to show some interesting math and build up a little number sense at the same time. Here is the problem:
Step 1: Pick any positive integer .
Step 2: If is even divide it by 2, and if is odd multiply it by 3 and then add 1.
Step 3: Repeat step 2 with the number you ended up with after step 2, but stop if you ever get to 1.
For example, if you start with the number 3 you get the sequence: 3, 10, 5, 16, 8, 4, 2, 1.
For any number that has ever been tested, whether by hand or by computer, the sequence always ends up at 1. The Collatz conjecture states that every integer will end up at 1 eventually. Although many people believe that this conjecture is indeed true, it has not been proven to be true.
Here is our introductory discussion of the problem:
In the second part of our project today I introduced the twist on the Collatz conjecture that Conway describes in his essay:
Step 1: Start with any positive integer n.
Step 2: If the integer from the previous step is of the form:
2.a: 2k, make a new integer 3k,
2.b 4k + 1, make a new integer 3k + 1,
2.c 4k – 1, make a new integer 3k – 1.
Step 3: Repeat step 2 until you encounter a number you found previously.
For example, if we start with the number 4, we get the sequence: 4, 5, 9, 7, 5, and then back to 4.
As with the Collatz problem, there’s not much that mathematicians have been able to say about this new problem. There are a few known cycles, like the example above, but for most integers the sequence you get from following Conway’s process seems to go on forever without repeating.
In our introductory talk about this new problem we go through one example and then spend a little bit of time talking about why all positive integers are either even (step 2a above), one more than a multiple of 4 (step 2b), or one less than a multiple of 4 (step 2c). This discussion hints at a basic idea in number theory called modular arithmetic.
Next we talked about why Conway’s problem is a little bit different than the Collatz conjecture. One of the things that’s really interesting is that you can run the computations in Conway’s problem both forwards and backwards. You can’t do that in the Collatz problem because multiple numbers can map to the same number. For example, in the Collatz problem the number 10 can come from dividing 20 by 2 or by taking 3 and multiplying it by 3 and adding 1. That means you can’t go backwards from 10.
In his article Conway plots a few of the sequences that arise in the new problem (actually, he plots the logarithm of the sequence, but that’s a detail I’ll put to the side for now). The plots look surprisingly similar to the letter V. The shape of those graphs was really surprising to me.
Because there is a connection between the number 12 and Conway’s version of the Collatz problem, he calls the pattern in the numbers you get by following the new process “amusical.” I’ll leave the description of why to him, save for this bit of mathematical comedy:
“However, since the series always ascends by a fifth modulo octaves, it does not sound very musical, and it has amused me to call it amusical.”
The connection, or lack of a connection, to music seemed to be a neat thing to illustrate for the boys, so I used Mathematica’s Sound function to create a sound for each number in a particular sequence. This part was just for fun, but watching it just now I wish I would have described the process a little better. At least you can see the Mathematica code on the screen and copy it if you want. The boys really liked hearing the music, though, and played around with the different sounds a little bit after we finished:
So, a really fun project going through two unsolved math problems. Conway uses these problems as examples of problems that may actually be no way to solve. That’s an interesting topic, too, though more than I wanted to get into today. For now the goal was to show some fun math and continue to build up their number sense. I really enjoyed this project.
8 thoughts on “The Collatz conjecture and John Conway’s “amusical” variation”
Mike, I was thinking about your work withyourkids on bases, and your mention of mod math above reminded me of two things I did w/discrete math kids. First is that in any base, the mental trick for multiply by 11 works the same. For example in base 5 , 3123 x 11 = 34353…. Which becomes 34403… And the other they might enjoy, although they are so precocious they may already know,is that casting out nines, or whatever number is one less than base, works the same . So to chech if 3123 base5 is devisible by 4, just find the digital root mod 4, and if it is zero, it is divisible, and if not, the residue is the remainder. And you can check answers in other bases by the same method as used with digital root in base 9. Sorry if this is old news to them.
I think there is a slight typo in your sequence for Conway’s twist, should be
4 6 9 7 5 4 (second term)
Somehow, this reminded me of looking at Fibonacci recursions mod 10 (or any other base you want). Start with any pair of numbers, then keep adding the last two terms of the sequence to get the next. Done modulo n, you know that all sequences will end for any starting seeds, but how many terms will you get? How many distinct chains are there? This is another case where the chains also run in reverse, so what does that tell you?