1
Oct

Collatz Conjecture (3x+1 Problem)

Introduction:

The Collatz Conjecture, also known as the 3x+1 problem, is simple by definition, but upon further research it becomes a very complex theory. Basically, the problem goes as this: an integer (x) is chosen and then systematically broken down into a result of 1. The system runs in two different operations. If the integer (x) is odd, then it is multiplied by 3 and then added 1 (3x+1). The second operation is that if the integer (x) is even, then it is divided by 2 (n/2). The integer is broken down by these two operations until it’s result is 1. For example:

x = 5

5 is odd, so multiply by 3 and add 1:

16 is even, so divide by 2:

8 is even, so divide by 2:

4 is even, so divide by 2:

2 is even, so divide by 2:

result is 1 .

In it’s mathematical form, the formula is:

From Collatz Problem

The Collatz conjecture has been verified for all integers from 1 to 599 * 1015. However, for this experiment, the computer being used is not a supercomputer capable of processing that high integer amount. Instead, the numbers from 2 to 100,000 will be explored. These results were recorded with a simple C++ program with a few loops and counters included.

Statistics:

These are the raw statistics taken from a few different intervals of integers (or test sets). First, with (x) being 1 to 10, second 1 – 100, third, 1 – 1000, and so on. All of which resulted successfully with a 1 as the final answer. The amount of steps (or operations) that it took to get to this result were recorded. The numbers in bold and parenthesis indicate which value of (x) had the maximum number of steps along the way.

From Collatz Problem

Interestingness:

In order to dig deeper for more interesting figures and facts, information from the table above will be used to find possible patterns or relationships between the results. One pattern found was that for each zero added onto the amount of integers to go through (or for each multiple of 10), the average (or mean) amount of steps taken to reach the result of 1 took 25 steps more than the last one. For example, integers 1 – 100 took on average 31.74 steps to reach the end result. Integers 1 – 1,000 took on average 59.6 steps to reach the end result. The different between these two averages is about 25 steps. This trend continues through to 1 – 100,000.

Another relationship is that the highest number of steps taken were from integers (x) with odd values. In sequence, they are: 9, 97, 871, 6171, and 77031. Respectively, these each took 19, 118, 178, 261, and 350 steps to result in 1.

When trying to calculate to the (x) value of 1,000,000, the time it took to record the data made a significant rise in time. The time it took to record the data of x = 100,000 took a few seconds whereas the amount of time it took to record the data of x = 1,000,000 was never concluded even after 10 minutes of waiting. The computer it was done on has an Intel Dual-Core CPU with 1024MB DDR2 RAM. It was interesting to see it make such a huge gap between x = 100,000 and x = 1,000,000.

The results of each test set were pulled into a statistical program and graphed onto a scatterplot, with the x-axis being the integers and the y-axis being the steps taken. The graphs turned out to be something of an art form, with plots making a unique spread across the coordinate plane. Each test set has it’s own uniqueness.

From Collatz Problem

Conclusion:

It’s easy to see why this particular conjecture has been so interesting to mathematicians and programmers. This theory has been tested and reviewed by some very brilliant minds and has yet to be proven as a law although there have been some great and intense efforts in trying to prove the “unprovable Collatz problem.” There have been some very close proofs, but none of which have actually been approved to be a proof.

The findings in this document were of significance only to a curious mind. They didn’t require much effort or thought, but rather, they were a product of what might have been interesting as the beginning steps to analyzing this function.

 

Sources:

Eric Roosendaal on the 3x+1 problem:

http://www.ericr.nl/wondrous/index.html

Simon Fraser University on the 3x+1 problem:

http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/node2-an.shtml

Kenneth Conrow, The Structure of the Collatz Trajectories with an Inductive/Constructive Proof of the

Conjecture, http://www-personal.ksu.edu/~kconrow/colstruc.pdf

 

Feel free to donate if this post prevented any headaches! Another way to show your appreciation is to take a gander at these relative ads that you may be interested in:


There's 2 Comments So Far

  • Your Proud Mom
    October 4th, 2007 at 1:43 pm

    Derek, You are a really deep thinker and you do a good job of trying to make it easy to the “average joe” (like me Ha!) You better have gotten an “A+”
    Love you, Mom

  • Austin
    December 22nd, 2007 at 1:53 pm

    Great article. The 3n+1 problem seems to be the classic “hard problem”. I have used the Ulam Spiral to visualize iterations over many whole numbers at once and have created a video you may be interested in.
    Collatz Iterations on the Ulam Spiral grid

Share your thoughts, leave a comment!