The Collatz Conjecture

I have been fascinated by the Collatz conjecture for years. It’s a math problem that is so simple to understand, yet no mathematician has managed to solve it. Since the problem was first proposed by Lothar Collatz in 1937, many mathematicians have gone crazy trying to solve it. Here’s how it works.

The Collatz function takes one number, denoted by n, and turns it into another number. If n is even, the result is n/2. If n is odd, the result is 3n+1. For example, if n is 3 then the result is 10. If n is 4 then the result is 2. If n is 5 then the result is 16. You get the idea.

A Collatz sequence is formed by starting with a number, and repeatedly applying the Collatz function to extend the sequence. For example, the Collatz sequence for n=3 is 3-10-5-16-8-4-2-1. The Collatz sequence for n=5 is 5-16-8-4-2-1. The Collatz sequence for n=2 is just 2-1. Here is a picture of the sequences for n=7 and n=19.

After looking at some of these sequences, you may start to notice a pattern. No matter how high they go, they always seem to come back down to 1. Does every Collatz sequence always come back down to 1? Perhaps some of them get into a loop and keep going round forever, or perhaps some of them just keep going up and up towards infinity. This is the Collatz conjecture: prove that every Collatz sequence eventually comes back down to 1.

Another way to picture the problem is using total stopping times. The total stopping time of a number is the number of steps it takes for the number’s sequence to reach 1. The Collatz conjecture states that every number has a finite stopping time. Despite being such a simple problem, and being open for almost 75 years, nobody has managed to prove or disprove the Collatz conjecture.

There are a couple really tantalizing patterns in the total stopping times. Let me show you just one. Have a look at the first 1000 stopping times.

The first 100 total stopping times. The horizontal axis is n, and the vertical axis is the total stopping time of n.

Notice any patterns? It looks like some of the points are bunching up into short horizontal lines. Furthermore, these short horizontal lines seem to line up in large sweeping curves. To investigate these patterns further, I wrote a short C++ program to draw the same chart, except for the first ONE BILLION stopping times. This time, the x-axis is logarithmic.

The first one-billion total stopping times. The horizontal axis is n, and the vertical axis is the total stopping time of n.

Whoa, now that’s a pattern! Look at all those nice straight lines. Check out a closeup of the bottom-right part of that image.

Close-up of the patterns in the total stopping times

What is causing all those straight lines? Why are they all the same length? The most interesting question to me is, why is there always a long “dash” followed by a short “dot”? If we can explain the structure of these regular patterns, can we construct an exact probability distribution for the total stopping time of any number? Could this distribution be the key to finally proving or disproving the Collatz conjecture? If you want to do a bit of work on the Collatz conjecture, answering these questions might be a good place to start.

Tags: , , , , ,

