THE COLLATZ CONJECTURE
Editor's Note: In this submission Jay G. ('16) provides an explanation of the Collatz Conjecture and his personal attempt at proving the conjecture using a tree diagram.
Basic Background:
The Collatz conjecture was proposed by Lothar Collatz in 1937. Lothar Collatz found that if you take any number and divide it by 2 if it is even or multiply it by 3 and add 1 if odd, you will end up at 1 no matter what if you follow this pattern. For example, for 5 we would multiply it by 3 and then add one because it is odd, which equals 16. Now we divide 16 by 2 because it is even which yields 8. We then divide 8 by 2 again because it is even we get 4. Then 4 divided by 2 for the same reason, which equals 2, then 2 divided by 2, which gives our final value 1. These sequences of steps can be expressed as 3n+1 for any odd value and n/2 for any even value where n is any whole number. The reason why this conjecture is called a conjecture is because it has never been proven. In fact Collatz offered a 500 dollar reward for the answer. Many proofs have been tried, and many have come close, but all have ended up in having small flaws. All proofs make connections between how odd numbers will end up as even numbers when we multiply them by 3 and add 1. Thus this allows odd numbers to be divided. But this then begs the question why multiply by 3, and how could this number possibly end up at 1. This is the question mathematicians have been trying to answer for years. Though there is no proof, all whole numbers that are less than or equal to 19*2^58, which is equal to about 5.48*10^18 have been proven. Unfortunately, the only way to prove the conjecture wrong is by using a number in the parameters of the conjectures and finding that it does not equal one or will never equal one. The difficulty with this is that if the number cannot equal one, the sequence will never end. However, some numbers have sequences that go on for thousands of steps. As a result, if we find a number that had billions of steps and still have not reached 1, we cannot assume that it does not eventually reach one because the number could just be part of a really long sequence. This is why disproving the conjecture or finding the proof is very hard to do, as a result if the conjecture truly is wrong and does not have a proof, we can never know for sure, do to the infinite possibility of numbers in the universe.
Tree Diagram:
Before I did any research I decided to go about the conjecture in my own way. I knew I wanted to do a tree diagram of the conjecture, but I had no idea where to start. As a result I decided to think about the conjecture in a backward fashion. Instead of finding 1 with a random whole number I decided to find what could equal one through the parameters of the equation. As a result I started with 1 and multiplied it by 2 and stopped as 1024 shown by the “capped" sign. (Note: the “capped” sign means that I decided to end that part of the tree there). For the purposes of this problem/diagram let us call this branch “main street” (the trunk of the tree). So for every number on main street I wanted to see if there was a whole number that I could multiply by 3 and add 1 to get that number. This process can be represented by the equation 3n+1=t (t being an existing number already on the tree that I wanted to use). If such a number existed I drew a horizontal arrow to that number. Like wise upward arrows represent when I multiplied a number by 2, which is the reverse for n/2. Off of “main street” I repeated this process for as many numbers as I possibly could on the four sheets of paper I used. What I found that if we started with any number on the sheet and followed the Collatz rules we would eventually find our way down the tree onto main street and then back to one. So, theoretically all the whole the numbers in the universe not on this sheet have to go through one of the capped numbers that I stopped at on the tree, which leads to 1. After finishing the tree I noticed a couple really interesting things. All numbers take different number of steps to get back to main street regardless of how high the number is. For example 1180 takes a very small amount of steps to get back to 1 because it is on a side street right next to main street compared to 39. 39 is much farther from main street and takes many more steps even though it is a much smaller number. Now lets look as we look at 1296 and 1204. These two numbers are very close, with a difference of only 92. However, do not let that fool you, in fact these two numbers are from two very different branches of the tree. 1296 can be found all the way at the top of the right side of the tree and leads back to 16. 1204 can be found at the left side of the tree and leads back to 256 on main street. As a result, I can conclude that the hierarchy of numbers in the conjecture has no correlation to where the numbers lead or how many steps they have. Also, another thing I noticed was that below 1024 on main street all the numbers I found on the tree led back to only three of the main street numbers: 256, 64, and 16. As a result, with this tree we can visibly see that since 16 is the lowest number before the tree branches out we can conjecture that all numbers in the universe other than, 8, 4, 2, 1, and 0 have to go through 16 to get to 1. Another interesting thing that I noticed with the tree is that there seems to be something like a paradox in it. As I found all the numbers that led to one by using the conjecture in reverse, I would sometimes find even numbers that could be multiplied by 3 and add 1 to get a number on the tree (Note: I stopped these numbers with brackets). So if I got an even number I would end it. I did this because if I continued the number I would repeat a section of the tree I already found. There are two important things to draw from this. The first is the idea of the paradox. If we attempt to arrive at the number 2 using the conjecture backward we arrive there in one easy step the same way every time, right? No. Actually you can arrive at two in different ways. So for example, when we get to the number 7 on the tree, we could say 2 can be multiplied by 3 and add 1 to get 7. So 7 leads to 2. So now we have a paradox to get to 2 in two different ways. But this is where it gets weird. Once we get this “second” 2 we cannot get back to 7 if we use the conjecture, instead it goes back to 1. So the conjecture in my eyes is almost like a lobster trap. The 2 is the lobster and the spot where the new 2 is, is the trap. We can get the 2 into the trap, but it cannot escape back into the tree using the conjecture. In fact the 2 jumps. It jumps from its new spot on the tree back to main street where the original 2 is (this is the paradox). This is the same for any even number found when trying to find a value that works in my equation: 3n+1=Existing tree number (plug in). So the contraction repeats itself through this sort of paradox. However, the crux of this tree diagram is to visually show the path a number needs to take to get to 1, and how complicated the tree can get, which makes it so hard to prove.
Note: Please ignore orange colored pencil (mistake) and green colored pencil (mistake)
Note: Corresponding colors from the tree equals the continuation of those numbers in the conjecture somewhere else on the page. For example the numbers in the purple box on the right side of the tree corresponds to those numbers continuation in the tree in purple box on the bottom left of the page.
The Collatz conjecture was proposed by Lothar Collatz in 1937. Lothar Collatz found that if you take any number and divide it by 2 if it is even or multiply it by 3 and add 1 if odd, you will end up at 1 no matter what if you follow this pattern. For example, for 5 we would multiply it by 3 and then add one because it is odd, which equals 16. Now we divide 16 by 2 because it is even which yields 8. We then divide 8 by 2 again because it is even we get 4. Then 4 divided by 2 for the same reason, which equals 2, then 2 divided by 2, which gives our final value 1. These sequences of steps can be expressed as 3n+1 for any odd value and n/2 for any even value where n is any whole number. The reason why this conjecture is called a conjecture is because it has never been proven. In fact Collatz offered a 500 dollar reward for the answer. Many proofs have been tried, and many have come close, but all have ended up in having small flaws. All proofs make connections between how odd numbers will end up as even numbers when we multiply them by 3 and add 1. Thus this allows odd numbers to be divided. But this then begs the question why multiply by 3, and how could this number possibly end up at 1. This is the question mathematicians have been trying to answer for years. Though there is no proof, all whole numbers that are less than or equal to 19*2^58, which is equal to about 5.48*10^18 have been proven. Unfortunately, the only way to prove the conjecture wrong is by using a number in the parameters of the conjectures and finding that it does not equal one or will never equal one. The difficulty with this is that if the number cannot equal one, the sequence will never end. However, some numbers have sequences that go on for thousands of steps. As a result, if we find a number that had billions of steps and still have not reached 1, we cannot assume that it does not eventually reach one because the number could just be part of a really long sequence. This is why disproving the conjecture or finding the proof is very hard to do, as a result if the conjecture truly is wrong and does not have a proof, we can never know for sure, do to the infinite possibility of numbers in the universe.
Tree Diagram:
Before I did any research I decided to go about the conjecture in my own way. I knew I wanted to do a tree diagram of the conjecture, but I had no idea where to start. As a result I decided to think about the conjecture in a backward fashion. Instead of finding 1 with a random whole number I decided to find what could equal one through the parameters of the equation. As a result I started with 1 and multiplied it by 2 and stopped as 1024 shown by the “capped" sign. (Note: the “capped” sign means that I decided to end that part of the tree there). For the purposes of this problem/diagram let us call this branch “main street” (the trunk of the tree). So for every number on main street I wanted to see if there was a whole number that I could multiply by 3 and add 1 to get that number. This process can be represented by the equation 3n+1=t (t being an existing number already on the tree that I wanted to use). If such a number existed I drew a horizontal arrow to that number. Like wise upward arrows represent when I multiplied a number by 2, which is the reverse for n/2. Off of “main street” I repeated this process for as many numbers as I possibly could on the four sheets of paper I used. What I found that if we started with any number on the sheet and followed the Collatz rules we would eventually find our way down the tree onto main street and then back to one. So, theoretically all the whole the numbers in the universe not on this sheet have to go through one of the capped numbers that I stopped at on the tree, which leads to 1. After finishing the tree I noticed a couple really interesting things. All numbers take different number of steps to get back to main street regardless of how high the number is. For example 1180 takes a very small amount of steps to get back to 1 because it is on a side street right next to main street compared to 39. 39 is much farther from main street and takes many more steps even though it is a much smaller number. Now lets look as we look at 1296 and 1204. These two numbers are very close, with a difference of only 92. However, do not let that fool you, in fact these two numbers are from two very different branches of the tree. 1296 can be found all the way at the top of the right side of the tree and leads back to 16. 1204 can be found at the left side of the tree and leads back to 256 on main street. As a result, I can conclude that the hierarchy of numbers in the conjecture has no correlation to where the numbers lead or how many steps they have. Also, another thing I noticed was that below 1024 on main street all the numbers I found on the tree led back to only three of the main street numbers: 256, 64, and 16. As a result, with this tree we can visibly see that since 16 is the lowest number before the tree branches out we can conjecture that all numbers in the universe other than, 8, 4, 2, 1, and 0 have to go through 16 to get to 1. Another interesting thing that I noticed with the tree is that there seems to be something like a paradox in it. As I found all the numbers that led to one by using the conjecture in reverse, I would sometimes find even numbers that could be multiplied by 3 and add 1 to get a number on the tree (Note: I stopped these numbers with brackets). So if I got an even number I would end it. I did this because if I continued the number I would repeat a section of the tree I already found. There are two important things to draw from this. The first is the idea of the paradox. If we attempt to arrive at the number 2 using the conjecture backward we arrive there in one easy step the same way every time, right? No. Actually you can arrive at two in different ways. So for example, when we get to the number 7 on the tree, we could say 2 can be multiplied by 3 and add 1 to get 7. So 7 leads to 2. So now we have a paradox to get to 2 in two different ways. But this is where it gets weird. Once we get this “second” 2 we cannot get back to 7 if we use the conjecture, instead it goes back to 1. So the conjecture in my eyes is almost like a lobster trap. The 2 is the lobster and the spot where the new 2 is, is the trap. We can get the 2 into the trap, but it cannot escape back into the tree using the conjecture. In fact the 2 jumps. It jumps from its new spot on the tree back to main street where the original 2 is (this is the paradox). This is the same for any even number found when trying to find a value that works in my equation: 3n+1=Existing tree number (plug in). So the contraction repeats itself through this sort of paradox. However, the crux of this tree diagram is to visually show the path a number needs to take to get to 1, and how complicated the tree can get, which makes it so hard to prove.
Note: Please ignore orange colored pencil (mistake) and green colored pencil (mistake)
Note: Corresponding colors from the tree equals the continuation of those numbers in the conjecture somewhere else on the page. For example the numbers in the purple box on the right side of the tree corresponds to those numbers continuation in the tree in purple box on the bottom left of the page.
Source:
Weisstein, Eric W. "Collatz Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CollatzProblem.html
Weisstein, Eric W. "Collatz Problem." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/CollatzProblem.html
