Pick any integer you like. Got an integer? OK, now apply this simple rule: if the integer is even, divide by two; otherwise, multiply by three and add one. For example, if you started with 10, you would get 5; if you started with 13, you would get 40. Pretty simple, right? You can pretty much do it in your head for small numbers. (Actually, if you’re willing to concentrate you can probably do it in your head for big numbers too! Quick, what would you get if you start with 217?)
You might not think there’s anything very interesting to be said about this rule… but you would be wrong.
The fun starts when we consider iterating this rule. I’ve talked about iteration before: it just means repeating the rule. So, for example, if we start with 10, we get 5; applying the rule again to 5, we get 16; applying it to 16 gives 8, and so on. What happens if you keep going? Try it before reading on!
Continuing past 8, we get 4, 2, 1, 4, 2, 1, 4… obviously, once we reach 1, we’ll keep cycling through 1, 4, 2 forever: one more than thrice 1 is 4; half of 4 is 2; and half of 2 is 1 again. Hmm… let’s try some other starting numbers and see what happens. What about 3?
3, 10, 5, …
But of course we already know what happens after 5. Starting with 6 goes right to 3. How about starting with 7?
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, …
It takes a bit longer, but we eventually reach 1. The obvious question presents itself: will we always reach 1 when we iterate this rule, no matter what positive integer we start from? Is there some other loop we could get stuck in? Or is it even possible that there are some starting numbers from which the successive numbers will just keep getting bigger and bigger and never loop at all? If you think that last option isn’t possible, try starting with a number like 27:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 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…
Having reached as high as 1780, with no end in sight, we start to question whether we’ll ever get back to 1. Well, in this case, it turns out we do, eventually — after going as high as 9232 and repeating the rule 111 times! — but there are lots of other positive integers we still haven’t tried (infinitely many, in fact).
As you might have guessed from the title of this post, no one knows the answer! The Collatz conjecture (put forward by German mathematician Lothar Collatz in 1937) guesses that all starting numbers eventually do reach 1. This is true for all the starting numbers anyone has ever tried (computer programs have been used to try all the integers up to 
As a parting challenge for you, suppose we modified the rule so that if you have an odd number, you multiply by two and add one, instead of multiplying by three and adding one. Even numbers should still be divided by two. What can you say about iterating this new rule?
The Math Less Traveled 
Ah yes, one of the forms of “looping” covered in a book in my fourth-grade classroom. Another example was to count the number of letters in the spelled-out form of numbers, which turns monotonous with “four.”
Indeed! Although in contrast to the Collatz problem, it’s not too hard to prove that the counting-letters thing always reaches four from any starting number. (I’ll leave the proof as an exercise for any interested readers.)
So, of course, I started with 87 and I’ll easily admit that I had to use my calculator. I wasn’t counting, but I’d say it took 20 iterations maybe? I even guessed (correctly) where it was going to end up. Cool! I’m working on the proof now. Should have it in another few . . . .
“If you want to know how many steps it will take to reach 1 from a particular starting number, no one knows a better way to figure it out than just trying it.”
That was an asinine thing to say. Just because YOU don’t know doesn’t mean that no one knows.
import collatz_functions
e = 177149
mersenne = 2**e – 1
odds = 4.819 * e
evens = e + (odds – e) * 2
actual = collatz_functions.collatz(mersenne,0)
print evens, odds
print actual
print evens/actual[0],odds/actual[1]
print
fermat = 2**e + 1
odds = 2.410 * (e + 1)
evens = odds * 2
actual = collatz_functions.collatz(fermat,0)
print evens, odds
print actual
print evens/actual[0],odds/actual[1]
print
## output
##
## 1530213.062 853681.031
## [1531812, 854697]
## 0.998956178696 0.998811310909
##
## 853863.0 426931.5
## [859371, 430434]
## 0.993590661077 0.991862863993
@Mensanator: you know, a simple “actually, did you know that…” would have sufficed. If I’m ever wrong about something I’ll freely admit it. In this case, however, all you’ve done is demonstrate a way to approximate the number of steps for certain special classes of starting integers (Meresenne numbers, and Fermat numbers), which hardly contradicts my statement. It is interesting, though, and I’d love to know more about it if you wouldn’t mind posting an explanation or links.
Ok, I apologize, although I simply meant “silly”.
And sure, they’re only approximations, but one
could infer from your statement that nothing is
known, which is not the case. An approximation
always trumps ignorance.
And although I only gave a couple examples where
I have the constants memorized, there are plenty
of other examples.
The examples shown were of mono-stable binary
resonnance. There are also cases of bi-stable,
tri-stable and quadra-stable binary resonnance
(details of which I would have to look up in
my notes). All of these types have various
formulae for computing the length of the
resonnant portion, after which they behave
randomly (here random behaviour means they act
statistically indistinguishable from random
bit patterns). And, of course, there’s a formula
for calculating “random” behaviour.
A binary number will grow (via 3n+1) by at
least 1 bit or at most 2 bits if there’s a
propagating carry. In practice, this averages
to 1.585 (log 3 / log 2) and is the MSC (Most
Significant Constructor).
The LSD (Least Significant Destructor) removes
trailng 0 bits via n/2. Because the least
significant 0 bits of the integers have a
negative binomial, specifically, a geometric,
distribution, and the mean of a geometric
distribution is the inverse of the probability,
LSD will be approximately -2 for “random”
patterns.
Thus, with a mean MSC of 1.585 and a mean LSD
of -2, random patterns converge at the rate of
-0.415 bits per 3n+1 operation.
When there is a signicant amount of resonnance,
one has to calculate a MSD/LSD for that portion
(which may be net positive for Mersenne Numbers
or net negative for Fermat numbers) which
resonnates and add that ot the standard -0.415
rate (assuming one knows how many bits will be
present at the end of resonnance and that
resonnating patterns always become “random”).
That’s how those formulae and constants were
derived in my program.
Links:
http://members.aol.com/mensanator
The link
“True But Unproven: the Collatz Conjecture”
is a random assorment of unrelated pages (to be
consolidated someday). Be sure to check out
“Hailstone Patterns” for more on resonnance.
http://groups.google.com/group/TrueButUnproven
Is my Google Group. The post there “paper published”
will give you directions to my on-line paper
Blueprint for Failure:
How to Construct a Counterexample
to the Collatz Conjecture
And although I’ve only made minor contributions
to the Wikipedia, I am very active in the discussion
page (actually created by me) of the Collatz
Conjecture article.
After working on the conjecture for some 30 years, I reckon I have found a simple proof.
There are lots of papers on the subject. Who is prepared to take a serious look at yet another proof ? It is simple but not trivial.
“Is there some other loop we could get stuck in? Or is it even possible that there are some starting numbers from which the successive numbers will just keep getting bigger and bigger and never loop at all? If you think that last option isn’t possible, try starting with a number like 27:”
I am currently working on a proof for the Collatz conjecture, and can add a bit more insight into the above.
To answer the first question: is there some other loop than the 4,2,1,4 loop could we get stuck in? The answer is no, I have a solid proof of why there isn’t, but since it isn’t published I don’t want to give this away, but I can prove this 100% for sure(verified by several mathematicians at my university).
Will the numbers get bigger and bigger? This question I have been trying to disprove but have a hard time disproving the {infinity,…, k, …, infinity} sequence. This is the part I am currently working on, either disproving this, or proving the {infinity, … , k, … , 4, 2, 1, 4, … } sequence is the only one possible for any integer k, therefore proving the conjecture.
Any possible integer in the set of natural numbers will lead to a number in the following set {4, 10, 16, …, 6n + 4}, if you draw out the Collatz graph in mod 6( 0->0 until reaches odd number, if so 0->3->4, from 4 you have 3 cycles the 4->2->4 cycle, the 4->5->4 cycle, and the 4->2->1->4 cycle, so as you see if you start with any number eventually you will reach a 4 mod 6 integer. Every integer in the set {4, 10, 16, …, 6n + 4} has 2 possible prior integers either 1) you divided by 2, so any number from {8, 20, 32, …, 12n + 8} or 2) you multiplied by 3 and added 1, which means the second value is found in one of the 3 following sets {1, 7, 13, …, 6n + 1}, {3, 9, 15, …, 6n + 3}, {5, 11, 17, …, 6n + 5}. So this means the size of the set of integers in the k-1 position in the sequence will be 2x as large as the kth position in the sequence, and decreases in factors of 2 for each 4 mod 6 value we loop through during the sequence. The {infinity, …, k, …, infinity} sequence therefore cannot be possible since if you take the size of the set of all numbers at position k in this sequence, as s, then s would eventually decrease to a fractional number of a number between 0 and 1, and since s has to be an integer value, therefore the {infinity, …, k, …, infinity} sequence cannot exist.
This is my formal argument currently for that point, unfortunately you have problems if you take s to be infinity, and every s of position k would also be infinity, just less and less dense each time, so this is the only problem I can see with the argument I proposed above for this, any way around this?
The reason why 27 has a long sequence compared to it’s neighbours is because it is a 0 mod 3 value. All 0 mod 3 values will have a longer sequence than their neighbours, if you look at the inverse Collatz graph in mod 6, you will notice that 3 mod 6 -> 0 mod 6 loop infinitly part of the graph will act as a sink, meaning if you start at any other number, you will loop through the 1, 2, 4, 5 mod 6 values an unspecified number of times until you reach a 3 mod 6 value, then never be able to come back. So as you see in the inverse Collatz graph you will always reach the 3 mod 6 values last, and therefore these are the longest since if you keep branching outwards you will eventually reach this value and stay there, by the cycle/sink mathematics theories. In essense 3 mod 6 acts as a sink, and the sequence starting from {3, 6, … 3n + 3} must go through all other integers of 1, 2, 4, 5 mod 6 prior to entering the 4, 2, 1, 4 cycle, asssuming the conjecture is true.
As a note to the last argument, it sounds like I say that any sequence starting with {3, 6, …, 3n + 3} has to be longer than its neighbours, this isn’t true, but my argument was that they will have a tendancy of being a longer sequence because the set of sequences beginning with {3, 6, …, 3n + 3} must go through all other 1, 2, 4, 5 mod 6 sets of integers prior to entering the 4, 2, 1, 4 cycle. This is assuming the conjecture is true of course. Just thought I’d clarify that part.
To add onto my second argument for my proof of why numbers don’t get bigger and bigger meaning that that number would be part of a Collatz sequence of the form {infinity, …, k, …, infinity}, I am going to look at the only possibility for the existance of this sequence, and that is if all s of position k are infinite.
As a side note you may be wondering if s is finite and it reduces by half each time it cycles through a 4 mod 6 number, why doesn’t this defy my argument that if you keep reducing a finite number by half eventually it will not be an integer, and since it isn’t an integer and the size of a set must be an integer therefore any set cannot exist. See this is only true for sets without any cycles which the {infinity, …, k, …, infinity} sequence if it does exist must have no cycles, since in the first part of my proof I prove that the 4,2,1,4 cycles is the only one.
For the {infinity, …., k, …., 4, 4, 4} sequence if we only look at the sequence from the 4 mod 6 integers only, then we notice that s will get stuck at 1 because of the cycle and never reduce.
s of 2nd position = {10, 64}; s = 2
s of 1st position = {4}; s = 1
s of 0 to negative infinity position = {4}; s = 1
Note: and yes I know s doesn’t reduce by half because some branches end in 0 mod 3 and never return, but s must always decrease since there are an infinite number of 1 and 5 mod 6 numbers and I already took out all the 0 mod 3 branches from my former argument, so any level with these branches would be a void level, and not count towards the reduction of s, either way if you include them they would halt s or reduce it by a factor > 1/2. So you can exclude this possibility from the argument.
Now back to looking at the only hypothetical possibility for the existance of the {infinity, …, k, …, infinity} sequence, and that is if all s of all positions in it’s sequence are infinite.
Now this not only proves that if these types of sequences existed that they would hold an infinite number of distinct elements but that there would be an infinite number of seperate Collatz graphs of this form which would each be infinitely long with infinite number of distinct elements.
We can come to this conclusion, if we suppose that a sequence of the form {infinity, …, k, …, infinity} had a last position j. Remember for this type of sequence to be true s must be infinite for all positions in the sequence including this hypothetical last one. Since j is the last position in the sequence, we can conclude that the size s for that particular graph is 1, and therefore for s to be infinity there must be an infinite number of Collatz graphs, which each are infinitely long, and each infinitely longer than the {infinity, …, k, …, 4, 4, 4, …} graph for which we know exists.
So if we suppose each of these graphs of each of the 2 forms had equal representation among all positive integer numbers, then we can conclude that there would be infinitely many more integer values in a sequence of {infinity, …, k, …, infinity} form than the {infinity, …, k, …, 4, 4, 4, …} form, and since by empirical evidence every positive integer value that we are aware of is part of the {infinity, …, k, …, 4, 4, 4, …} sequence and have found 0 in the {infinity, …, k, …, infinity}. Then we can only conclude that the probability of the {infinity, …, k, …, infinity} type of Collatz sequence to exist if it exists to be infinitely close to 0%.
Therefore by this reasoning we can be infinitely close to 100% certain that the Collatz conjecture is true for all positive integer values.
As I said I need some help in either refining this part of my proof, or another method to verify that the Collatz is true 100% of the time, instead of infinitely close to 100% of the time, but at least this argument very very strongly suggests, that the numbers will not get bigger and bigger and never come back to the 4,2,1,4 loop which contains the integer 1.
Assuming the Collatz conjecture to be true, you can use the following relation to define what the highest possible value k of any position in the sequence between 0 and j to be < 4^j, the jth position being the position where k of j = 4. Also we only count 4 mod 6 values to count as k or j position values.
To Brent,
I am an activist reseacher, resident in Africa. Unfortunately (though this is par for the course here), I face great harassment and run the risk of deten tion.
I have solved the Collatz conjecture. And duly sent it to a reviewed journal. However the journal secretary has informed me, weeks after, it is yet undergoing review and the review may take months. Hence , considering the threats,I want to send the proof to a selection of those interested, so long as they acknowlege authorship, and willing to pay the cost of preparation and sending.Another prerequisite,imposed by the journal ,is to refrain from publication till the review is over: however you may dicscuss it,including online.
My proof is both lucid and brief ,it occupies about four pages.Also it is written in a style to be accesible to the nonspecialist.
I ask for a rapid reply.
Take care.
Hi Keav,
I have approved your comment on the offchance that you are genuine, however, you will forgive me for saying that this sounds rather like a scam, although a decidedly unusual one. I cannot imagine what ‘cost of preparation and sending’ there would be, and I am certainly not willing to send you any money, given that you could simply prepare your proof in a LaTeX document and send it as a PDF entirely for free. If you would like to do that and send me your proof I would take a look at it, at least out of curiosity. However I do find it rather improbable that you have actually solved the conjecture, although not impossible of course.
There seems to be no shortage of ‘proofs’, so here is mine.
I welcome any constructive criticism.
Mensanator has already seen it, but he read things into it that weren’t there. Thanking him anyway.
Hi Richard,
Thanks! You have some very interesting insights there. I like the way you have organized your explorations. Unfortunately, the one thing you have not shown is that every odd number eventually appears in some complete or incomplete sequence. You have shown very nicely how we can always work *backwards* from any number of the form 6n+1 or 6n+5 to find an (infinite list) of integers which can come before it in a Collatz sequence (i.e. after it in a reverse sequence), but that is not the same as showing that we can always go *forwards* to 1. We could extend all these sequences from 1 infinitely and yet still manage to miss some number which will never appear in any of the branches. If so, it is because the Collatz sequence starting from that number never reaches 1, but keeps increasing forever. Does that make sense?
I received some feedback indicating lack of clarity, so the paper has been revised for better notation, more detail and examples. If you get the latest version (sat aug 30), the conclusion will explain that ALL odd integers except 6n+3 have unique sets of predecessors, thus they will appear some sequence.
You missed the critical point: if a number never reached 1 it would have to loop, but that is impossible because no predecessor sets share common elements, i.e., disjoint sets.
Hi Richard,
It is not enough to say that all odd integers except 6n+3 have unique sets of predecessors. That is true, but it does not show that all odd integers will appear in some reverse sequence starting from 1. You could start with 1, choose all possible values for y2 (all unique), then all possible values for y3 (also all unique),… and continue forever, and there might be some number that you would never, ever encounter! In all the infinite possible, infinitely long reverse sequences starting from 1, there might actually be a number that never appears. (Infinity is weird like that.) You have not actually shown that this cannot happen.
Also, it is not true that a number would have to loop if it does not reach 1. You are correct that there are no other loops — in fact, I think this is well-known, having been proved by Conway and others — but the problem is that the sequence following some number could keep getting larger and larger without looping, and therefore never reach 1.
Richard,
I just thought of a different way to explain it, perhaps it will be more clear this way. Suppose I am building some reverse sequence. The fact that every odd number not of the form 6n+3 has a unique set of predecessors means that *once I reach* such an odd number, I can always extend the reverse sequence further with a unique set of predecessors. However, that says nothing about the “once I reach” part. If you pick any particular odd number, there is nothing in your proof that shows that I *must eventually reach* that particular number, i.e. that it can be found in the predecessor set of some other number which in turn must eventually be reached, and so on. Perhaps there is some odd number which is not in the predecessor set of ANY other odd number.
Thank you for the discussion of this subject.
Assume there exists an odd number z, that is not reached from 1.
Apply the hg(z) algorithm producing an odd integer w.
The integer w must be contained in one of the (1,5)mod 6 classes.
The paper demonstrates the construction of the S set for all members of these classes. One of those sets would contain z.
There can be no number missing.
quote:
“If you pick any particular odd number, there is nothing in your proof that shows that I *must eventually reach* that particular number,”
I think here, you are touching the issue of computablity of the problem, as in the Lagarius, Feinstein papers. It’s not so much, “I must”, but “I can”.
There can be no mathematical predictive formula for constructing a sequence, since each step is a free will choice. Any calculations can only be done after a sequence is selected. This excludes statistical methods, which are done after the fact.
Does this make sense?
Certainly, if you start with some number z, apply the hg algorithm to it producing w, and then contruct a predecessor set S for this w, z must be contained in it. That is clear. But this does not prove anything: you have just shifted the question of whether z is reachable from 1 onto the question of whether w is reachable from 1. z is reachable from 1 if and only if w is also. But if I didn’t believe that z must be reachable from 1, then there is no reason for me to believe that w is.
Thanks again for the challenges, it raises details I did not consider.
The flow chart was revised to show that the odd number loops until resolution.
1. The paper shows all numbers 1 mod 6 and 5 mod 6 are linked to 1,
so where are you getting this z which is not?
2. Forming the reverse sequence starting with 1, to some end term y, obviously decides the ascent from y to 1. From y up the tree cannot be determined, because it involves choices not made. Predicting continuously increasing values, or any other pattern, is undecidable. Its equivalent to randomness.
Hi Richard, in response to your points:
1. What I am saying is that the paper does *not* show this. I am saying that you have not shown that no such z can exist. I have no way of getting a particular value of z from which you can’t reach one (if I did, I’d be famous!), but you have not shown that such a z will never be found. (Neither has anyone else, of course! =)
2. I agree with the first sentence. I see what you are saying with the other two sentences, but I don’t see how it is relevant.
With respect, I would suggest that in order to make progress you should take a course in mathematical logic or problem-solving. You have some good ideas and good intuition, but they need to be put on a firmer basis of mathematical rigor.
I’ve been revising the paper for more clarity and details (0-7-2008), some in response to the type of questions you asked.
As far as finding an odd integer z not included, the equations show the predecessor sets exist for ALL odd integers except 6n+3, i.e., all predecessors have successors. Page 3 should help verify this point.
If you have any additional questions, after reviewing the latest paper, post them and I’ll reply.
When this was originally posted, it was for review only, and was not, and is still not presented as a proof. My mistake for not being specific.
Your comments have been very helpful, thanks.
So many people claim to have proved it…I’m not buying it. There’s always some reason they haven’t published it, or it hasn’t been accepted and whatnot.
did you know that there are infinity number of collatz problems related to 3N+1 problem? I have the proof. 3N+1 is just the beguining, it is like a point in a line that extends from negative infinity to positive infinity. also I found a way to demostrate why all the numbers end at one. also I want to say that the famous constant e is related. I already send my paper to my ex calculus teacher to see what he think. I am waiting for the replay. problably if my paper is not the proof that every body hope, I am sure that at least it will be a strong hypothesys. if you are interested in review my paper send me an email to martin_malagon@yahoo.com and I’ll send it so you can see that I am not lying.
Least-residue trees (sub-trees of the Collatz graph) have a lot of interesting properties. An article is at “http://home.graysoncable.com”.
Oops. It’s “http://home.graysoncable.com/dkcox”.
If anyone still reads this thread, and thinks they have a solution, they may (or may not) want to publish their solution on the Unsolved Problems web site. Just email me.
John Cook at the Endeavour Blog has a link to a paper claiming a solution:
http://www.johndcook.com/blog/2011/06/01/collatz-3n-1-conjecture-solved/
Pingback: The Collatz conjecture is safe (for now) | The Math Less Traveled
looking at m-cycles (learned from wikipedia)
A=2x+1 (any odd number)
(forgive my notation, I’m not a math guy.)
3(A) + 1 = 2^n(2^n'(…..(n^n””( A”” )))))
Where we start at some odd A, it can be expressed as a cycle of even-odd-even reductions.
but if 2^a(2^b(2^c))) = 2^(a+b+c), then
3(A)+1 = 2^z( A’ ) where z is some cludge of stuff I don’t care about. but I could make A’ the odd number “1”.
Wolfram alpha tells me the solution has a solution
x=(2^z-4)/6,
I figure I haven’t hit on anything interesting, but for any odd number, I can find a z that gets me there from 1.
lol, I realized an error, which makes all of the above nonsense.
lemme re-think what I wasn’t really thinking and get back to you.