You may have heard of Collatz Conjecture, it’s simple enough to explain to a 2nd grader, yet has stumped mathematicians for the last 80 years. Paul Erdos famously referred to it when he said “Mathematics is not yet ready for such problems.” I like exposing students to unsolved problems in mathematics, because it gives them a real sense for what mathematicians do (also their’s no pressure to solve it).
I have explored it with a variety of ages, last year I had a fruitful experience with my 5th-6th grade class and thought others would enjoy the investigation. Below you will find two ways to introduce the conjecture, and a method for reversing the recursive formula to “grow the Collatz tree.” This investigation also hits a few of the Expressions and Equations standards, such as 6.EE.A.1-2, and 6.EE.B.5.
1. Take any natural number n.
2. If its even divide by two, if its odd multiply by three and add one.
Repeat step 2 indefinitely. The conjecture states that you will always reach 1 eventually.
For example, say you start with 5 your sequence would go 5-16-8-4-2-1.
The Game Intro: One way I’ve introduced it in the past is to have the students play a game where they roll a 10 sided die for a starting number. Then the person who gets to one in the most number of steps wins. Students quickly realize they can create a diagram, or tree network, which tells them right away who will win. Sometimes we extend it, by playing the game with 20-sided die and trying to solve that version as well. Here’s what the tree network might look like for the game with a ten sided die.
The Human Tree Intro: Another way to introduce it that is more kinesthetic, is to give each student a number on a sticky note, name tag, or index card. Then say if your number is even, look for the person that is half your number and if your number is odd find the person with one more than triple your number. Once they find their person they can connect with them by holding their hand or putting their hand on their shoulder. I usually make a stack starting with one, going up the “Collatz Tree” until I have enough numbers for the amount of students and teachers in the group. I also try to make it so there are several branchings. When everyone is “connected,” the group should work to untangle themselves so that the overall structure can be seen. I wish I had a picture of the process, and outcome, but alas I couldn’t find one.
Growing the Collatz Tree (doubling)
Once students get familiar with the structure of the Collatz tree we talk a bit about what it would mean for the conjecture to be true. Can we prove that a certain set of numbers will always go to one. Quickly students discover that as soon as you hit a power of 2, you are dividing by two all the way down. I like calling this the “tower of powers.”
We use the powers of 2 as the “trunk” of our Collatz tree, and the first example of a way to grow the Collatz Tree. You can reverse the recursive formula and double any number to “grow a branch” of the tree. For example, 5 could have come from 10, which could have come from 20, which could have come from 40, etc.
Branching Rule (n-1)/3
Then I ask the students to notice when there are “branchings” in the tree, in other words when are there two numbers that will lead to the same number such as 5 and 32, both lead to 16. Here students have to think about when (x-1)/3 will have an integer solution. This happens when a number is one more than a multiple of three. So we reviewed the divisibility rule for 3, and tried it out on a few examples.
Students worked in groups to apply these two methods to grow the Collatz tree. There are lots of opportunities to differentiate the process, as students noticed patterns in branchings and some wrote algebraic expressions to describe the branches. For example, the 3-6-12… branch above can be described as 3*2^n.
Here is an example of what one group made:
Extensions and Connections
1. If you extend the recursive formula into the complex plane you get the fractal below. For a thorough explanation check out the blog post by Nathaniel Johnston.
2. Dan Finkel over at mathforlove.com has a variation called “The Dr Squares Puzzle” where they come up with a similar recursive process, with a few loops.
3. Here’s another recursive process involving numbers and their written form (It also has a tree structure):
Step one: choose a natural number N
Step two: write the number in words, count the number of letters in the word and write that number.
Step 3: Repeat Step two.
For example: One-3-Three-5-Five-4-Four… stays at four indefinitely. You can also try other languages.
Finally, a post on Collatz Conjecture wouldn’t be complete without this from XKCD: