Fun with Collatz Conjecture

Collatz Formula

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.

Collatz Conjecture:

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.

Introduction:

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.

Collatz Tree for a game with ten sided dice

Collatz Tree for a game with ten-sided dice

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)

IMG_0002

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.

IMG_0004IMG_0006IMG_0009

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:

IMG_0002

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.

collatz fractal

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. :)

For English it has a tree like structure.

For English it has a tree like structure.

Finally, a post on Collatz Conjecture wouldn’t be complete without this from XKCD:

collatz_conjecture xkcd

About these ads

5 Comments

Filed under 6.EE, Elementary, Games, Graph Theory, Mathematical Investigations, Middle School, Unsolved Problem

5 responses to “Fun with Collatz Conjecture

  1. I love that you introduce problems that haven’t been solved. Math students are often scared of finding the wrong answer, but there is no wrong answer (or pressure) when the solution is unknown.

    For me, as an Algebra I teacher, I find this problem mind blowing and commend you for introducing it so early to so many different grades. Students are clearly exposed to multiple levels of thinking throughout the process.

    You also made it FUN! Fun, fun, fun! Let’s roll a die and get to the bottom of this. Investigation is the foundation for true learning as students have the chance to struggle and make mistakes, but move forward by learning from those!

    EXCELLENT! (I’m still afraid to try this with my high school students; maybe I’ll take the leap)

  2. I think I might just try this! I teach 7th grade and would have never considered posing a problem like this to my students. As Joshua said, “There’s no wrong answer if the solution is unknown.” Thanks for sharing your experiences,

  3. This was great, thank you for sharing. I will share this with my kids.

  4. Hi Federico,

    Thanks for sharing this great idea, and thanks for posting pictures of student work. I, like Joshua above, am really excited to have another way to explore open questions in mathematics. We’ve kicked around the twin prime conjecture a bit in the past, but I think the Collatz conjecture offers even more room for exploration. I look forward to corresponding with you more!

    -Jason

  5. Pingback: Sierpinski’s triangle and snap cubes. | mikesmathpage

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s