41 Responses to “The Collatz Conjecture”

  1. Adam Sadovsky says:

    Very nice post, Jeff. Now I have another thing to ponder this weekend :)

  2. Jesse Onland says:

    Typo: In the second paragraph, you have “odd” and “even” interchanged.

  3. jeff says:

    Thanks Jesse! I fixed this now.

  4. wikipedia says:

    From wikipedia:

    In 1977 R. Steiner and 2000 and 2002 J. Simons and B. deWeger (based on
    Steiner) proved the nonexistence of certain types of cycles.

  5. [...] The Collatz Conjecture—an intriguing example of how graphically plotting data can sometimes lead you to more easily recognize patterns in the data. [...]

  6. Speaking of probability distributions. The rule for odd numbers increases the value of the next number, but also ensures that the next number is even. The rule for even numbers decreases the next number, which could either be even or odd. As a result, the chance of getting an even number as the result of an applied rule is greater than the chance of getting an odd number, which drives the sequence down towards one.

  7. Never mind, I’m wrong, although you could do a probability assessment, its not as easy as I made it out to be, and just shows that the result will diverge, not that it will go one direction or the other.

  8. What’s interesting is if you extend the Collatz function to the complex plane and plot the number of iterations required before convergence; it turns out to be a fractal (the so-called Collatz fractal) which I did a paper on in high school. (See http://www.nathanieljohnston.com/index.php/2009/06/the-collatz-conjecture-as-a-fractal/). Cool stuff.

  9. Des says:

    Very cool,

    I worked on the Collatz Conjectue for my final year project at Uni (Developed a Distributed Computing approach (think SETI@Home) to number crunch) – you should check out the work done by: Eric Roosendaal and Tomás Oliveira e Silva.

  10. Ralf Nieuwenhuijsen says:

    Some obversations:

    1) every odd number always immediately becomes an even number
    2) even numbers are repeatedly divided by two. This will always end in a PRIME number.

    Is 2) a proven fact? I’m not a mathimatician!

    You divide even numbers by two. If they are again an even number, you repeat this over and over again. This seems to always end in a prime number.

    Is that something that is proven? It might be crucial here. Since it was proven, then all you need to prove is that it will go to 1 for all prime numbers.

  11. Ralf Nieuwenhuijsen says:

    Oops, I submitted too early!
    And my claim isn’t true either. I found a counter example.

    But they do seem to converge to prime numbers.
    What’s going on?

  12. Bob says:

    This is equivalent to proving that eventually a number in the sequence will be a power of two.

  13. evan says:

    interesting to see how primes are mapped on this in red. I like the moire like effect…. intriguing.

  14. Nelson says:

    I made a silly experiment using the conjecture to generate music. See:

    http://wiki.freaks-unidos.net/weblogs/arhuaco/listen-to-the-collatz-conjecture

  15. [...] The Collatz Conjecture « Jeff Cameron’s Blog (jpcameron.com) – February 27, 2010 [...]

  16. John Skinner says:

    You have toooooooooo muuuuuuuuuch time on your hands. Go OUTSIDE! It’s a nice day.

  17. Alex says:

    Looks like Randall got in your head already: http://xkcd.com/710/

  18. [...] The Collatz Conjecture « Jeff Cameron's BlogI have been fascinated by the Collatz conjecture for years. It’s a math problem that is so simple to understand, yet no mathematician has managed to solve it. Since the problem was first proposed by Lothar Collatz in 1937, … Read more [...]

  19. m3kw says:

    Hint,Try subing in 0.999999 instead of one in 3n+1, use 3n+0.999999999.

  20. Matthew says:

    Hello Mr. Cameron,

    I have been curious about the Collatz conjecture for about a year now. I wrote a short, very inefficient program for my significantly insufficient TI-84 Plus Calculator, by which I have calculated and plotted the stopping times for the first ~200 positive integers. May I request to have the code for the program you wrote to find the first 1 billion?

    Thanks for your consideration.

  21. Gareth says:

    Hi there

    Very interesting post, I first heard about the Collatz conjecture in September, and am loving working on it.

    I’m looking at the problem based primarily on how many odd numbers there are in each sequence….quite fun to play with!

    one question, in your first graph, you seemed to have missed out on the stopping time of the number 27, which has a stopping time of 111.

  22. JonnyPonder says:

    While I encourage and applaud your investigations, and I THINK I fully understand the Collatz Conjecture…forgive me for sounding rather blunt, but…what is the point in it? What purpose does it serve? I cannot see how it could be useful, it seems fairly straight forward and self-explainatory, so I not see how it could be further researched into.

    I hope to hear back, please understand this isn’t a criticizm, I just think I am missing something :)

  23. mugbuff says:

    Anyone prpared to discuss my approach to the underlying structure of the conjecture ? My over ambitious claim of a proof was a tactical mistake but the criticism did not invalidate any of my calculations. Take any odd integer prime to 3 and it is possible to construct an infinity of sequences which converge to that integer; the same pattern of calculations applies to find these sequences whatever the initial integer. This could account for a large scale pattern appearing. It is easy to show that if any integer fails to converge to 1 then there are an infinity of such integers – it shouldn’t be hard to find one of them (this is a comment, not an attempt at a proof).

  24. alphachap says:

    The first one-billion total stopping times.
    It is amazing!
    Do you have a bigger image of this graph?
    (I am currently computing them with a Java Processing program.
    But I am not graphing them.)

  25. mathieu chenier says:

    because all impair number additioned by 1 will lead to a number dividable by 2 ?

  26. Ernst Berg says:

    I was just Googling and saw this.

    I too was fascinated by the 3x+1,x/2 and have written programs to use this.
    My point of view was “it seems to work all the time so trust it.”
    Anyway it’s been a dependable system.

    I wanted to share what I know from exploring the 3x+1,x/2 form and I personally use notation of brackets [] to denote a cycle. so [3x+1,x/2]
    For the 3 of 3x+1 we can say A so Ax+1,x/2 or Ax(+ or – ) y , x mod z
    For all y that is a power of three there is one attractor for all input so 3x+3,x/2 will cycle 12,6,3.. and similar for all powers of three for Y of [Ax+/-y,xmodz]

    Another thing that seems to be real is the idea of a cycle of values. The term Ring is already established as a proper math term so I will call it a ring as in a cycle.
    We all know the 4,2,1,4,2,1 of 3x+1 so it is a cycle of three or a ring size of three. That is how I am using the term ring here.
    Now since a system like 3x+5,x/2 has: Report for 3(x) + 5 Contains 6 Attractor(s) 1 19 5 23 187 347 I believe we are not looking at just 3x+1,x/2 but a larger family of systems and that family of systems has structure because it is obvious the attractors have relationships.

    Proving 3x+1 means proving 3x+5 or y = 999999999999999…. for example.

    Some attractors

    Report for 3(x) + 1 Contains 1 Attractor(s)
    1
    ———————————————-
    Report for 3(x) + 3 Contains 1 Attractor(s)
    3
    ———————————————-
    Report for 3(x) + 5 Contains 6 Attractor(s)
    1 19 5 23 187 347
    ———————————————-
    Report for 3(x) + 7 Contains 2 Attractor(s)
    5 7
    ———————————————-
    Report for 3(x) + 9 Contains 1 Attractor(s)
    9
    ———————————————-
    Report for 3(x) + 11 Contains 3 Attractor(s)
    1 13 11
    ———————————————-
    Report for 3(x) + 13 Contains 10 Attractor(s)
    1 13 131 211 259 227 287 251 283 319

    Now I worked out one day that 3x+1 is one in a set of systems where 3x+1/x/2 was a part and it is based on the facts that if we express the process of any number in any [3x+y,x/2]we can write out the 3x part as one parity (“1″) and the x/2 as the other (“0″) in an even odd or binary string.
    Then we can see that no two odd cycles ( if we represent 3x+y as a set or odd parity ) can be in a sequence sequentially because any 3x+y is followed by an x/2
    so for the iterations of one cycle it is possible to have one of 2 outcomes 0 or 1.. In 2 iterations it is possible for 00,10,01 or three and in fact it is Fibonacci
    2,3,5,8,13,21…

    The set of all functions is then 2/1,3/2,4/3,5/5,6,8,7/13… I don’t know if “all functions” is appropriate I like to call it a Universe but I’m not qualified to name things like that outside of personal labels.
    All of these can be explored. I looked into [7x-1,x/13] and adding or subtracting the Y can have different effects in different systems for different values.
    I don’s see why more complex processing is not possible such as [3(x+7*12),x/2] or sum such thing that works.. I just typed that at random..
    What they all have in common is pattern. Look at these from the parity expression they make. I don’t believe the point is the value of X it’s the pattern of value processed. In fact I consider the function to be the thing moving not value but I have several points of view I visit on these types of things..

    3/2 shows us in the form [3x+/-y,x/2] that the patterns follow Fibonacci counts but 4/3 is different using 00,01,10 and 11 in it’s pattern. So too are 7/13 with long runs of one parity symbol before the other is seen and so on..
    I figure there would be a practical use for generating patterns based on a single value for X. Proving them all is not on my todo list. I have explored a few other than 3/2 system.
    Oh by the way if we want to generate a number that has over 1 billion iterations or more the “Reverse Collatz” I wrote can do that. It’s a crude program but was my attempt to explore what creates a value of a specific distance or stopping time.
    I was looking for the natural language behind it all. The truth is the landscape changes when the Y changes. I conjecture that no two systems for Y where Y1 != Y2 have the same structure.
    Alright.. I stand by what I wrote and offer this post as a contribution.
    I have web sites and forums so if there is any need to have a forum I can add it to sites I already have up and running.
    Currently I am working on the Million digit challenge and am finding the hard truth about data but I am not out of creative approaches yet.
    all in all I like exploring these kinds of things and I assume they can be called dynamic systems. The result isn’t a number but a pattern from what I can tell.

    Ernst
    —-
    Well that’s all good..

    I also have a rudimentary program that can grow values that will be close to the natural iterations needed to reach 1 in a simple attempt at reverse [3x+1,x/2]

    So that is what i did. I am open to discuss or share.

    I was thinking that those cycles of value such as the 4,2,1 of [3x+1,x/2] may not be separate after all. Since non power of three Y values will have other than that Y in it’s attractor list is it possible that some systems connect in some way to other systems?

    Well I saw structure and pattern in the attractors and there was an upward growth in the maximum value needed to express all the instances of attractor for a given system.

    So I know that 3x+1 is not alone nor will explaining what it is doing only cover 3x+1

    In fact I think we are just looking at two functions that share a common element in a struggle between two systems of 3x and x/2.
    We are the force that causes it to cycle by artificially cycling it when 1 is a power of 2 and an odd. We allow all powers of 2 to be divided but one other wise it would head off into infinity as an endless series of x/2.

    However, since this seems so stable I have envisioned using values to create pattern that can be used is an intelligent system perhaps in robotics where the functions of operations are defined by values but are visited by the current value of x in A(x)+/-Y,X/modZ] where A=3, Y=1 and Z = 2

    Well That’s the short of it.. I’m available to share what I did so drop me a line if I can be of help ernst_Berg@Sbcglobal.net

  27. Ernst Berg says:

    One more thing..

    In the [3x+1,x/2]

    We can look at this as two sets of data. Set one is the 3x+1 data and the other is the x/2 data.
    Even and odd numbers are a part of both sets.
    x=1 means 4,13,40,121…. it’s a progression
    and given the constraints of dividing only numbers that have a power of two in them you can see that after a 3x+1 the even value that is present is a member of both sets but not a second even iif that even value can be divided by 4,8 and so on.
    So the two systems share one element. The even after an 3x+10
    I believe I was generating progressions to make the sets such as x=1 [2x] and x = 1 [3x+1] when I noticed the common element .
    So they share a common value because in [3x+1] x can be an even value and even values are part of the progressions that make a complete set of values for [3x+1]
    Remember I use brackets to denote cycle . I don’t know if anyone else does.

    So the common element concept is another thing you guys might look at and see if it helps. I’m sure I have some C code some place . I work with C Code to explore things so I have a program for everything rather than a paper with equations.

    Okay then.. If I can be of help..

    Ernst_Berg@Sbcglobal.net

  28. Someone says:

    Finally proven? Error found:

    [quote]Author’s note:
    The reasoning on p. 11, that “The set of all vertices (2n; l) in all levels will
    contain all even numbers 2n > 6 exactly once.” has turned out to be incomplete.
    Thus, the statement “that the Collatz conjecture is true” has to be withdrawn,
    at least temporarily.
    June 17, 2011[/quote]

  29. Someone says:

    I have been fascinated by the Collatz conjecture for years too. Here I have something which is a result of my search and I think that may be the answer to the questions posed by the author. Here’s the formula for the average (arithmetic mean) length of the Collatz the range from 1 to n. I think that the actual average length of the Collatz converge to this pattern, but I don’t have (yet) a formal proof of this. And I checked only n less than 1001… Example:

    C: 1,5x+0,5 if odd; x/2 if even

    Number 1 – stopping time: 0

    Number 2 – stopping time: 1

    Number 3 – stopping time: 5

    Number 4 – stopping time: 2

    = (0+1+2+5)/4 = 2

    My general formula:

    = 2/ln(0.75) * [n*(ln(1/n)+1)-1)]/n

    The best results we obtain for large n, example n=1000:

    = 39,89

    My general formula:

    = 41,08

  30. Rakesh K. Sharma says:

    I know you all are waiting for a proof for Collatz Conjecture, and your wait is coming to an end. I have solved this problem, however, last 3 days I spent in ER, so did not get time to type my proof.

    I have also sent my proofs for Fermat’s Last theorem and Catalan’s Conjecture for publication. My proofs will shock the number theory world that such a simple proofs did exist for these problems.

    All this work has been done in just last 2 months of time.

    I left math in 1992 when I was fed up with University Politics and started working for Industries. I had never even imagined that I will solve these problems with such an ease. Proofs presented by me have already been checked by math professors, who have found these proofs quite fascinating. Now I am just waiting to have these published before you all will get a chance to see these proofs.

    So just wait for few more months to see these proofs.

  31. Tony N says:

    Interesting – I can’t say I have ever seem this game before, but it appears simple enough. Basically it is just a function of how long it takes for the number to become a binary value, at which point it will collapse.

  32. Harry altoft says:

    Perhaps consider this

    Any odd number is squared and then one is taken away, any even number is divided by two, ill youll find it very interesting

  33. I was a control system engineer working with temperature, level, flow and pH control sytems. The Collatz algorithm looks more and more like these
    control systems which are 2nd ordered negative feedback control systems. Nonlinearity does get involved and some disturbance will cause unstable divergence. Behaviour of Collatz algorithm follws such patterns quite closely. Control systems were already in commercial use before 1937. I suspect Collatz translated these models into number theory. However not being a number theorist, I could only guess.
    HueYK

  34. Mikołajki says:

    keep up the superb work , I read few blog posts on this web site and I conceive that your weblog is very interesting and contains sets of great info .

  35. No real-world control system is as complicated as Collatz 3x+1. It is easy to control the absolute level of liquid but not the plus and minus fluctuation of micro-level. I don’t think there is an analytical proof for Collatz 3x+1. However I could be wrong since Wiles took 140 pages to prove FLT. A control engineer proposing a 140 pages solution in his control system would be sacked immediately. Here is my suggestion: Sandwich Collatz 3x+1 between Collatz 3x and 3x+2 and prove by mutual exclusion using even-integer/odd-integer ratio. It it is greater than unity, it is convergent. If its reciprocal ratio is almost close to zero, it is absolutely divergent. In between there is inaccessible gap unreachable by the three. Voila

  36. Corrections:

    If its even-integer/odd-integer ratio is almost close to zero, it is absolutely divergent. In between there is an inaccessible gap unreachable by the three. Voila!!!!!!!!!!!!!!!!!!!!!!!!

  37. Try my hybrid Collatz(3x+1/3x-2 Conjecture:
    for m from 10^70 thru 10^70 do print([g:1100,makelist( [x:m,y:makelist( if evenp(x) then x:1/2*(x) elseif x=1 then x:3*x-2 else x:3*x+1, k,1,g),sum(evenp(part(y,j)),j,1,g)],x,2^i,2^i)]);
    It takes 1325 steps to converge to 1111…. for initial x value = 10^70. Test my Maximaline on Online Maximala.
    Here is the end of the output:
    ,137194,68597,205792,102896,51448,25724,12862,6431,19294,9647,28942,14471,43414,21707,65122,32561,97684,48842,24421,73264,36632,18316,9158,4579
    ,13738,6869,20608,10304,5152,2576,1288,644,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,
    1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288
    ,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,
    160,80,40,20,10,5,16,8,4,2,1,1,1,1,1],71*false+154*true]]]

  38. Hello it’s me, I am also visiting this web page regularly,
    this website is in fact good and the visitors are in fact sharing fastidious thoughts.

  39. paleo diet says:

    What i don’t understood is if truth be told how you’re now
    not really a lot more well-liked than you might be right now.
    You’re so intelligent. You know therefore significantly with regards to this matter, produced
    me individually believe it from so many various angles.
    Its like women and men don’t seem to be fascinated unless
    it’s one thing to do with Lady gaga! Your personal stuffs excellent.
    At all times deal with it up!

    Feel free to surf to my web-site – paleo diet

Leave a Reply