One of the most notorious problems in elementary mathematics that remains unsolved is the Collatz conjecture, concerning the function defined by setting when is odd, and when is even. (Here, is understood to be the positive natural numbers .)

Conjecture 1 (Collatz conjecture)For any given natural number , the orbit passes through (i.e. for some ).

Open questions with this level of notoriety can lead to what Richard Lipton calls “mathematical diseases” (and what I termed an unhealthy amount of obsession on a single famous problem). (See also this xkcd comic regarding the Collatz conjecture.) As such, most practicing mathematicians tend to spend the majority of their time on more productive research areas that are only just beyond the range of current techniques. Nevertheless, it can still be diverting to spend a day or two each year on these sorts of questions, before returning to other matters; so I recently had a go at the problem. Needless to say, I didn’t solve the problem, but I have a better appreciation of why the conjecture is (a) plausible, and (b) unlikely be proven by current technology, and I thought I would share what I had found out here on this blog.

Let me begin with some very well known facts. If is odd, then is even, and so . Because of this, one could replace by the function , defined by when is odd, and when is even, and obtain an equivalent conjecture. Now we see that if one chooses “at random”, in the sense that it is odd with probability and even with probability , then increases by a factor of roughly half the time, and decreases it by a factor of half the time. Furthermore, if is uniformly distributed modulo , one easily verifies that is uniformly distributed modulo , and so should be roughly times as large as half the time, and roughly times as large as the other half of the time. Continuing this at a heuristic level, we expect generically that half the time, and the other half of the time. The logarithm of this orbit can then be modeled heuristically by a random walk with steps and occuring with equal probability. The expectation

is negative, and so (by the classic gambler’s ruin) we expect the orbit to decrease over the long term. This can be viewed as heuristic justification of the Collatz conjecture, at least in the “average case” scenario in which is chosen uniform at random (e.g. in some large interval ). (It also suggests that if one modifies the problem, e.g. by replacing to , then one can obtain orbits that tend to increase over time, and indeed numerically for this variant one sees orbits that appear to escape to infinity.) Unfortunately, one can only rigorously keep the orbit uniformly distributed modulo for time about or so; after that, the system is too complicated for naive methods to control at anything other than a heuristic level.

Remark 1One can obtain a rigorous analogue of the above arguments by extending from the integers to the -adics . This compact abelian group comes with a Haar probability measure, and one can verify that this measure is invariant with respect to ; with a bit more effort one can verify that it is ergodic. This suggests the introduction of ergodic theory methods. For instance, using the pointwise ergodic theorem, we see that if is a random-adicinteger, then almost surely the orbit will be even half the time and odd half the time asymptotically, thus supporting the above heuristics. Unfortunately, this does not directly tell us much about the dynamics on , as this is a measure zero subset of . More generally, unless a dynamical system is somehow “polynomial”, “nilpotent”, or “unipotent” in nature, the current state of ergodic theory is usually only able to say something meaningful aboutgenericorbits, but not aboutallorbits. For instance, the very simple system on the unit circle is well understood from ergodic theory (in particular, almost all orbits will be uniformly distributed), but the orbit of a specific point, e.g. , is still nearly impossible to understand (this particular problem being equivalent to the notorious unsolved question of whether the digits of are uniformly distributed).

The above heuristic argument only suggests decreasing orbits for *almost all* (though even this remains unproven, the state of the art is that the number of in that eventually go to is , a result of Krasikov and Lagarias). It leaves open the possibility of some very rare exceptional for which the orbit goes to infinity, or gets trapped in a periodic loop. Since the only loop that lies in is (for ) or (for ), we thus may isolate a weaker consequence of the Collatz conjecture:

Conjecture 2 (Weak Collatz conjecture)Suppose that is a natural number such that for some . Then is equal to , , or .

Of course, we may replace with (and delete ““) and obtain an equivalent conjecture.

This weaker version of the Collatz conjecture is also unproven. However, it was observed by Bohm and Sontacchi that this weak conjecture is equivalent to a divisibility problem involving powers of and :

Conjecture 3 (Reformulated weak Collatz conjecture)There does not exist and integerssuch that is a positive integer that is a proper divisor of

*Proof:* To see this, it is convenient to reformulate Conjecture 2 slightly. Define an equivalence relation on by declaring if for some integer , thus giving rise to the quotient space of equivalence classes (which can be placed, if one wishes, in one-to-one correspondence with the odd natural numbers). We can then define a function by declaring

for any , where is the largest power of that divides . It is easy to see that is well-defined (it is essentially the *Syracuse function*, after identifying with the odd natural numbers), and that periodic orbits of correspond to periodic orbits of or . Thus, Conjecture 2 is equivalent to the conjecture that is the only periodic orbit of .

Now suppose that Conjecture 2 failed, thus there exists such that for some . Without loss of generality we may take to be odd, then . It is easy to see that is the only fixed point of , and so . An easy induction using (2) shows that

where, for each , is the largest power of that divides

In particular, as is odd, . Using the recursion

we see from induction that divides , and thus :

Since , we have

for some integer . Since is divisible by , and is odd, we conclude ; if we rearrange the above equation as (1), then we obtain a counterexample to Conjecture 3.

Conversely, suppose that Conjecture 3 failed. Then we have , integers

and a natural number such that (1) holds. As , we see that the right-hand side of (1) is odd, so is odd also. If we then introduce the natural numbers by the formula (3), then an easy induction using (4) shows that

with the periodic convention for . As the are increasing in (even for ), we see that is the largest power of that divides the right-hand side of (5); as is odd, we conclude that is also the largest power of that divides . We conclude that

and thus is a periodic orbit of . Since is an odd number larger than , this contradicts Conjecture 3.

Call a *counterexample* a tuple that contradicts Conjecture 3, i.e. an integer and an increasing set of integers

such that (1) holds for some . We record a simple bound on such counterexamples, due to Terras and to Garner :

Lemma 5 (Exponent bounds)Let , and suppose that the Collatz conjecture is true for all . Let be a counterexample. Then

*Proof:* The first bound is immediate from the positivity of . To prove the second bound, observe from the proof of Proposition 4 that the counterexample will generate a counterexample to Conjecture 2, i.e. a non-trivial periodic orbit . As the conjecture is true for all , all terms in this orbit must be at least . An inspection of the proof of Proposition 4 reveals that this orbit consists of steps of the form , and steps of the form . As all terms are at least , the former steps can increase magnitude by a multiplicative factor of at most . As the orbit returns to where it started, we conclude that

whence the claim.

The Collatz conjecture has already been verified for many values of (up to at least , according to this web site). Inserting this into the above lemma, one can get lower bounds on . For instance, by methods such as this, it is known that any non-trivial periodic orbit has length at least , as shown in Garner’s paper (and this bound, which uses the much smaller value that was available in 1981, can surely be improved using the most recent computational bounds).

Now we can perform a heuristic count on the number of counterexamples. If we fix and , then , and from basic combinatorics we see that there are different ways to choose the remaining integers

to form a potential counterexample . As a crude heuristic, one expects that for a “random” such choice of integers, the expression (1) has a probability of holding for some integer . (Note that is not divisible by or , and so one does not expect the special structure of the right-hand side of (1) with respect to those moduli to be relevant. There will be some choices of where the right-hand side in (1) is too small to be divisible by , but using the estimates in Lemma 5, one expects this to occur very infrequently.) Thus, the total expected number of solutions for this choice of is

The heuristic number of solutions overall is then expected to be

where, in view of Lemma 5, one should restrict the double summation to the heuristic regime , with the approximation here accurate to many decimal places.

We need a lower bound on . Here, we will use Baker’s theorem (as discussed in this previous post), which among other things gives the lower bound

for some absolute constant . Meanwhile, Stirling’s formula (as discussed in this previous post) combined with the approximation gives

where is the *entropy function*

A brief computation shows that

and so (ignoring all subexponential terms)

which makes the series (6) convergent. (Actually, one does not need the full strength of Lemma 5 here; anything that kept well away from would suffice. In particular, one does not need an enormous value of ; even (say) would be more than sufficient to obtain the heuristic that there are finitely many counterexamples.) Heuristically applying the Borel-Cantelli lemma, we thus expect that there are only a finite number of counterexamples to the weak Collatz conjecture (and inserting a bound such as , one in fact expects it to be extremely likely that there are no counterexamples at all).

This, of course, is far short of any rigorous proof of Conjecture 2. In order to make rigorous progress on this conjecture, it seems that one would need to somehow exploit the structural properties of numbers of the form

In some very special cases, this can be done. For instance, suppose that one had with at most one exception (this is essentially what is called a *-cycle* by Steiner). Then (8) simplifies via the geometric series formula to a combination of just a bounded number of powers of and , rather than an unbounded number. In that case, one can start using tools from transcendence theory such as Baker’s theorem to obtain good results; for instance, in the above-referenced paper of Steiner, it was shown that -cycles cannot actually occur, and similar methods have been used to show that -cycles (in which there are at most exceptions to ) do not occur for any , as was shown by Simons and de Weger. However, for general increasing tuples of integers , there is no such representation by bounded numbers of powers, and it does not seem that methods from transcendence theory will be sufficient to control the expressions (8) to the extent that one can understand their divisibility properties by quantities such as .

Amusingly, there is a slight connection to Littlewood-Offord theory in additive combinatorics – the study of the random sums

generated by some elements of an additive group , or equivalently, the vertices of an -dimensional parallelepiped inside . Here, the relevant group is . The point is that if one fixes and (and hence ), and lets vary inside the simplex

then the set of all sums of the form (8) (viewed as an element of ) contains many large parallelepipeds. (Note, incidentally, that once one fixes , all the sums of the form (8) are distinct; because given (8) and , one can read off as the largest power of that divides (8), and then subtracting off one can then read off , and so forth.) This is because the simplex contains many large cubes. Indeed, if one picks a typical element of , then one expects (thanks to Lemma 5) that there there will be indices such that for , which allows one to adjust each of the independently by if desired and still remain inside . This gives a cube in of dimension , which then induces a parallelepiped of the same dimension in . A short computation shows that the generators of this parallelepiped consist of products of a power of and a power of , and in particular will be coprime to .

If the weak Collatz conjecture is true, then the set must avoid the residue class in . Let us suppose temporarily that we did not know about Baker’s theorem (and the associated bound (7)), so that could potentially be quite small. Then we would have a large parallelepiped inside a small cyclic group that did not cover all of , which would not be possible for small enough. Indeed, an easy induction shows that a -dimensional parallelepiped in , with all generators coprime to , has cardinality at least . This argument already shows the lower bound . In other words, we have

Proposition 6Suppose the weak Collatz conjecture is true. Then for any natural numbers with , one has .

This bound is very weak when compared against the unconditional bound (7). However, I know of no way to get a nontrivial separation property between powers of and powers of other than via transcendence theory methods. Thus, this result strongly suggests that any proof of the Collatz conjecture must either use existing results in transcendence theory, or else must contribute a new method to give non-trivial results in transcendence theory. (This already rules out a lot of possible approaches to solve the Collatz conjecture.)

By using more sophisticated tools in additive combinatorics, one can improve the above proposition (though it is still well short of the transcendence theory bound (7)):

Proposition 7Suppose the weak Collatz conjecture is true. Then for any natural numbers with , one has for some absolute constant .

*Proof:* (Informal sketch only) Suppose not, then we can find with of size . We form the set as before, which contains parallelepipeds in of large dimension that avoid . We can count the number of times occurs in one of these parallelepipeds by a standard Fourier-analytic computation involving Riesz products (see Chapter 7 of my book with Van Vu, or this recent preprint of Maples). Using this Fourier representation, the fact that this parallelepiped avoids (and the fact that ) forces the generators to be concentrated in a *Bohr set*, in that one can find a non-zero frequency such that of the generators lie in the set . However, one can choose the generators to essentially have the structure of a (generalised) geometric progression (up to scaling, it resembles something like for ranging over a generalised arithmetic progression, and a fixed irrational), and one can show that such progressions cannot be concentrated in Bohr sets (this is similar in spirit to the exponential sum estimates of Bourgain on approximate multiplicative subgroups of , though one can use more elementary methods here due to the very strong nature of the Bohr set concentration (being of the “ concentration” variety rather than the “ concentration”).). This furnishes the required contradiction.

Thus we see that any proposed proof of the Collatz conjecture must either use transcendence theory, or introduce new techniques that are powerful enough to create exponential separation between powers of and powers of .

Unfortunately, once one uses the transcendence theory bound (7), the size of the cyclic group becomes larger than the volume of any cube in , and Littlewood-Offord techniques are no longer of much use (they can be used to show that is highly equidistributed in , but this does not directly give any way to prevent from containing ).

One possible toy model problem for the (weak) Collatz conjecture is a conjecture of Erdos asserting that for , the base representation of contains at least one . (See this paper of Lagarias for some work on this conjecture and on related problems.) To put it another way, the conjecture asserts that there are no integer solutions to

with and . (When , of course, one has .) In this form we see a resemblance to Conjecture 3, but it looks like a simpler problem to attack (though one which is still a fair distance beyond what one can do with current technology). Note that one has a similar heuristic support for this conjecture as one does for Proposition 3; a number of magnitude has about base digits, so the heuristic probability that none of these digits are equal to is , which is absolutely summable.

## 190 comments

Comments feed for this article

25 August, 2011 at 10:33 am

Allen KnutsonI don’t have a reference, but I was told once (by Conway I think) that if you generalize the recursion to “fix a k, and for each residue class i mod k, apply an affine-linear map x |-> (x-i)/k”, then one can prove that most of those limiting-cycle problems are undecidable in ZFC. That doesn’t prove that Collatz is one of the undecidable ones, but why shouldn’t it be.

25 August, 2011 at 11:02 am

Terence TaoYes, this is a result of Conway from 1972 (link here). I guess I should have mentioned it in the main post. Note though that the examples of undecidable recursions of Conway’s type are (as far as I am aware) examples that tend to have an output larger than the input, whereas with the original Collatz recursion it is the other way around (after one normalises to ). This opens up a lot of time for the recursion to do some interesting computation (and in particular to encode a problem known to be undecidable, e.g. solving an arbitrary Diophantine equation). In contrast, the original Collatz recursion, when starting with a large integer n, should only last about iterations before collapsing to the 1-2-4 cycle, and it doesn’t seem like there is enough time to do any undecidably complicated mathematics in the interim. Of course, this is not a rigorous proof of anything…

25 August, 2011 at 12:27 pm

Fred LunnonTypos —

Conjecture 3 should read

“There do not exist $k \ge 1$ and integers … such that … ”

“non-trivial periodic orbit has length at least {105,000}”

prints space after the comma — maybe {$105,000$} ? (twice)

Para. previous to equn. (6) — {q} undefined — see equn. (7).

For “counterexmaples” read “counterexamples”

(plenty of the former around for CAS users …)

Para. after equn. (8) —

For “parallelopiped” read “parallelepiped”

(and several times later — I agree it’s strange!).

Something wrong in next paragraph — maybe

“count number of times {S} contains {0}” ??

[Corrected, thanks – T.]25 August, 2011 at 3:45 pm

AnonymousConjecture 3: it would make more sense to me if you re-indexed to a_0,…,a_k and then set n>1. As it is stated now, n = 1 is actually the trivial cycle with k=1, a_1 = 0 and a_2 =2 (note the empty sum), because 1 divides 1 right? See equation (7.3) in Crandall’s paper.

http://www.ams.org/journals/mcom/1978-32-144/S0025-5718-1978-0480321-3/S0025-5718-1978-0480321-3.pdf

[Oops, you’re right, n should be strictly greater than 1 rather than greater than or equal to 1. I’ll keep the a indexing currently because I don’t want to inadvertently create other typos while trying to re-index. -T]25 August, 2011 at 5:49 pm

AnonymousMore on Conjecture 3: when talking of periodic orbits, loops or cycles, it helps to state, for the sake of the lay reader, that the value a_{k+1} is the number of evens and the value k is the number of odds (not double counting n) in such a non-trivial cycle, should one exist.

If you really are interested in equation (8), I have a draft paper under consideration with a peer-reviewed journal which aims to get an explicit description of equation (8) when it is part of a representation of a value for which the conjecture holds,i.e., I got em all. Perhaps, it would give you something to exploit. I actually need help finishing the key proof, but I do have all of the pieces in place. Please ,let me know if you are interested via comment. There is some clumsy stuff in the draft, but it’s not bad.

26 August, 2011 at 4:25 am

AnonymousI see you made mention of my suggestion about what a_k+1 and k mean later on in the proof of Lemma 5, but it might be better to mention it sooner for boneheads like me.

To be clear, by “explicit desc. of equation (8)” I meant a partition of the a_k such that one knows what choices of a_k correspond with a value m (for which the conjecture holds), where m is congruent to 3(mod 4), 1(mod 8), 5(mod 8), and 13(mod 8). Here m = (2^{a_k+1} – n) / 3^k. Of course, I have not solved the conjecture. But the lightbulbs went off this morning in my head when thinking about the Erdos conjecture you mentioned. I had never heard of it. In layman terms, the last odd term in a non-trivial cycle would be a power of 2 times the starting value n. So now I’m wondering if my partitioning scheme would be of any help. I’ll poke around with it this weekend.

26 August, 2011 at 4:30 am

AnonymousI abused n, by my first use of n I meant the sum in equation (8). By the 2nd use, I meant the root of a non-trivial cycle, should one exist. Good grief…

25 August, 2011 at 10:01 pm

Marcus HutterThought from an amateur:

One can break up the Collatz conjecture into

(i) The sequence f^1(n), f^2(n), f^3(n), … never diverges (i.e. always reaches a limit cycle)

(ii) 1,2,4 is the only limit-cycle of f (i.e. if the sequence does not diverge, then it ends in limit-cycle 1,2,4)

Your interesting Proposition 6 indicates that (ii) is hard to prove, but it does not indicate that (i) is hard.

As far as I remember, there are many Collatz-like functions f that satisfy (i)

but that have more than one limit cycle.

This makes (ii) for me less interesting, since it appears coincidental.

It would be nice to be able to also “show” “hardness” of (i) or prove (i).

25 August, 2011 at 10:40 pm

Farah Herbalits so difficult… how to start… :(

26 August, 2011 at 7:18 am

tomer shalevHello Terrence. a very nice webtalk. there was a time that this problem amused me when I was looking for a break from my current thesis.

It is worth mentioning the fundamental work of Terra on the subject regarding

the stopping time of a sequence, which if proved to be finite for all numbers, then simple induction can prove the whole conjecture.

Terras proved that almost all numbers have a finite stopping time.

Ivan Korec gave another tighter version of terras theorem.

If I’m not mistaken, Erdos was cited saying that this problem is beyond math’s

reach. I guess it is not that different from Goldbach’s and other out of reach and dangerous problems to explore when one is at a stage where productivity

is an important goal.

I regard this problem as a true math gem, I also was arguing with a friend about how should “real” mathematics look and sound like. I refereed him to

one of Erdos’ papers. my friend said that the paper looks like homework in

graduate Calculus. but then he didn’t stop saying that everything about Erdos’

observations are mind changing. Who knows, maybe Collatz’s conjecture has

a messy Erdos’s proof which is not as deep as much as it is cleverly constructed.

26 August, 2011 at 4:33 pm

Terry A. davisMaybe, you’d like the “magic pairs” problem. Let SumFact(n) be the sum of factors.

Find all n1,n2 in a range such that

SumFact(n1)-1-n1=n2

and

SumFact(n2)-1-n2=n1

http://www.losethos.com/code/MagicPairs.html

26 August, 2011 at 5:18 pm

Jonathan DHas anyone tried to prove this conjecture using an iterative proof?

For example: It would seem that you can show that (as initial conditions) by starting with 4 as a known “true” value, and then testing n=5, you can show manually that the conjecture is true for 5. Then repeating with true values for all the members in the set {1->5}, when you test n=6, you don’t need to show the conjecture reaches 4,2,1 you just have to show that somewhere in the sequence for 6 it reaches 5 or less. Then you can simply iterate test 7 with {1-6} as true, test 8 with {1-7} as true… onward.

Given some high value for n, for which we’ve already and checked all values less than n, [[you could start the proof at 1,000,000, and then for all values greater than 1,000,001]] – you have to prove that at some point in the sequence evolution the values hit a result less than n => you don’t need to prove it all the way back to 4,2,1.

But it gets even easier – every even value in this method is already proven true – the first step in the sequence for n rolls it below n-1, so even values for n are automatically true.

For the odd values, you have to look at the prime factors of 3n+1, and here we can could use a sieve method. All you need it some number in the sequence were the prime factors (removing all the 2 values) multiply to some number less than n. It was at this point I couldn’t really take it any farther, but could see that as n increases, there are more prime factors below it, and eventually, the sequence will hit some 2**j {factors} where factors are less than n.

Perhaps there is a way to prove that that for odd n above a certain size, the series will reach (must reach) a point less than n /before/ it reaches a cycle. I also don’t have the math to prove that.

-JD

26 August, 2011 at 5:27 pm

Jonathan Dthis was how far I got looking at the inductive proof

http://pastebin.ca/raw/2078636

just scrabbled together code

-JD

26 August, 2011 at 6:57 pm

Jonathan Dhere is a much cleaner copy of the code, with references and explanation

http://pastebin.ca/raw/2078648

there are several really interesting patterns that emerge

26 August, 2011 at 10:45 pm

Jon WI notice you spend more time on the weaker version than the actual conjecture. Is that just because you make better headway there?

22 September, 2011 at 12:46 pm

AnonymousI suggest a 10% rule is in order here. All peer-reviewed journals should immediately reject any purported proof of the 3x 1 Problem not properly referencing at least 10% of the literature, regardless of the authorship.

23 September, 2011 at 5:48 am

AnonymousYou’ll have better luck with the Diophantine properties of the “proxies” of local minima (those having the smallest absolute value) in 3n+c cycles than Bohm and Sontacchi’s formula; these are the ideals of the 3n+c problem. An “attachment point” in a cycle is an even integer i such that 3 divides i-c (and (i-c)/3 is not already in the cycle). An attachment point i is “primary” if 4i is not an attachment point. Extending the 3n+c sequence backwards from primary attachment points (taking the path (i-c)/3 and [not 2i] at nodes) gives an odd integer divisible by 3, the proxy of the local minimum immediately after the previous primary attachment point. For cycles with only one attachment point, the previous primary attachment point is the primary attachment point. For example, the proxy of -17 in the c=1 cycle of {-34,-17,-50,-25,-74,-37,-110,-55,-164,-82,-41,-122,-61,-182,-91,-272,-136,-68} is -21 (the primary attachment point is -68). These extended sequences have many interesting properties.

25 September, 2011 at 6:00 am

AnonymousErdos called such diophantine equations unconventional, hmm. In 1978 money cow VanHalen hit the music scene. Critics called the finger tapping solo style guitar playing unconventional. Now the adjective is toy model. Looks like the snobs are still in the lead in mathematics! Solving such exponential equations includes an adhoc grab bag of tricks, try surveying those before wimping out. No wonder amateurs love this problem, they want to find the cool trick. The pros avoid such lowly styles, and the ones who don’t say words like trajectory rather than sequence to make their work sound cool.

26 September, 2011 at 4:16 am

AnonymousOpinion 111 of Doron Zeilberger says it all, please see there the following quote in context,

“”Almost” proving something is often a piece of cake (for example that almost all x wind up at 1 after iterating the 3x+1 map).”

I like Zeilberger, he tells it like it is. Most of the work on this 3x+1 Problem is absolutely worthless but fashionable at the time of creation, so it sees publication in prestigious journals. What a joke.

26 September, 2011 at 8:13 am

Terence TaoActually, that precise statement (almost all x wind up at 1 after iterating the 3x+1 map) remains open; the best result currently known in this direction, as noted in the post, is that of the numbers less than N tend to 1, a result of Krasikov and Lagarias. Getting a density 1 set of numbers tending to zero would, in my opinion, be quite a significant achievement, even if it still falls well short of the full conjecture. (Perhaps Zeilberger was thinking of the weaker result that almost all x end up at some point at an integer less than x, which is indeed an easy result by modern ergodic theory methods, and was already noted in the first few papers on this problem, but which is nowhere near strong enough to push almost all numbers to 1.)

Ultimately, the precise problems solved are not what is the most important here, but what types of new technology and insights are developed, and a better sense of which obstructions are more substantial than others, and what types of tools are suited for each such obstruction. For instance, the accidental discovery of some sporadic cycle of length in the millions would, technically, resolve the Collatz conjecture, but for rather “uninteresting” reasons, for (unless there was some insight provided by the way the cycle was found) we have not learned anything broader about how to control an exponentially unstable recursion for an extended period of time, how to control the interaction between powers of small exponents such as 2 and 3, what fields of mathematics might be connected by posing these sorts of questions, etc. I recommend Thurston’s “On proof and progress in mathematics” for a great discussion as to why theorems (or “theorem-credits”, as he puts them) are the way we keep “score” in mathematics, but why

insightsare the real objective.1 May, 2012 at 4:30 am

Anonymous[Unsubstantiated anonymous allegation deleted. -T.]26 September, 2011 at 9:08 am

AnonymousNow you are talking semantics, “almost all” is a fuzzy statement and infinity is infinity, loosly speaking :-), so your assignment of significant achievement status is rather relative. Your point is well taken though.

I think a less objectionable conclusion to your article would be that the solution to the 3x+1 Problem ought to offer a means to solve an entire class of exponential Diophantine equations. Saying some equation is a “Toy model” is a derogatory statement, and a sequence is a sequence, not a trajectory – see Knuth’s comments on putting useless jargon into the literature.

26 September, 2011 at 9:17 am

Terence TaoThere are indeed a number of ways to formalise the concept of “almost all” in mathematics, but in number theory it is almost always (ha!) understood in the sense of density.

The concept of a toy model is also standard usage in both mathematics and physics, and is not intended as a derogatory term. (For instance, I have worked for many years on the Korteweg-de Vries equation, which is often called a toy model for more sophisticated (but less tractable to analyse) dispersive and water wave PDE.) See also the post http://mathoverflow.net/questions/1354/what-are-examples-of-good-toy-models-in-mathematics

I did not use the term “trajectory” in my post.

26 September, 2011 at 9:34 am

AnonymousScore card:

1. On “almost all” – you win.

2. On “toy model” – just because the apparent norm is to do so, doesn’t make it OK. Thoughts?

3. On “tracjectory” – I know, and you seem to agree … mute point.

26 September, 2011 at 9:39 am

Terence TaoThere are certainly circumstances in which it would be desirable to refer to a sequence as a trajectory, if one wished to emphasise the dynamical systems features of that sequence, and to emphasise the interpretation of the index parameter as a time variable. In this particular post, though, the dynamical systems aspects of Collatz sequences, while present, were not the primary feature I wished to emphasise, and so I did not use the terminology of trajectories (or orbits, although the latter term often suggests time-reversibility, which is not a feature of the Collatz iteration). See also my post on selection of good notation for more discussion of when a given mathematical notation is appropriate for a given situation, and when it is not.

Regarding any normative connotations that one may impute to terms such as “toy model”, I think you may be reading too much into this term, which is used in a specialised technical sense rather than as a colloquial one. A “conservative vector field“, for instance, is not a vector field with right-wing tendencies, “natural transformations” are no more eco-friendly than any other type of transformation, a “simple group” is no less worthy of respect than any other group (such as, say, a perfect group), and a “toy model” is no more childish than any other type of model; it is simply a model that is worth toying with, nothing more.

26 September, 2011 at 11:10 am

AnonymousI think we agree on (3), as I have seen the term used far too loosly: as if pushing the latest fashionable approach in a subtle way. I cannot cave on (2). It is a non-value add description, and can be offensive to some (the minority) and abused by those wanting to push the importance of their focus above those of others. It’s really no different than kids teasing each other with nicknames. So if by specialised you mean insidious, then I might concede.

Suppose somebody solves that conjecture of Erdos 10 years from now and submits a paper (using some trick offering no new insights) to a prestigious journal. Then a rejection letter arrives to the author saying something broiler plate like: Because competition is fierce, and though your proof of this “toy model” is valid, we must reject your paper as it offers no new insights. The same journal then goes on to publish a proof of positive density 1 (at a later time) offering no new insights either. I’m just saying…

30 September, 2011 at 11:03 am

AnonymousThere are some empirical results on a new way to tackle Simons and de Weger’s Lemma 14 at http://home.graysoncable.com/dkcox/.

28 March, 2017 at 6:37 am

Ing. Kontra MiklosHi Terence, I would like to know if there is anyway to get in touch with you to show the graph and the teory behind the graph tahat shows that for all positive number the conjecture is true, thank s in advance for your time.

28 September, 2011 at 10:32 pm

human mathematicsI’m sure someone has computed a large number of $(k,n)$ pairs. Do you know roughly for how many $n$ this has been done?

28 September, 2011 at 10:38 pm

human mathematicsThis blog post http://jpcameron.com/blog/?p=47 has some interesting pictures of the patterns in k for the first billion n. Visually appealing.

28 September, 2011 at 10:50 pm

human mathematicsYour method of assuming that “half the time” n is even and half the time odd got me thinking about “autocorrelation” of Collatz sequences. There are certain numbers, like 32, which if f_0 reaches them, will instantiate a long path “straight” down to 1. Of course these numbers are the powers of 2. So what if you think about the n as products of primes? Thinking that way you can “jump ahead” whenever 2^x is included in the number’s prime decomposition 2^x 3^y 5^z 7^w …. You can “jump ahead” in the sequence to just 3^y 5^z 7^w. Considered this way the conjecture is saying that (3n+1, scrape 2^powers, 3n+1, scrape 2^powers, 3n+1, … ) will eventually find a number whose prime decomposition is only 2’s.

28 September, 2011 at 10:52 pm

human mathematicsSorry, maybe that is just a longer way of saying what you said about 2-adic’s and ergodicity.

1 October, 2011 at 9:44 am

aks prime test amateur bojan vasiljevicMy view of The Collatz conjecture is next:

First key statement:

Numbers that are result of odd numbers and factor 3 are of digit value 3 or 6 or 9.

So plus 1 gives us numbers of digit value 1 or 4 or 7 (interestlingly only even numbers)

Second key:

Doubling seguence numbers (1,2,4,8,16,32,64,128,256,512,…) are of digit value 1 or 2 or 4 or 8 or 7 or 5; and are the only numbers that will get us to number 1 when dividing with 2.

So conclusion is that function for odd numbers tries to push number in doubling sequence area because there is the only posible way to find such number that leads to ending result 1. Also it ensures more even numbers than odd numbers in whole process.

3 October, 2011 at 8:00 pm

amateur bojan vasiljevicI was playing on the next Collatz conjecture applet

http://www.staff.science.uu.nl/~beuke106/collatz/bigCollatz.html

And I have realized that everything that i siad above is valid also for odd number function 3*n – 1

But 3*n -1 doesnt end on number 1 at the end always!(use applet).

So i started to play with both functions 3*n -1 and 3*n +1 for odd numbers with the help of the next picture.

http://t1.gstatic.com/images?q=tbn:ANd9GcQ-E2yQmH3qf2aXYK3lKsCQEqB3p6wYJmEF6QKFprNxSSOD0Wvc

treat this numbers around the circle as digit values( for all natural numbers)

And I have acknowleged that with the 3*n +1 you always end up on 1 for every odd number or even one eventually.

With 3*n – 1 is is not such a case.

5 October, 2011 at 4:01 am

AnonymousIn the first paragraph, you can remove the word positive as the naturals are positive by definition.

21 March, 2017 at 2:41 pm

Wade A. MoselyThe need for the word “positive” in this case depends upon the reader. Some include zero in the set of Natural Numbers and some do not. For set theorists, the inclusion of zero seems to be the convention. See https://plato.stanford.edu/entries/set-theory/

Some even include negative integers as members of the set of Natural Numbers. (Egad!)

Anyway, the inclusion of the single word “positive” to ensure a lack of ambiguity seems harmless and actually quite constructive, in my opinion.

5 October, 2011 at 5:53 am

AnonymousOperators act instantaneously, such as the limit operator. Thus we think of the limit at infinity, even though the word approaches appears in the definition. To this end saying things like WHEN n is odd or Passes through is silly. Just say if or for, and for the later: has.

The problem with using any is that the reader or student can often find multiple meanings for its usage. So in the statement of conjecture 1 I would replace any given with every. What is orbit again?

6 October, 2011 at 3:04 am

amateur bojan vasiljevicLet me also say that that almost all primes (exception is prime number 3) is in range of digit value 1 or 2 or 4 or 8 or 7 or 5.

So Collatz conjecture algorithm pushes odd numbers connected to primes by some factor inside doubling sequence area so that they become divisible by 2.

6 October, 2011 at 4:01 am

amateur bojan vasiljevicwith the help of 3*n+1 function

12 October, 2011 at 7:15 am

AnonymousReducing the set of integers to density 0 for which one must check is the conjecture is true is conceptually the same as showing the conjecture holds for almost all of them. So the result of Korec and Znam is state of the art, in my opinion.

13 October, 2011 at 3:26 pm

Terence TaoActually, there is a major formal (and conceptual) difference between a reduction to a small set of cases, and the verification of all but a small set of cases: before the conjecture is proven in full, the former situation yields no unconditional cases of the conjecture, whereas the latter situation yields plenty of unconditional cases of the conjecture. So, as a measure of partial progress, the latter is far more satisfactory than the former.

A good example is provided by Fermat’s last theorem: for every , there are no solutions to in the positive integers. It is a trivial matter to observe that to prove Fermat’s last theorem for all , it suffices to verify it for the odd primes and for (just because Fermat’s last theorem for an exponent automatically implies Fermat’s last theorem for all multiples of .) This observation already reduces the exponents that one needs to verify to a density 0 set; however, this is considered a trivial reduction that only comprises a very tiny portion of the full proof. In contrast, the much stronger assertion that Fermat’s last theorem holds for almost every n is a much more difficult and significant statement, which I believe was in fact not even established by the time of the Wiles-Taylor proof of the theorem.

25 November, 2011 at 4:57 pm

Kevin FordMinor correction: FLT for almost all n follows quickly from Faltings’ theorem, as shown in a short note by Heath-Brown in 1985 (Bull. London Math Soc, vol 17, p. 15-16).

28 March, 2017 at 6:30 am

Ing. Kontra MiklosHi Terence, I was looking at the work of Conway and I would say that his work is very good but he is missing a few branches in his work, i mail him but it seem s that he is very hill, but a familiar told me that he woulld like to see my work, I ve been working for almost for 4 years on a similar work that did Conway and I found a proof od Collatz Conjecture it is really true for every positive number, my proof is based on a graph, and looking at the final graph I would say that the hungarian mathematician Paul Erdoss was true that mathematics are not ready for this kinf of things, I know that i am not a mathematicain but an electronic engineer and i know of my limitation, i m presenting my work at the university of Matanza in Argentina as a thesis, in the graph that i found it can t be seen in some branches that there is no way to show by any means of series the conjecture of Collatz.

13 October, 2011 at 6:00 pm

AnonymousWhy would reduction to a set of density 0 have to yield a remaining set of conditional cases? Why not one abstract case? A method of proof is unknown at present.

14 October, 2011 at 5:05 am

amateur bvWho ever wants to solve Collatz conjecture must also prove that no natural number in a sequence doesnt repeat its self.

24 November, 2011 at 8:43 pm

Collatz Conjecture « Guzman's Mathematics Weblog[…] Terry Tao on the Collatz Conjecture Share this:TwitterFacebookLike this:LikeBe the first to like this post. […]

4 January, 2012 at 2:26 pm

d005I’ve recently caught this particular mathematical disease, and I’m having a hard time finding someone to point me in the direction I’m interested. It seems to me that if you go from the assumptions that:

a. All numbers eventually become odd or 1,

b. all numbers which are not even or 1 can be represented as 2b+1,

c. every step in the conjecture must remain whole,

d. a number may never have factors larger than it is, and

e. the conjecture is described by (3x+1)/2 and x/2

Eventually the process must come to an ‘end’ given any integer input, because the ‘b’ term requires an increasingly complicated and large set of input factors to go through a series of processes that make the remainder caused by division progressively more complicated.

Noone will help me, and I’m curious why I can’t find literature or get an easy answer. It seems a simplistic argument.

Dylan.

17 September, 2012 at 6:58 am

Marie GaudinHello, my father has done a very hard work on this theme. He is looking for someone to read and appreciate his work (in french).Marie

7 February, 2012 at 2:53 pm

Anonymousabout the toy model problem for the (weak) Collatz conjecture:

a1 = 0 < a2 < … < ak ?

23 February, 2012 at 5:52 pm

strange nicknametomer shalev wrote:

“Terras proved that almost all numbers have a finite stopping time.”

I have a question. How he did it? Is it a rigorous proof or just random-probabalistic proof (based on uncertain propositions)?

I ask, because I found some quite simple proof (but still has about 10 pages) that almost all numbers shouldn’t has a divergent trajectory. What’s more we can prove this way that, for example in 5x+1 problem almost all numbers has a divergent trajectory.

I ask you that also, because I read some publications of Jeffrey’s Lagarias and I was thinking why he do that many “random tests” of collatz conjecture (wchich has proved for example that almost all positive integers has a finite stopping time) while it is known since Terras has been proven it…

29 February, 2012 at 1:34 pm

AnonymousHaving a proof that there exists a divergent trajectory for the 5x+1 problem is a new result(i think). Have you shown your proof to anyone?

29 April, 2012 at 4:50 am

AnonymousTerras’ proof is not rigorous, and I think it is flawed in a way similar to Everett’ proof of the same result. Everett’ proof is flawed towards the end. Cranks with Phds… Sorry if the truth seems rude… We all make mistakes, but passing off trash as something great for decades on end, like certain other results, shows a lack of Academic honesty, and a waste of student tuition ultimately.

25 February, 2012 at 7:21 am

strange nicknameAnonymous wrote:

“Most of the work on this 3x+1 Problem is absolutely worthless but fashionable at the time of creation, so it sees publication in prestigious journals.”

1. I think it’s good to explain some things even if they are obvious. If someone will do this, all the rest of mathematicians doesn’t need to explain it all over and over again, they can only cite the source.

2. Even if someone wrote obvious publication, this publication can induce the others to valuable thoughts. What’s more “obvious” things aren’t always obvious for all, sometimes it’s subjective issue.

26 February, 2012 at 10:53 am

StudentTernce Tao wrote:

“The above heuristic argument only suggests decreasing orbits for almost all n”

For some time I have an explanation and proof of why this heuristic argument works (we can prove that the Collatz sequence performs Bernoulli process, such that p = 0.5), but I’m just a student and I have no way to publication this (I do not even know where I should try to do it). I even have trouble to find someone who assess the reliability and validity of this proof, because mathematicians who are familiar in this area is relatively not much.

Ternce Tao wrote:

“though even this remains unproven, the state of the art is that the number of n in {1,…,N} that eventually go to 1 is >> N^0.84, a result of Krasikov and Lagarias”

Can be proved that if N goes to infinity then the number of n that eventually go to 1 is N^c and c=sqrt(3)/2.

By the way I’ll show you an equivalent version of the weak Collatz conjecture (I don’t know if it is known to mathematicians):

Let’s some geometric series. Suppose we have two sequences (n = 0,1,2,3, …):

c_ {n} = 1.5^{n}

and a sequence which is defined in such way that we take any vector

consisting of any natural numbers with zero:

[a_ {1}, a_ {2}, …, a_ {k}]

and create on its basis the sequence of vectors assuming a constant r:

[a_{1}+r, a_{2}+r, …, a_{k}+r]

[a_{1}+2r, a_{2}+2r, …, a_{k}+2r]

[a_{1}+3r, a_{2}+3r, …, a_{k}+3r]

…

[a_{1}+p*r, a_{2}+p*r, …, a_{k}+ p*r]

Our second sequence will be as follows:

2^{a_{1}}, 2^{a_{2}}, … , 2^{a_{k}}, 2^{a_{1}+r}, 2^{a_{2}+r}, … ,

2^{a_{k}+r}, 2^{a_{1}+2r}, …

Now create an infinite number of consecutive terms of taking quotients

these two sequences:

SUM = {1,5^{0}}/{2^{a_{1}}} + {1,5^{1}}/{2^{a_{2}}} + … + {1,5^{n}}/

{2^{a_{k}}} + {1,5^{n+1}}/{2^{a_{1}+r}} + {1,5^{n+2}}/{2^{a_{2}+r}}

+ … + {1,5^{2n}}/{2^{a_{k}+r}} + …

Question: Is there a finite amount of natural numbers which

such series can be convergent? Are the only solutions are 1 and 2?

All indications are that there are only two natural numbers which

such series can be convergent. Whatever the sequence of vectors

themselves and what we assume a constant r. Here are that series:

vector:

[1]

r = 1

(1,5^(0))/(2^(1)) + (1,5^(1))/(2^(1+1)) + (1,5^(2))/(2^(1+2*1)) + …

= SUM_(n=0)^(infty) (1,5^(n))/(2^(n+1)) = 2

and

vector:

[2]

r = 1

(1,5^(0))/(2^(2)) + (1,5^(1))/(2^(2+1)) + (1,5^(2))/(2^(2+2*1)) + …

= SUM_(n=0)^(infty) (1,5^(n))/(2^(n+2)) = 1

Can be shown that if these are the only natural numbers to

which such series can be convergent, the only cycle in the

Collatz sequences is a trivial cycle, and conversely, if for some

vector and the constant r series can converge to some other natural numbers, there are non-trivial cycles in Collatz sequences.

After a moment’s thought is easy to find the criteria for convergence of such series. You can also bring the problem to the following issues:

– for which r exists a k and k – elements sequence of natural numbers for which this expression takes the value of natural:

(2^(r+k))/(2^(r+k)-3^k) * [1/2^a_{1} + 1,5^1/2^a_{2} + 1,5^2/2^a_{3} +… + 1,5^(k-1)/2^a_{k}]

30 April, 2012 at 10:24 am

AnonymousWow, since when did non-rigorous heuristics suggest anything meaningful?

Maybe it’s because many of todays grad students write very few rigorous proofs. Now these sort just memorize and reproduce sketchs to earn a degree and then go with the flow.

26 February, 2012 at 2:05 pm

StudentI wrote:

“Can be proved that if N goes to infinity then the number of n that eventually go to 1 is N^c and c=sqrt(3)/2.”

I’m sorry, I made a little mistake. If can be proved that Collatz sequence performs Bernoulli process, then it suggests that almost all n collatz ssequnces are converge.

I mean, it can be proved that almost all numbers in trajectories converge as if they were multiplied by sqrt(3)/2 or faster and it has no connection with the results of Lagarias and Krasikov.

27 February, 2012 at 9:28 am

Joseph SinyorAt the risk of being self-serving, I suggest that one possible key to understanding the pattern behind the 3x+1 conjecture is related to the Mersenne numbers (2^k-1). See my 2010 paper published in the International Journal of Mathematics & Mathematical Sciences: “The 3x+1 Problem as a String Rewriting System”:

http://www.hindawi.com/journals/ijmms/2010/458563.html

Joseph Sinyor

18 April, 2012 at 9:19 am

AnonymousI have seen a rigorous proof using curves that the ones-ratio approaches zero as the number of odds increases for sequenes containing the trivial cycle.

One can split the sequences for the set 2^k – 1 in half and see that the first half of each seaquence has a ratio above a bound, where the number of odds is unbounded. The question is whether there is a rigorous result on the other half of said sequences to produce a contradiction that the conjecture is false.

19 April, 2012 at 4:49 am

Joseph SinyorIf I may restate your comment, It is easy to show that the path from 2^k – 1 for a given k leads to 3^k – 1 (rapid expansion). The trick is to show that the sequence from that point leads to 2^m – 1 where m < k

19 April, 2012 at 5:17 am

AnonymousNo, the trick is to keep track of, and say something rigorous about, the ones-ratio.

20 April, 2012 at 4:46 am

AnonymousFor example, fix n equal to one in equation one above. Then if the conjecture is true, there exists a finite value k whereupon the other variables enumerate every value of the form of mersenne numbers.

3 March, 2012 at 7:59 am

strange nicknameAnonymous wrote:

“Having a proof that there exists a divergent trajectory for the 5x+1

problem is a new result(i think).”

I think so too. In fact I have proved that density of numbers which have convergent

trajectories is zero and it does not necessarily mean that we can find a natural number which has divergent trajectory, but we can be sure that these trajectories exist in the infinity, for example, divergent trajectory for 2.5x+0.5 occurs in the limit:

lim (n to infty) [sum_(i=0)^(n) 4^i]

Anonymous wrote:

“Have you shown your proof to anyone?”

I posted the proof on some mathematical forum, but I have got no answers,

only one person said that is a bit long and incomprehensible. But it’s

not exactly true, if someone knows the subject matter poorly, than any

evidence may seem difficult.

3 March, 2012 at 8:24 am

StudentJoseph Sinyor wrote:

“At the risk of being self-serving, I suggest that one possible key to understanding the pattern behind the 3x+1 conjecture is related to the Mersenne numbers (2^k-1). ”

An interesting publication about Mersenne numbers is here as well: http://arxiv.org/pdf/1104.2804.pdf. The authors noted that a path length of a Mersenne number (2^n-1) is approximately proportional to 13.45n.

By the way I have proof, that if the standard heuristic arguments for the path length is true, then there are infinitely many numbers 2^n-c (c is some natural number) which have approximately proportional path length. What’s more if the Collatz for negative numbers has no divergent trajectories, then all the numbers 2^n-d (d is any natural number) in Collatz path for positive numbers have approximately proportional path length.

9 April, 2012 at 4:09 am

Conjetura de Collatz « Blog de Alex Moretó, un lugar para disfrutar aprendiendo matemáticas[…] Para quien quiera ver como un matemático de primer nivel piensa sobre ella le recomiendo esta entrada del blog de […]

9 April, 2012 at 8:38 am

tomaszdzHere:

http://www.occampress.com/solutionsubmit2.pdf

I found another collatz conjecture proof. Is it correct?

30 April, 2012 at 11:28 am

AnonymousIt’s every bit as rigorous as the two thousand and three paper of Applegate and Lagarias in MCOM.

25 April, 2012 at 10:33 am

singularnicknameWe can extend Bohm’s and Sontacchi’s result (weak collatz conjecture equivalent) and we can obtain any loop which has any “structure” (explained below) in collatz-like function by model (for obvious reasons, we limit here only to give the formula for the odd numbers):

Let be any odd integer. Let be odd number, defined as follows:

and the conditions are met:

1)

2)

Let be any natural number and the number of operations such as in the loop of number .

Let be any natural number and the number of operations such as in the loop of number .

Let be a rational number such that is an integer and also is an integer.

Using this formula, after the adoption of relevant variables that define our function, we can determine any number which goes into a loop in a Collatz-like sequences.

Example:

First, we select a variable , assume . Then we define and . It is easy to predict that our loop length will therefore . Assume that . The definition of our function will be as follows:

Let’s define . Note that the different selections of the variable so that the conditions are met:

1)

2)

are:

And for each of these options we will get a loop, but we take the variable described as follows:

Number which is a loop in our sequence is therefore:

Here is this loop:

1 May, 2012 at 12:57 am

leszek3Hi.

I have question:

Are two problems 3n+1 and 3n-1 equivalent ?

5 May, 2012 at 1:12 pm

singularnicknameIn which way?

5 May, 2012 at 11:46 pm

leszek3The existence of unusual trajectory (new period or divergent) in one,

implies such trajectory in the other. Consider e.g. only positive n.

7 May, 2012 at 12:51 pm

singularnickname“The existence of unusual trajectory (new period or divergent) in one,

implies such trajectory in the other.”

Not exactly. Can be proven only that if for example is number of divergent trajectory in one of sequences and then for sure the -th elements of trajectories () will be grow to infinity. In other words trajektory of also will be divergent.

There are many compounds of 3x+1 and 3x-1 sequences. What is more these two sequences are mirror images if we consider the structure of transformations in these sequences. This fact has many implications which indicate very strong relationships of these sequences.

8 May, 2012 at 1:53 am

leszek3Thank You very much.

6 May, 2012 at 12:02 pm

AnonymousI believe they are two separate problems; no one has proven that one is equivilant to the other.

22 April, 2014 at 4:00 am

AnonymousYes, in that 3n-1 is what you would get if you took the 3n+1 algorithm into the negative numbers but looked at the in the positive. it contains the loops containing each smallest number here: -1, 1, 5, 17. whereas the loops for 3n+1 have as their smallest numbers; 1, -1, -5, -17.

14 September, 2012 at 10:24 am

April NicoleBasically, if you add 1 to every odd number, you get an even number. you dont even have to multiply by three. The equation is the same and can be stated many different ways with the same result. If even divide by two, if odd just add 1. If you can prove any odd number plus 1 = an even number, you have essentially proven the Collatz conjecture.

17 September, 2012 at 8:30 am

AnonymousHello! Would you know please, which journal would be appropriate to submit to an article on this subject? Thanks for helping me

27 December, 2012 at 7:28 pm

Chris Bernardinithe sets of odd numbers are three infinite and one finite sets that separate all odd N. they are based on cardinality and in order to keep it simpler i will only state cardinality in these definitions because we already know what these mapping of values to the set of all N entails and their true meaning.

Set X = Odds 2,5,8,11,14,17,….etc…..infinity

Set – = odds 3,6,9,12,15,18,…etc….infinity

Set + = Odds 4,7,10,13,16,….etc…..infinity

Set ???? = 1 and ONLY 1.

now the true point of these set designations is this. due to prime factorization and the fact that every odd number is factorized by a unique set of odd prime factors and all evens are just adding a string of multiplications of 2s on each unique odd numbers factorization. essentially what I’m saying is every even integer is composed of an odd base and multiplication of a string of 2’s that each even number has a particular unique number of 2s In its factorization and all even numbers if stripped of 2s will descend to a particular odd number and that number as well as the movements leading to that number are predetermined because due to he rules every number can ONLY move one preset direction. a few rules involving these sets are this

if any element of set X has ANY amount of 2’s in is prime factorization no whole positive odd integer X can ever equal that value as a result of (X*3)+1

if any element of set – has any odd number of 2’s in its prime factorization then One and only one X will satisfy for X*3+1. that value is predetermined in the following ways.

if an element of set – is multiplied by 2^1 then the value that produces that even as an odd within the collatz system is the element of -‘s actual numerical value minus its cardinality within set – multiplied by 2. for 5 which is the first element of this set it would be for example 5 – 2*1 and the next number in set x is 11 and the value that creates it times 2 is 11 – 2*2 and so on so forth into infinity.

the other infinite set + acts directly parallel to set – except that it does this by adding its cardinality multiplied by 2 instead of subtracting. also where for set – all of the odd numbers of twos in is prime factorization gets switched with evens for this one. and the minimal case where the producing value is directly related to the odd is that odd multiplied by 4 for example 7 is the first number in this set and 7 *4 is equal to (7+(2*1)*3+1 and 13 which is the second number in this set times 4 is equal to 13+(2*2)*3+1

this is for the most part everything involving how to split up and see the predictable nature. but one will notice that logically it seems that you could have 1 be part of set + based on the progression of those numbers. BUT it cannot for it would throw off every other numbers cardinality and causes 1 to be left alone as 1 *4 = 1*3(+1) and is the only number that causes a number hat breaks down to itself on immediate removal of all 2’s on successive division of two.

also for all Odds numbers X. if X * 2^n = n*3+1 then X*2^n+2 = n*4+1 or n+x*2^n both of these give the exact same values.

also another reason 1 mus be in a set of itself is another way of splitting odds hat requires it to be so. it basically falls on my concept of the way a number must move is a transform stage. so in my notation for this part x—–>y means that X becomes Y under all circumstances and Xx then x——>1.

if element of set E——>X then X———>Y and y is always Greater than E for ALL E’s

if element of set O———->X then X———–Y and y is always less than E for all E’s

also if N———>X————–>Y if N is any odd Y will be odd and NO Y will EVER be an Element of set X from the previous groups.(no number divisible by 3 will occur as Y and if y——–>z——->f,,,, so on so forth and no number will ever be divisible by 3 after a value divisible by three has occurred.

this last part is the one area i haven’t gone too much into. I’m sure there might be a real rule that pinpoints exactly how much larger or smaller a number will be on second transform but i haven’t really felt like going into this any further as i am currently working on a new problem. Hopefully this gives news answers and may be the part needed to prove this “Hard” problem. i just think its more absurd to think any other number would cause a cycle based on the two different clearly explained reasons why one causes an exception when working with the set of all odd numbers.

27 December, 2012 at 7:32 pm

Chris Bernardinithere are simple ways to turn an odd into is set and its cardinality very simply. i left this out simply due to laziness. but the method is whether or not you have to add 2 or subract two from it to make it divisbile by 3 and that tells you which set and then you simply divide that value that is divisible by 3 and thats N’s cardinality in that set. for the set X they are all the odds divisible by three and u just divide by 3 to get their cardinality although that set is completely unessecary for anything.

28 January, 2013 at 7:20 am

AnonymousThe result of Krasikov and Lagarias, world record five in Lagarias’s 2010 book, does not have a rigorous proof: and therefor is unessecery for anything.

2 February, 2013 at 2:09 am

HuenykI am a control system engineer. 3n+1 problem has attracted my attention as a controller tuning problem for stability to 1. After one month, I give up for good. The reason is that n/2 cannot be touched. You can’t go to n/4. 3n+1 can be finely tuned to either 3n+3 or 3n-1 both of which are nonconvergent. This is a highly nonlinear control system. As a control engineer I give up. But number theorists don’t know that. So they plod on!

HuenYK (dr)

cosmolog92@gmail.com

2 February, 2013 at 7:08 am

Anonymoushow could it not be linear when the entire equation and operations is linear? slopes up (3n+1) and comes back down with slope 0(N/2).

N/4 is touchable for sure but you just need to look at one very particular string of odd numbers. this particular string of odd numbers to be exact 1+8n for all N. ex. 1,9,17,……

ill even make it easier for you with a simple proposition.

3(1 + 8N) +1 = (1 + 6M) 2^2 iff N is any Natural number and M is dependent on N. meaning there is only one M for each N.

13 May, 2013 at 1:58 pm

vznvznhi all great to see the intense enthusiasm for the problem here. here is a brief writeup on my Turing machine blog of an approach based on a real FSM (finite state machine) transducer constructed for iterates (briefly mentioned but not given in the wikipedia article>) which also has a close connection to an old paper by Shallit/Wilson on its relation to regular languages. its also ruby “tool box” code for experimenting with different enumeration orders that might be helpful for finding an inductive structure/proof. it also cites Sinyor’s paper as a very “nearby” approach. hope to chat with anyone on the subj & interested in experimental/computational approaches to & attacks on the problem via comments etc.

16 July, 2013 at 9:13 pm

helloparthThere is a typing error in: “An inspection of the proof of Proposition 4 reveals that this orbit consists of {k} steps of the form {x \mapsto 3x+1}, and {a_{k+1}} steps of the form {x \mapsto x/2}. As all terms are at least {n}, the former steps can increase magnitude by a multiplicative factor of at most {3+\frac{1}{N}}. Should say “As all terms are at least {N}…”

[Corrected, thanks – T.]19 July, 2013 at 3:24 pm

summer fun/break/vac & the may collatz breakthru | Turing Machine[…] 5. The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 | What’s new […]

2 October, 2013 at 2:34 pm

NickBy working with a fully reduced version of the Collatz function $f(n) = (3n+1)/(2^r)$ to produce only odd number values, one is able to generate new solutions (and therefore new trajectories of equal size) to the associated exponential Diophantine equation by performing arithmetic on the exponents.

For example, if $n$ is an odd number (with finite trajectory) and $(k, a_1, a_2, … , a_k+1)$ is its associated (reduced map) tuple, then $(k, a_1, a_2 + 2, a_3 + 2, … a_{k+1} + 2)$ is another solution, namely $4n+1$. Here we are adding 2 to each exponent other than $a_1 = 0$. $4n+1$ then has the same trajectory as $n$ (after the seed value). Indeed, you can add any even integer $2m$ the exponents to obtain the $m’th$ iterate of $n$ under $4n+1$.

One can also add integer multiples of $phi(3^k)$ to $a_{k+1}$ to obtain new solutions. Here, $phi$ denotes Euler’s Totient function.

18 April, 2014 at 10:56 am

vznvznhi TT, back… some interesting hot-off-(word)press new ideas re collatz…gamechanger? :idea: just found that looking at “blocks” starting at through , and algorithms that choose next values in the blocks to decrease, can create “aggregate trajectories” that stay smaller than a ceiling (close to the initial ceiling which is sum of the starting block values). if these aggregate trajectories can always be proven to converge, theres a proof…. :!:

polymath prj, anyone?

am planning to crunch on this further but at a pause point, dont have next step in mind yet….

22 April, 2014 at 4:26 am

Anonymousafter 10 years working on the collatz conjecture I feel pretty stupid having all of my independently derived formulas splashed all over the page up top. :) specifically the formula

but i write a(k+1) as x1+…+xn, k as n and a1,a2, as x1,x1+x2…

But i’ve noticed that integer solutions pop up everywhere once you bend the rules. for example, plug in values for the accumulative totals of the exponent of 2’s that dont exist as a 3n+1 function, and put a zero or negative number in the mix and you get loops with even numbers where there should be odd, loops with a single number only being an integer. etc etc.

if the cumulative sum of x1 to xn is between n and 2n an integer solution can exist for the ‘n’ in in equation (1) (which i denote as a function of x1,x2…xn, representing how many times you divide by 2 between each time you multiply by 3 then add 1: as B(x1,…,xn) )

its essentially the same formula, but I use each value as a sum, instead of a1<a2…

22 April, 2014 at 4:50 am

Anonymousformula didnt display right :(.

[Corrected – T.]anyways, here are some of my results you guys may find interesting:

NB:

B(x) = B(x,x,x,x,x,x,x) repeating loops

B(X,Y) = B(X,Y,X,Y) repeating loops

B1(X,Y,Z) = B(X,Y,Z) 1 means first term first

B2(X,Y,Z) = B(Y,Z,X) 2 means second term first

B(2) = 1 (trivial cycle, 1,4,2,1…)

B(1) = -1 (true negative cycle, -1,-2,-1…)

B(1,2) = -5 (true negative cycle, -5,-14,-7,-20,-10,-5…)

B2(1,2) = -7 (true negative cycle above, -7,-20,-10,-5,-14,-7…)

B(1,1,1,4,1,1,2) = -17 (true negative cycle)

Non 3n+1 values that DO fit the formula:

B(-2,0,7) = 2

B(4,3,-1) = 5

B(1,6,-3) = -13

B(0,6,-3) = -4

I have 53 integers so far in ‘n = 3’ sets for outside collatz parameters.

13 June, 2014 at 2:40 pm

AnonymousThis is funny and curious: http://www.collatz3xplus1problem.com/

3 July, 2014 at 9:27 am

$3M Breakthrough Prizes now awarded in mathematics! | Turing Machine[…] Tao among them. who is a great blogger and have commented on his great blog in the past (he has a great page on Collatz theory). cybersynchronicity! just wrote him a congratulatory comment yesterday. am hoping he reacts in his […]

16 July, 2014 at 3:40 pm

Number Theory is the Cocaine of Mathematics | fractalcows[…] following resulted not from my intention to prove the conjecture, but from the drive to deeply understand its underlying […]

30 August, 2014 at 9:45 am

vznvznnew very promising property on collatz conjecture discovered. invitation to collaborators

15 September, 2014 at 3:40 am

rlvLet c(n) be the number of steps to convert n to 1 using the Collatz rules. I just noticed that c(5) = 5. Are there any other number n such that c(n) = n? Or is there a simple explanation as to why only 5?

1 December, 2014 at 4:47 pm

vznvznCollatz, striking visualization of binary density for 3x + 1 operation! crucial new piece of the puzzle! ruby/ gnuplot experimental math results

11 January, 2015 at 8:25 pm

vznvznattack on collatz using a novel genetic algorithm approach with some interesting results under further development, building on prior density results. the general high level idea is to create a new random walk out of collatz random walks with adjustable parameters, and the new random walk can be quantatively measured as “less random”.

9 April, 2015 at 12:30 am

herberthellinghttps://collatzproof.wordpress.com/

8 June, 2015 at 12:50 pm

Carlos Toscano-OchoaCould any of you send me the PDF by Bohm and Sontacchi?? I cannot get it and I need it for my research on Collatz conjecture. My email is biotoscano@gmail.com. Thank you very much!!

This is the URL that points to the paper, but it cannot be accessed:

http://www.ams.org/mathscinet-getitem?mr=551509

Thank you!!

8 September, 2015 at 6:14 am

AnonymousDemonstrated the Collatz Conjecture.

There are infinity of algorithms in the form for the cycle 4,2,1.

The first with $latex(X = 3)$; the second ; the third .

See:

http://www.hrpub.org/journals/article_info.php?aid=2882

20 September, 2015 at 3:05 am

Unsolved problems with the common core | Bits of DNA[…] despite much numeric evidence that it is true, has eluded proof. Mathematician Terence Tao has an interesting blog post explaining why (a) the conjecture is likely to be true and (b) why it is likely out of reach of […]

24 September, 2015 at 1:19 am

TECNOLOGÍA » Unsolved problems with the common core[…] much numeric evidence that it is true, has eluded proof. Mathematician Terence Tao has an interesting blog post explaining why (a) the conjecture is likely to be true and (b) why it is likely out of reach of […]

25 February, 2016 at 5:58 pm

oOn the toy model for the weak Collatz conjecture: The correct constraint is \\ $$a_1=0<a_2<\cdots<a_k$$

[

The two constraints are logically equivalent, since is never divisible by 3. -T.]4 April, 2016 at 10:48 am

Pętle w ciągach typu collatza | Problem Collatza - co nowego?[…] The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 […]

18 May, 2016 at 7:59 pm

Collatz Conjecture – Ket Space[…] Tao wrote an excellent post on the Collatz Conjecture on his blog. If you’re interested in taking a shot at this problem or just playing around with it a bit, […]

19 May, 2016 at 5:17 pm

Thor X. JonesRestate Collatz’ conjecturre: Following the 3n+1 or /2 rule will produce a number which is a power of 2.

And incidentally every other power of 2 is 3*an odd number +1 and the others are 3*and odd number minus 1.

8 June, 2016 at 12:19 pm

gninrepoli1) Let us find the upper limit (https://en.wikipedia.org/wiki/Schnirelmann_density#Schnirelmann.27s_theorems – Look at ), then for the equation there is for which the equation has no solution?

2) For example, we find this constant (let it be ) whether it will improve the latter estimate ?

14 August, 2016 at 7:34 pm

Sawon PratiherIt has been shown in the below arxiv preprint version. that, there exists only six, i.e., a finite number of recurrent forms in which the path elements of the Collatz sequence switches, till one of them reaches a number of the form 2^m.

http://arxiv.org/abs/1608.03600

15 August, 2016 at 1:21 am

aI think Sawon Pratiher’s approach is correct. I have thought about the same idea before and I am more or less sure looking at mod 4 and mod 8 suffices. Professor Tao please take a look at Sawon’s Pratiher’s result. Even if not correct he is extremely close to correct path.

26 August, 2016 at 3:09 am

Sawon PratiherThe recurrences shown here, can it be solved using the method of solving simultaneous solution of linear congruence equations?

http://arxiv.org/abs/1608.03600

28 August, 2016 at 2:08 pm

Miklos KontraHi, I would like to tell everyone that i found the solution to the problem, i am working on the problem since 3 years and i m glad to show the results in my computer science thesis here in Argentina University UNLAM I show that as the hungarian Paul Erdos said mathematics are not ready to solve this kind of problem, basically the answer is as Conway states that it s a tree b, but i showed that it behaves as a tree if you take out the cycle 4 2 1 since a tree can not have a cycle on it, i found the 3 patterns that shows how to get from any points before getting to the cycle which i removed. The good thing once i get the graph is that it shows why it s really deterministic and shows in it the randomness behaviour i wrote to conway but i was told that he is not able to understand my work may be due to some hilness I would like to get in touch with Tao to discuss the work is it posible? Thanks in advance.

25 September, 2016 at 7:39 am

yuvalleventalI have discovered an infinite number of solutions for the Collatz conjecture. This does not prove it, but shows that there is no upper bound. Is this already known/good enough for a research paper? Does anyone want to give advice?

http://pastebin.com/raw/q5DyHGiz

Yuval Levental

http://linkedin.com/in/yuvallevental

29 September, 2016 at 4:45 pm

CraigTwo professors from Italy and Belgium recently announced a proof of the Collatz Conjecture. Any comments on it? https://www.researchgate.net/publication/299749569_A_proof_of_the_Collatz_conjecture

29 September, 2016 at 9:39 pm

AnonymousRequest to please have a look at the recurring patterns in the 3n+1 problem.

https://arxiv.org/abs/1608.03600

30 September, 2016 at 7:07 am

AnonymousThe argument in theorem 9 (excluding the existence of any zero-measure unbounded deterministic trajectory) is not sufficiently clear. It would be clearer if it could be made effective (e.g. by giving an explicit bound for all the iterates of any ).

30 September, 2016 at 8:39 am

CraigI think they mean that since there are no zero measure sets of integers given the measure that they defined, there cannot be a zero-measure trajectories, by the ergodic theorem.

10 January, 2017 at 5:12 am

Dmitri KamenetskyThe paper looks legit. I would love to know the opinion of the experts.

16 October, 2016 at 3:04 pm

anh quốc nguyễncollatz conjecture’s proof

1. Introduction:

Collatz conjecture are define that with G(n)={ n÷2 n≡0(mod2)

3n+1 n≡1(mod2)

conjecture said that there will alway exist k that Gk(n)=1.

2. backround of the proof

the proof will base on the position of odd number in the chart. the problem of this situation is about the input and the out put of the equation.

3. proof

by observing G(n)≡0(mod2) => G(n)= 2k×m

m=2 =>G(n)k+1=1

m≡1(mod2) => G(n)k=m

base on that fact

we will mainly focus on the behavior of G(n) when m≡1(mod2)

let O be the group of odd number

O={O1, O2, O3, …, OL,…}

where OL+1-OL =2

O1 =1

L: the position of odd start from 1

=>OL= 2L-1

by another observation

G(OL)-G(OL-1)=3 (since O1-O2 =2)

=> the output of the equation as O1-> infinity is alternating odd and even.

since G(1)≡0 (mod2)

=> G(O2L-1)≡0 (mod2) and G(O2L)≡1(mod2)

same agument, we will just forcus on output odd.

since G(O2L)≡1 (mod2) => G(O2L)= Osomething

we know that G(1)=G(O1)=2, G(OL)-G(OL-1)=3 and OL=2L-1

=> other way of writting for the equation of n ≡1(mod2)

G(O2L) =2+3(2L-1)= 6L-1= O3L

O3L=G(O2L)

now we look at G(odd)≡0(mod2)

G(n)≡0(mod2)

=>G(n)=2k×m

m≡1(mod2) (did mention)

m=2 =>G(n)=2k+1

2k+1=2+3L

=>L=2k+1-2÷3

=> 2k≡1(mod3)

=>k≡0(mod2)

with the position of odd that

L=(2k-2)/3 k≡1(mod2)

G(x)->1

since there are infinite k≡1(mod2)

=> there are infinite L that make G(x)->1

=> the conjecture is true

11 November, 2016 at 1:28 pm

CraigWhy did Professor Tao say it is only possible to prove uniform convergence for the first O(log n) iterations and that it gets too complicated afterwards for known techniques?

11 November, 2016 at 4:21 pm

miklos kontraHi, i ve worked out a way to show that Collatz conjecture is true using a tree structure just like Conway did , but my tree is better than the one that Conway did it also shows why mathematics can t show how to solve the problem since in the tree structure it can be seen that there is some kind of randomness, i would apreciate if some one could help me showing me or teaching me how to upload the tree structure and it s explanation, i live in Argentina and i m working on this problem at one of the University but since it is not amathematical proof but a perfect tree structure that holds all the numbers showing all the paths, i think that if matematicians sees the structure they would better understand what s going on and might use their knowledge to solve mathematically the problem which i know is not under my knowledge since i m an electronic engineer but a real entusiasm and i love maths, i thing it would really benefit the math word to understand that the Collatz conjecture is true and help mathematicians.

Miklos Kontra from Argentina

Enviado desde mi iPad

El 11 nov 2016, a las 6:28 p. m., What’s new <comment-reply@wordpress.com> escribió:

Craig commented: “Why did Professor Tao say it is only possible to prove uniform convergence for the first O(log n) iterations and that it gets too complicated afterwards for known techniques?”

20 November, 2016 at 11:09 am

Collatz-formodningen. | Matematikbloggen på AAU[…] Erdös har efter sigende sagt, at matematikken endnu ikke er klar til at løse Collatzproblemet og Terry Tao er enig. Det er et fint problem, fordi det er let at forklare, man kan selv finde på lignende problemer […]

14 February, 2017 at 10:20 am

Martin MaderaI have noticed a surprising and very strong regularity in the distribution of orbit lengths. I define chain(n) as the orbit, skipping even numbers and terminating once a number in some earlier chain(k) for k<n has been reached. So the first few chains are as follows:

chain(1) = {1}

chain(3) = {3, 5, 1}

chain(5) = {5}

chain(7) = {7, 11, 17, 13, 5}

chain(9) = {9, 7}

chain(11) = {11}

chain(13) = {13}

chain(15) = {15, 23, 35, 53, 5}

and the corresponding chain lengths are 1, 3, 1, 5, 2, 1, 1 and 5, respectively. The idea is to iterate until you hit a number that you've seen before.

I have calculated all chains up to n=50,000,000. I then looked at the distribution of chain lengths for 0 < n < 100,000 and compared this to the distribution for 49,900,000 < n < 50,000,000. To my surprise the distributions are virtually identical!

Here's a snippet:

Chain length — Number of occurrences 0-100k — Number of occurrences 49,900k-50M

1 — 23401 — 23418

2 — 13665 — 13646

3 — 3238 — 3244

4 — 3333 — 3342

5 — 1671 — 1677

6 — 1413 — 1393

7 — 841 — 844

8 — 525 — 512

9 — 397 — 380

10 — 271 — 267

I don't see a way of attaching the full graph, so I will post a link to my Google Drive instead:

https://drive.google.com/file/d/0B9yj-Ue4a4e9SXlwMnJxWTcxMU0/view?usp=sharing

For higher lengths (where there are fewer occurrences) there is more noise, but overall these look to me like two samples drawn from an identical distribution. The accuracy with which fine details are reproduced (e.g. the dip at length=3) in both samples is very surprising to me.

Here is my very simple Perl5 script for calculating chains:

https://drive.google.com/file/d/0B9yj-Ue4a4e9ZFJxSmVNTHlDV1E/view?usp=sharing

and its output up to 10,000:

https://drive.google.com/file/d/0B9yj-Ue4a4e9cWNOOFB3T2kwVnM/view?usp=sharing

These results seem to suggest that chains around n=50,000,000 behave exactly like chains around n=1.

14 February, 2017 at 11:03 am

Martin MaderaP.S. It has occurred to me that calling these objects “branches” rather than “chains” would make more sense. The word “branch” makes one think of something attached to the rest of the tree, which is a very good intuition for what these objects are.

14 February, 2017 at 11:13 am

Anonymoushttps://www.quora.com/Is-the-Collatz-Conjecture-solvable/answer/David-Cole-146

14 February, 2017 at 2:59 pm

Gerry“Conjecture of Erdos” links to a review of his 1979 paper, Some unconventional problems in Number Theory. That paper is available at http://www.renyi.hu/~p_erdos/1979-21.pdf but I don’t see the powers-of-2 conjecture in it.

[Link corrected – seems Erdos published two papers with the same name in 1979! -T]15 February, 2017 at 2:34 am

Martin MaderaI have made further progress. The definition of branches in my previous post is fairly difficult to reason about, because it involves looking at the content of all earlier branches.

So I tried a simpler definition: branch(n) is the orbit of n, leaving out even numbers, which terminates once it reaches a number k < n. So the first few branches are as follows:

branch(3) = {3, 5, 1}

branch(5) = {5, 1}

branch(7) = {7, 11, 17, 13, 5}

branch(9) = {9, 7}

branch(11) = {11, 17, 13, 5}

and the lengths are 3, 2, 5 and 2, respectively.

It turns out that the behaviour for this simpler definition is even more regular! I have looked at two intervals:

I1 = 2 … 2^22 (= 4,194,304)

I2 = 2^50 + 2 … 2^50 + 2^22

Both contain exactly 2,097,151 odd numbers. The number of occurrences of branch lengths up to and including 26 is exactly the same in both intervals (!), and it is as follows:

2 1048575

3 262144

4 262144

5 98304

6 114688

7 49152

8 30720

9 43520

10 22144

11 30464

12 15376

13 10608

14 16090

15 8818

16 12750

17 6806

18 9807

19 5170

20 3737

21 5909

22 3348

23 5034

24 2746

25 1984

26 3189

I find it more helpful to transform these into stopping probabilities, defined as:

P(stop at length L | not stopped earlier) = (number of branches of length L) / (number of branches of length >= L)

The first three stopping probabilities are as follows:

2 … 50.0000%

3 … 25.0000%

4 … 33.3333%

I have looked at the values of n for which L := |branch(n)| = 2, and it is fairly easy to spot that they appear to be of the form:

L=2 branches: n = 4k+1

where k is an integer >=0.

It is quite easy to see what is going on here: all even integers are of the form 2k+1, which can also be written as either 4k+1 or 4k+3. Since n is odd, the first step must be:

n –> 1/2 * ( 3n + 1 )

which gives:

4k+1 –> 6k+2 … even, so /2 to 3k+1, which is less than 4k+1 = stop

4k+3 –> 6k+5 … odd, so another iteration of 1/2 * (3n + 1)

So we can see that n=4k+1 stops at L=2, whereas n=4k+3 continues. This explains why exactly 1/2 of all branches stop at L=2.

I have further looked at branches of length 3, and noticed that all of the n for which |branch(n)|=3 appear to be of the form:

L=3 branches: n = 16k+3

This would explain why the stopping probability is 1/4:

– the branches that did not stop at L=2 are of the form 4k+3

– this is equivalent to 16k+3, 16k+7, 16k+11 or 16k+15

– of these, 16k+3 stop at L=3, i.e. exactly 1/4

As a final exercise I looked at branches of length 4, and these appear to be of the form:

L=4 branches: n = 32k+11 or 32k+23

Once again it is fairly simple to explain why the stopping probability is 1/3:

– the branches that did not stop at L=3 are of the form 16k+7, +11, +15

– this is equivalent to 32k+7, +11, +15, +23, +27, +31

– of these, 32k+11 and +23 stop at L=4, i.e. exactly 2/6 = 1/3

Once I noticed the key role of powers of 2 (i.e. 4, 16, 32), I changed the intervals to reflect this and produced the statistics above.

If this behaviour continues for longer lengths, it would explain why there are differences at L>26: the base at this point has presumably grown to >2^22, so the various classes relevant at those lengths start having different numbers of members in the two intervals I have chosen.

15 February, 2017 at 11:18 am

Martin MaderaI have found a neat way of generating orbits longer than any arbitrary length.

If we call the two transformations g and h,

g: n –> (3n+1)/2

h: n –> n/2 … the “h” is short for “halve”

and then define g^k to have the obvious meaning:

g^k (n) := g{ g^(k-1) (n) }

i.e. k successive applications of g, then I believe that

N(L) := (2^L) – 1

is obviously odd, and more importantly will remain odd under each of (L-1) successive applications of g.

For the record, the result of L applications of g will be:

g^L {N(L)} = (3^L) – 1

Unless I messed up somewhere, this relation can be derived by iteratively repeating the following steps:

1) Apply the substitution:

k –> 2k + 1

to the equation derived during previous iteration, or to the following equation in the first iteration:

k = k.

In the first iteration this simply results in:

2k + 1 = 2k + 1.

In general, assuming that we are in iteration n+1 and the equation resulting from iteration n was:

g^n { (2^n)k + (2^n) – 1 } = (3^n)k + (3^n) – 1

this step will give:

g^n { (2^(n+1))k + (2^(n+1)) – 1 } = 2*(3^n)k + 2*(3^n) – 1 .

2) Note that following the substitution, the RHS is now clearly odd, so we can generate the next number in the orbit by applying g to both sides. In the first iteration this results in:

g(2k+1) = 3k + 2

which just happens to be of the form noted above. In general, applying g to the RHS from step 1 gives:

g{ 2*(3^n)k + 2*(3^n) – 1 } = (3^n)k + (3^n) – 1

and the LHS is simply:

g^(n+1) { (2^(n+1))k + (2^(n+1)) – 1 }

This is precisely the equation for n+1.

As the final step in the proof, we may as well set k=0 to simplify the result.

17 February, 2017 at 6:24 am

MatjazGQuite neat indeed. Just an extension your observation:

which is odd for and even for , where of course .

In particular this means that all numbers of the form have orbits of length at least for .

P.S.

Of course it holds that for which means that the first elements of the orbit of (from to ) actually form a monotonously increasing sequence of odd numbers.

17 February, 2017 at 8:59 am

MatjazGEven more generally for and odd:

which is odd for and even for . All numbers of the form for odd thus have orbits of length at least .

(The above formula can be easily checked by writing as .)

The length of the orbit is actually a bit longer, if we count halving even numbers with as steps (we usually do). After iterations we arrive at:

after which we would need at least halvings to reach as fast as possible. The actual orbit is thus at least steps long assuming we don’t end up in a non-trivial cycle (in which case the Collatz conjecture would be false).

17 February, 2017 at 10:16 am

Matjaž GomilšekOf course every odd number can be written in the form and every even number can be written in the form where is odd and . We can thus define a compressed version of the Collatz function :

This function is just iterated times on numbers of the form for . The function maps odd numbers to even ones and vice versa:

and the trivial cycle of is again the same as for , namely: .

It can also be quite efficiently implemented in a binary encoding. Explicitly:

1.) If is even: delete the trailing zeros in its binary encoding.

2.) If is odd: add to it, delete the trailing zeros from the resulting binary encoding, multiply the resulting number by (= append a trailing zero to and add this to ; repeat times), and finally subtract from it.

Whether this is useful I do not know, but I do like the fact that this compressed always exchanges odd and even numbers … :)

17 February, 2017 at 10:34 am

Matjaž GomilšekFinally, can be compressed a bit further by defining as the composition of with itself, restricted (for example) to just the odd integers. Then:

and the trivial cycle is simply a fixed point: . I believe this to be a most economical way of writing the (iterated) Collatz function.

Explicitly, is equivalent to:

where: are uniquely defined for a given odd by (here are odd integers):

Or in other words, you can look at the occurrences of sequences in the application of to and replace each such sequence with a single application of .

17 February, 2017 at 2:46 pm

Matjaž GomilšekForgot to add that upon (uniquely) solving the system:

where odd and the result of applying to can be simply written as:

P.S. Solving the system is really easy, as detailed in a previous post. Explicitly:

1.) = (number of trailing binary zeros in )

2.) = ( without the trailing binary zeros)

3.) = ( without the trailing binary zeros) =

P.P.S. I must look over your posts in more detail as well, Martin. Will most likely post more tomorrow.

17 February, 2017 at 9:17 am

Martin MaderaYou are on the right track, but this can be generalised much, much futher.

I believe I have understood the reason for the periodicity shown in my earlier comments, but I’ve been too busy to post.

If we call the two operations

… “half”

(as before) and then compose the operations into operations like

then these “operators” have something that, for lack of a better word, I call eigensets.

I will start by writing out a few interesting equations, and then explain the meaning (to the extent that I’ve understood it) later.

hhh(8k + 0) = 1k + 0

ghg(8k + 1) = 9k + 2

hgh(8k + 2) = 3k + 1

hgg(8k + 3) = 9k + 4

ghh(8k + 4) = 3k + 2

hhg(8k + 5) = 3k + 2

ggh(8k + 6) = 9k + 8

ggg(8k + 7) = 27k + 26

The sets in the left bracket are what I call “eigensets” of the operator: they are the only integers for which the operator returns an integer (as opposed to a fraction).

We see that there are exactly 2^3 = 8 operators of order 3, and their eigensets span the integers.

This explains the periodicity observed in my earlier comments.

The general form of the eigen-equation is as follows:

where the operator T consists of a sequence of a total of

aoperators, of which(a-b)are g-operators andbare h-operators.Here I’ve used the fact that

or more generally

and since a similar relation holds for the h-operator as well, I get

Now there are two questions:

Q1: Given an eigenset, how do you find its corresponding operator?

Q2: Given an operator, how do you find its eigenset?

Rest in the next post.

17 February, 2017 at 9:28 am

Martin MaderaFollowing on from my previous post …

Q1: Given an eigenset, how do you find its corresponding operator?This is fairly easy: in order to find the operator associated with eigenset , you simply follow the orbit of

cforasteps and note the sequence of g and h operations. For example, for 8k+6 above, we first halve to 3, then g from 3 to 5, and then g again from 5 to 8. Hence, the operator associated with the eigenset 8k+6 is ggh, and the RHS constant is ggh(6)=8.Q2: Given an operator, how do you find its eigenset?Going the other way is a bit harder. The method I use generalizes the approach from my earlier post. It starts from the equation

k = k

and uses one of these two substitions at each step: either

or

.

For example for the operator ggh, we start with

k = k

and since we want to apply h, we need it to be even (at the moment it could be either). So we apply giving

2k = 2k

Now the RHS expression is clearly even, so we can apply h:

h(2k) = h(2k)

and simplifying the h on the RHS gives us the first-order eigen-equation

h(2k) = k .

Next we need an odd number for g, so looking at the RHS, we see that in this case we need to apply :

h(2(2k+1)) = 2k + 1

The RHS is now odd, so we can apply g:

gh(4k + 2) = g(2k + 1)

Working out the g() on the RHS then gives us the second-order eigen-equation

gh(4k + 2) = 3k + 2 .

Next we need the RHS to be odd for the final g, and we once again achieve this by applying :

gh( 4(2k+1) + 2 ) = 3(2k+1) + 2

i.e.

gh(8k + 6) = 6k + 5

The RHS is now odd for any k, so we can apply g once again:

ggh(8k + 6) = g(6k + 5)

and working out the RHS gives us the eigen-equation for our chosen third-order operator ggh:

ggh(8k + 6) = 9k + 8 .

The constant next to k on the RHS is always a power of 3, i.e. odd. So which substitution is applied at each step depends on the final number on the RHS and whether we need the result to be odd (for g) or even (for h). In the above example the relevant numbers were all even (0, 0 and 2, respectively). Had one of them been odd, we would have used the other transformation instead, e.g. if we wanted to turn

3k + 3

into an even expression, we would use , which gives us

3(2k+1) + 3 = 6k + 4.

17 February, 2017 at 9:50 am

Martin MaderaAs a final observation for the above posts, at any given order

athe “first” i.e. 0 eigenset is:and the last one is:

The 1 and 2 eigensets are as follows:

– for even orders:

– whereas for odd orders:

I have a bit more to say on operators, orbit length and the possibility of cycles, but need to go and earn a living. Hopefully more over the weekend!

17 February, 2017 at 3:00 pm

Martin Madera4. One idea I’m pursuing is that it might be more efficient to search (for cycles) in operator space as opposed to number space — in theory it could speed up the search because you don’t need to deal with all the copies, over and over again.

The idea rests on two insights:

i) All the operators I’ve looked at so far (except those corresponding to 0, 1 and 2 eigensets, which contain the and cycles) have the following property: in the eigen-equation

– either and … an “underwater” operator

– or and

i.e. the result is either always less than the argument, or always greater, for all k.

I am only interested in “branches”, defined as orbits that stop once you hit a lower number than the one you started from. (The rationale here is that if you’re lower than you started, you’ve “joined the tree” — the rest is a problem you’ve dealt with earlier in your search.)

ii) One can use the approach from Q2 in my previous post to grow the operator eigen-equations indefinitely. At each iteration one discards any operators that are “underwater”, and the rest are bifurcated via and and then grown by one.

5. Quickly regarding cycles. A cycle is T(n) = n.

If I remember correctly, it’s elementary number theory that prime decompositions are unique, so you can’t have and the only options are and .

So the only options for cycles are:

i)

ii)

It can be shown fairly easily that (ii) can’t happen — I will post the proof tomorrow. I’ve got a bit to say about (i) as well, but that’s clearly the place where the really really hard problem is buried. I recognize things from Terry Tao’s initial post.

@MatjazG – sorry I haven’t read your posts in detail, will do so tomorrow and will respond.

18 March, 2017 at 9:54 am

Abdelghaffar SlimaneHi all, I think I proved the Collatz’s conjecture for positive integers (cycle … 4, 2, 1) and for negative integers (cycle …-4, -2, -1). I submitted recently two papers to the AMS.

25 March, 2017 at 5:09 pm

Abdelghaffar SlimaneI strongly denounce the laxity of some mathematical journals. What is more frustrating than after finding the demonstration of a conjecture spelled out for more than 80 years which is Collatz’s conjecture and to see his manuscript being refused without plausible reason. May be my name !!!

26 March, 2017 at 2:57 am

Matjaž GomilšekHave you published anything before? Have you considered posting it on arXiv first (like Perelman)? What was the “unplausible” reason given to you by the AMS? It’s kind of hard to judge without answers to those questions …

26 March, 2017 at 6:52 am

Abdelghaffar SlimaneHere is their reply :

Dear Dr. Slimane,

This message concerns the manuscript

An elementary proof of the Collatz’s conjecture

by Abdelghaffar Slimane

Thank you for your submission to the Bulletin of the JJJ.

However your article is not suitable for publication in

this journal. JJJJ publishes only a very small number of

articles and we look for articles that appeal to a wide

audience. You may wish to submit your article to a more

specialised journal.

Best wishes,

…….. end of the message

So, at their point of view , solving an old problem (80 years old) is not an important thing !!!!!!

Please, what I want is just someone who endorse me on ARXIV for the submission of this proof. Please, consider my message as asking for endorsement.You can post your proposition on my email-adress : aslimane@gmail.com

Thank you

26 March, 2017 at 3:51 am

Czerno@Abdelghaffar Slimane : Hey! Please review or explain your above claim, Surely you’re aware Collatz has 3 well-known (trivial?) cycles in the negatives, not just one, Also “…-4, -2, -1” is not a collatz sequence. Your typo, I presume.

26 March, 2017 at 6:57 am

Abdelghaffar SlimaneI proved that all the positive integers finish their Collatz’s sequence by 4, 2, 1, and all the negative integers finish their Collatz’s sequence by -4, -2, -2. Those are the unique cycles for the Collatz’s sequence por negative and positive integers.

26 March, 2017 at 6:59 am

Abdelghaffar Slimanesorry for the eror in typing : and all the negative integers finish their Collatz’s sequence by -4, -2, -1.

26 March, 2017 at 7:13 am

Abdelghaffar SlimaneMay be my proof for the negative integers is wrong, but for the positive, I think is correct.

26 March, 2017 at 11:59 am

Abdelghaffar Slimane@Czerno :

Sorry, my proof seems correct. I am talking about a modified (conjugate) form of Collatz’s sequence for negative integers of the form :

Theorem:

Let V ∶ -N* → -N* be the modified Collatz sequence on negative integers defined by:

V(n)= n/2 if n is even

V(n)= (3n-1)/2 if n is odd,

Then

∀ n∈-N* ,∃ d∈N∶ V^d (n)=-1

Notice 3n-1 for negative integers instead of 3n+1 for positive integers.

26 March, 2017 at 2:38 pm

CzernoAh, alright then Abdelghaffar – but you do realize that your “modified” Collatz process in the negative integers just mirrors the postive, i.e. it essentially adds nothing new : you’re essentially considering the positive case twice…

The interesting extension is : either consider the original Collatz (3 n +1) formula extended to negative integers, or; equivalently, study the alternate (3 n -1) variant on the positives.

Anyways, your claim to a proof for the “classical” Collatz problem on the positives would be a remarkable feat, provided such proof holds scrutiny, of course…

26 March, 2017 at 2:45 pm

Abdelghaffar SlimaneThanks for your reply Czerno.I agree with you that it mirrors the real Collatz sequence of positive integers. All I want now is someone to endorse me to submit my manuscript on ARXIV and then you will see the proof.

11 April, 2017 at 9:39 am

CHENG GAOI ever thought that we could try to study the question from the opposite direction, that is, starting from 1, then exploring the random structure of the “tree”.

15 April, 2017 at 10:54 am

Michael M. RossIt’s not beyond the realm of possibility that simple conjectures have elementary proofs. It seems to me that half of the Collatz – the question of cyclicality – could be dismissed with the following:

Consider the values of even set {a} and even set {d} where the sets represent the ascending and descending numbers, respectively. They are disjoint sets of elements a (every 3x+1) and elements d (every a divided by 2∗2…).

If 3x+1 is true for every a=4+(6∗k)

(4, 10, 16, 22, 28, 34…)

and

If a/(2∗2…) is true for every d=2+(6∗k)

(2, 8, 14, 20, 26, 32…)

Then, a≠d for ∞

(A Collatz and mn+x calculator/grapher: http://questafi.net/numbers/CollatzCalcNGraph-1.xlsm)

17 April, 2017 at 11:27 am

gninrepoliThe distribution of the sequence of the Collatz function is similar to random variables, if this is true, then this problem lies in the theory of symmetric functions.

27 April, 2017 at 1:03 am

yuko.yI would like to say that the structure of the Collatz sequence have already been found. All odd numbers finally converge the smallest numbers of just the 6-type parent nodes. Then they reach 1. There is no repeating cycles exclude 1 and It is only 1 which can be a root node.

I am a real amateur, non-English speaker woman who is hard to conversation in English. but I think I understand well for the “structure” of the sequence than other people, sorry. And how all N; especially such numbers odd<f(odd) finally decrease and reach 1.

However It may be defficult to describe the total stopping time k for all N.

Collatz sequence' structure seems to have some interesting properties which relates other mathematical areas also computer science. Because this sequence can be represented as a rather simple data structure.

2017 is the 80th since L. Collatz have found this fascinate sequence. I hope the problem proved in this year.

27 April, 2017 at 8:46 am

AnonymousFYI:

https://www.quora.com/Is-the-Collatz-Conjecture-solvable/answer/David-Cole-146

28 April, 2017 at 2:51 am

yuko.yok. thank you very much.

I don’t use probability by the way. just thought the numbers as some subsets then permute them to be a simple structure.

I said there are only six(2*3)-typed parent nodes. and finally all odds converge the smallest numbers of each these typed parents.

but more interesting thing is that there are two-kinds of exponent tuples which formed three-forms by the circular shift oparation, respectively.

I only understand the structure of the sequence and how all N reach 1 without using probability. but I can’t give a rigid proof for it. I am very elementary amateur.

6 May, 2017 at 6:55 am

Abhishek RaiDoes being true automatically imply that the stopping time is a total (non PR) function?

6 May, 2017 at 4:36 pm

Michael M. RossQuestion for anyone: If there existed another function that generates a proper superset of the odd numbers in every Collatz sequence (in the same order), would proving that function always had a stopping time also prove the Collatz conjecture?

7 May, 2017 at 2:06 pm

mikllos kontraI ve found a graph that proves that collatz conjecture is true and also that mathematics series will never or at least for the moment solve the problem, math are just not yet ready to solve the problem. in the graph that i found after 3 years of work shows that in all the paths of the graph there is a part that shows some randomness behavior, except for the case of 4k +1 sorry for the language I m from Argentina. There is a main branch 4k +1 from which all the others branch starts.

7 May, 2017 at 5:35 pm

Michael M. RossWhen I see 4k+1, my eyes light up. I wonder if we’re talking about the same thing: You can divide Collatz sequences into sets of any size with equal stopping times. The same first odd term recurs for $n*4+1$, $n*4^2+4+1$, $n*4^3+4^2+4+1$, $n*4^4+4^3+4^2+4+1$, and so on. This means that the stopping times of such sequences may be deduced based on one member of the set.

9 May, 2017 at 3:05 am

Ing. Kontra MiklosWell as i said before there is a main branch 4k +1 from which each nodes starts a new branch going to infinity, i just can add for the moment that from each nodes it enters variable nodes which could be seen as random but well defines ( only 2 kinds of nodes) then each branch after this that appears to be randomness!! goes to infinity but first passing by multiple of 6 and goes to infinity passing by only even numbers to infinity, i can t tell much more because it s a final thesis that i m presenting in the University of Argentina in computer science and i already have presented a paper which shows the result in a legal place called in Argentina Propiedad Intelectual.

As soon as i present my thesis i will upload the paper, it s really wonderfull to see how the graph with infinities branches deriving from a principal 4k +1 branch, each of these goes to infinity passing trough a couple of nodes then reaches a multiple of 6 then to infinity (there is another point out there that the graph have infinite branches and each of them goes to infinity, but that is another question to be solved by mathematician infinite infinities, therer are some works out there but that is not the point for the moment)

I spend almost 3 years of work, and i would like to add that the Hungarian Mathematician Paul Erdos and Craig are right, there is no way to solve the problem using at least in my opinin using series, this small randomness which is not really randomness makes imposible to use series, in each case or each branch the numbers of nodes that shows this behavior before going to infinity passing before by a multiple of 6 are variables.

Sorry for my poor english.

The only thing that I would like to add is efectively the conjecture is RIGHT!!!!!!

By the way I woul like to add one more thing, the only work that i saw out there that is near but missing a couple of things is the work done by Conrow.

I wish you good luck in your journey Michael, may be you l be able to find another way to solve the problem.

10 May, 2017 at 8:54 pm

yuko.y“two kinds of nodes” which you explain is odd inverse mapping, I think?

If so, it can be classified even more separately and exactly. or if you use matrices, then the nodes would be just two.

Did the tree (it’s not actually called a tree, maybe) become symmetry? many people do this inverse approrch, but they don’t find the symmetrical tree.

In my approach, there is any randomness at all. All odd have their own (as it were) seat number and there is actually a seating chart..

Solving the Collatz problem needs no new mathematical tools nor ideas at least in my way. but it’s quite for the computer science because of its’ structure.

Were you able to define the stopping time?

Personally I think it’s not able to define well even if the problem will be solved. or just due to my skilllessness.

I don’t count the depths of nodes also. because solving the problem is just the permutation of odd numbers to every numbers conclude 1. it’s just in my opinion.

Only a difficult thing of the problem was such numbers; x<f(x). but they can map to a part of the members of their same subsets. those numbers are x≻f(x).

I can not write a paper of this. why, because I don't know the proper way of writing, mathematics also english. so good luck to all.

11 May, 2017 at 2:48 am

Ing. Kontra MiklosHi Yuko, First of all I thought it was a tree structure, but anlysing my papers on grapph structure, acording to strict definition it s no a tree but a graph structure composed by nodes, from each of these nodes borns two nodes where 2 new branches borns that i call in my work upward branch which always starts from these node and goes to infinity using 4k +1, so as i told you before ther is a main branch 4k + 1, then from each of these nodes starts 2 others nodes *branches* the funny thing is that again there will be as i called an upper branch which again keeps the pattern 4k +1 and goes to infinity and a branch that goes downward passing through these nodes that seems to be random but i showed that the re not random ang goes to infinty after passing this randomness path to some multiple numbers and then comes up all even (multiply by 2 this is cCollatz rule for even and reaches infinity), there is no way to calculate the stopping time because of this randomnes, Another thing tha i can tell you and is on my paper that there the nodes should not be taken as a number but a group of numbers, this is the trick of the thing to get the structure of the graph, again the graph is like a binary tree but there is one caractherisitc that do not belong strictly to the definition of tree and tah ts the reason why it s a graph.

i tried to look out for som symmetry but i did not find any and i left this part of my thesis as future branch of investigation, I can t follow investigating this work because I m working now on my PHD in computer science where i m demostrating THAT RSA criptography is not secure I showing a way to find P an Q without looking for prime number.

I wish you good luck in your work, i wish that you can find another way that Collatz conjecture is true, believe me it is but it woul be nice if some one out ther could find another way……good luck again.

7 May, 2017 at 5:45 pm

chris3991mProof of the weak Collatz conjecture (please read this):

We start with (2^(ak+1) – 3^k)*n as the value of the left hand after the first cycle. Note that 2^(ak+1) > 3^k.

We perform an infinite amount of cycles. This results in (2^inf*(ak+1) – 3^(inf*k)*n. Because 2^(ak+1) > 3^k, (2^inf*(ak+1) – 3^(inf*k)*n ~= (2^inf*(ak+1))*n

Therefore, – 3^(inf*k)*n ~= 0. Because – 3^(inf*k) is fixed, we must have a minimum value of n to be 1.

7 May, 2017 at 5:48 pm

chris3991mCorrections:

This results in (2^inf*(ak+1) – 3^(inf*k))*n. Because 2^(ak+1) > 3^k, (2^inf*(ak+1) – 3^(inf*k))*n ~= (2^inf*(ak+1))*n

Therefore, – 3^(inf*k)*n ~= 0. Because – 3^(inf*k) is fixed, we must have a minimum value of n to be 1.

7 May, 2017 at 5:51 pm

Michael M. RossBut what do you mean by the “weak” version of the conjecture?

7 May, 2017 at 6:06 pm

Michael M. RossNevermind my question. I see it’s defined above ;)

11 May, 2017 at 3:05 am

Ing. Kontra MiklosYuko one more thing to be said about your stopping time on Collatz, as i told you there is a main branch of type 4k + 1 passing by 1,5,9…… this is the only branch on which you can calculate the stopping time, but remember that i told you that on each nodes starts 2 new branches one will be again of type 4k + 1 that goes upward to infinity but in these cases there is no way to find a stopping time because all these branches that lies on the case 4k + 1 and do not belong to the main branch must pass through a randomness path.

So Concluding, there is a main branch of type 4k +1 starting at 1 and there are infinite branches of type 4k + 1 starting from each other nodes but must pass before reaching the main branch by a path wih have some randomnes nodes.

14 May, 2017 at 8:00 pm

yuko.yMaybe our approaches seem to be a little different.

But there is something similar perspectives that we have.

Actually what I saw the structure of the Collatz sequence is also not a tree.

But there is the hierarchical structure like the binary trees just as you said.

Althogh the charactaristics of the structure is not only this one.

If you have some knowledge of the database structure, it might help to find the symmetry in that binary-like branches, I think.

thank you for telling your study and advice ;)

16 May, 2017 at 2:22 pm

Miklos KontraHi Yuko, yes i know well database structure i m old enough to tell you tha t i ve a solid experience on database structure i ve start working on btrieve from Novel 3.12 where the structure were of b and b+ structure, if you think about this you ve got your way to Collatz solution where you will see that is of type of a binary structure from each node borns 2 nodes that i call in my work leaves lije in database structure that s why my thesis is in computer science and not pure math thesis, the solution to the problem is very easy and took me more than 3 years i ve start like every one using series binary numbers etc.. Nothing came out of this but if you think as a b tree structure and use logical math you ll get the answer, just be patient by the end of the year i will make my defense thesis at the university in Argentina and then upload the work, just hope that no one gets to the same result as i did, that s one of the reason why i writing in this chat to see if some one is on the same path, at the univerity they we re looking out there to see if some one had done my work before but it s seems that not, soon i will post all the results and you won t believe how easy it is and why you ll never be able to solve it using pure math, Anyway it would be wonderfull if someone out there could find another way to show that the conjecture is true, i can add one more thing and is that all the computers out there trying to prove or to find a case where it shows that s is not true will never find a case. Good luck Yuko

I would like to upload the work and ask the mathematician to find a way to show using math theory and finishing with this conjecture.

17 May, 2017 at 11:19 pm

yuko.yB tree. My mind image of the 3x+1 structure is not actually a B tree, but I see there is more similarities in our approaches.

I’ve done the generalisation of the convergence of the sets and the representration of ID for all number. So there is no randomness.

*but it’s very elementary way, so mathematicians will laugh at it when they look at it.

Those are not enough for solving the conjecture, I know. But the result of the structure is simple and interesting.

Our approaches seem to be different, but very similar I think.

so good luck, looking forward to read your paper in near future :)

11 May, 2017 at 7:41 am

Michael M. RossThere is a combinatorial rule about stopping time, which cannot be violated. I don’t know if we’re talking about the same rule:

The same first odd term (following ) recurs for , , , , and so on. All s belong to such a set. If you know the stopping time for one member of the set you know it for all.

Here’s a small table demonstrating this is true: https://qph.ec.quoracdn.net/main-qimg-cc48a7a7dfe4b957b6bd9062202cae9b.webp.

Explanation: An iterative function is going to generate composites with odd prime or composite factors multiplied by an exponent of . So, one half of the Collatz sequence is generating these or , and the other half is stripping them away. A function is going to find primes or odd composite factors, but geometrically further apart. These primes or odd composites are going to be the first terms of sequences – for example, ones that begin with .

58 = 2 * 29

232 = 2 * 2 * 2 * 29

928 = 2 * 2 * 2 * 2 * 2 * 29

3712 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 29

The reason that the stopping time increases by according to size is the two extra divisions by to strip the padding from the odd number.

P.S.

I’m following the instructions for latex formatting – forgive me if this comes out disastrously wrong. I’ve written about this subject in further detail here: https://www.quora.com/In-the-Collatz-conjecture-why-do-the-numbers-n-and-4n+1-share-the-same-Collatz-sequence/answer/Michael-M-Ross

[LaTeX repaired – one needs to put a space after $latex – T.]14 May, 2017 at 7:21 pm

yuko.yYes, It is able to define the stopping time in that case, as you said.

But your question above about a superset, I call something like the set as the parent set.

Where the one member of the set is also being as a member of the child set.

So that the sequence called the hailstone. And defining the stopping time of such superset seems to be difficult or undefinable.

It seems to be hard to prove the conjecture by showing the well-defined stopping time.

But all number have their own ID as a member of the child set. Those members of the set are well-ordered, and the parent sets are also well-ordered.

Plus, such odd number: x<f(x) can maps to the number x'≻f(x').

It's the key to all number converge 1. It is just in my opinion.

15 May, 2017 at 6:04 am

Michael M. RossThis may sound radical, but neither 3n+1 nor Powers of 2 are required to generate Collatz sequences.

There’s another type of function, call it “x-1/x+1”, that produces a proper superset of the odd numbers of each sequence. Every odd number is generated, in order, by this function – and some additional odd numbers that could not be with 3n+1. Those are multiples of 3 and prime numbers.

15 May, 2017 at 4:55 pm

yuko.yThe superset I’m thinking about is different to yours, sorry. I don’t use the 4n+1 rule.

So I could not understand clearly what your function suggests.

“every odd number is generated, in order” yes it looks right. But it could be more simplified by another way of representation, I think.

And I just follow the ordinary (called shortcut?) rule for the conjecture.

f^1+j (n) = 3(n)+1 /2^j if n = odd

f^h (n) = (n) /2^h if n = even j,h ≥ 1.

Thank you for sharing your ideas!

15 May, 2017 at 7:38 pm

yuko.ySo I mean, the function like your x-1/x+1 function could be also represented by another definition. I am not certain the function is completely the same of yours.

But your function genarates all odd number is right, then the results of the both functions must be the same.

*I am sorry for my poor explanation and bad english.

16 May, 2017 at 6:23 am

Michael M. Ross**43**, 130, **65**, 196, 98, **49**, 148, 74, **37**, 112, 56, 28, 14, **7**, 22, **11**, 34, **17**, 52, 26, **13**, 40, 20, 10, **5**, 16, 8, 4, 2, **1**

**43**, **65**, **49**, **37**, 9, **7**, **11**, **17**, **13**, 3, **5**, **1**

17 May, 2017 at 1:19 pm

Michael M. Ross(I’m sure your work with DB trees and hierarchies is far more interesting than my ideas.)

I want to address this point of the “ordinary function” as you’ve written it: It uses *3 and /2…. That’s half the problem.* What my function does is express much more precisely that there are three and only three results for every odd n:

1. If n+1 is divisible by 4, add 0.5n to n.

2. If n-1 is divisible by 8, subtract 0.25n from n.

3. If neither case applies, subtract 0.75n from n.

No surprise then that when we look at the odd ns of any sequence, values increase by half and decrease by a quarter or three-quarters:

27

41 + 0.518

31 -0.756

47 + 0.516

71 + 0.510

107 + 0.507

161 + 0.504

121 -0.751

91 -0.752

137 + 0.505

103 -0.751

155 + 0.504

233 + 0.503

175 -0.751

263 + 0.502

395 + 0.501

593 + 0.501

445 -0.75

111 -0.25

Hmm, has this regularity ever been noted for the odd ns? The sum of these values is a negative sum. The sequence terminates because of the frequency of mods 4 and 8 (and their absence).

Now it turns out that the disjoint occurrence of the moduli for x-1/x+1 eliminates the possibility of circularity because n+1 and n-1 cannot have moduli 4 and 8 for the same n. It’s one or the other (or the third condition of divisibility by 3 or 1, or a prime).

mod 4 mod 8 mod 3

27 28 0

41 40 0

31 32 0

47

71

107

161 160 0

121 120 0

91 92 0

137 136 0

103 104 0

155 156 0

233 232 0

175 176 0

263 264 0

395 396 0

593 592 0

445 444 0

111 112 0

*It’s a bad thing that this puzzle got the title the “3x+1 Problem”. It’s been rattling around in peoples’ heads too long; it even sells books. The conjecture is not the formula.

17 May, 2017 at 1:33 pm

Michael M. RossThat second list of numbers is meant to look like this: https://qph.ec.quoracdn.net/main-qimg-c8f24efd5ed20026ddb50c08aaa43de2

17 May, 2017 at 9:50 pm

yuko.ySo your x±1 function shows the odd number≢0 (mod.3) ?

If so, It would of course generates every odd number. But there is the certain rules about the indices of 2. I mean, because the generator of every odd number is the Collatz odd (multivalued) inverse mapping.

That’s why I use the shortcut function ” f^1+j= 3x+1 /2^j ” for x≔odd≢0(mod.3). I don’t deal with 3x+1 and /2^j separately.

And even is just the (multivalued) inverse mapping of odd. So even can be ignored.

Your findings:

1. If n+1 is divisible by 4, add 0.5n to n.

2. If n-1 is divisible by 8, subtract 0.25n from n.

3. If neither case applies, subtract 0.75n from n.

Actually I still could not understand cleary(..sorry that’s why I am an amatrue!) But I think it might be related the rules of the indices of 2 what I explained above.

And the mod. 4 list of 27–111, there is {27,41,31,47,71…}≡{-1,+1,-1,-1,-1…(mod.4)} Does it have any regularity of the ordering of -,+,-.. ?

Personally, I think this randomness IS undefinable.

My mind image of the 3x+1 structure, there is actually the symmetrical or fractal hierarchy (which represents the depths of the subsets of odd), but it’s not so important. There is just the permutation of the terms of odd number.

I have only four formulea which represent about the sets: Two parent sets(sueprset) and Two child sets(which converge thier parent sets). But the member of the parent sets is also being a member of the child sets… I can not explain cleary anymore.

Anyway, that sets can show almost all x≻1 is converge the number which less than x.

So, the final problem of the conjecture will be able to done If all such number; x<f^1+j(x) can be mapped to x'≻f^1+j(x'). It is just my personal opinion. ..And it can.

Our approachs are different, but I hope they will reach the same conclusion :) …I can not write the paper, though..

18 May, 2017 at 4:34 am

yuko.yThat above three results for every odd is very definite and surprising.

I can grasp a part of it but not completely a whole thing.

I’m tackling the conjecture with another way of yours, although each of them seem to describe something like the same thing, I think.

Forgive me my lack of understanding. lack of explanation, English and my rudeness.

Thanks for sharing your ideas!

18 May, 2017 at 6:08 pm

jrgDon’t think I’ve seen this function before and humbly suggest you try to prove something useful with it and that takes a lot of work! But I bet it took a lot more thinking and work to come up with this function than you perhaps realize. So to me, from an ethics point of view, that means your name, if you wished, ought to be listed as coauthor on the first published peer reviewed paper to ‘prove’ anything new or useful with it. Good luck!

19 May, 2017 at 2:18 pm

yuko.yI’m not certain that your comment is for me or Mr.Ross or someone else.

If it is to me, thanks! if not, sorry I’m embarassing..

Although I’ve found these ideas in my own way, however I found a paper by Prof. Hellekalek just yesterday. and found in there that my notion for the conjecture is almost the same to his notion. I don’t understand the paper completely because I’m an amateur, but I would like to support his study.

Here is the paper by Professor Perter Hellekalek.

https://arxiv.org/pdf/1605.02634.pdf

According to his paper, these above inverse mapping and shortcut fuction are not new. such function is called “the accelerated Collatz function” T.

I’m just an amature, so my result for the conjecture is more specific…well, what I would like to say is, there is more straightfoward formulea with numbers.

Anyway, thanks for your comment! (..if it is to me)

19 May, 2017 at 2:38 pm

yuko.yI am very sorry that if your comment is for Mr.Ross…!! His function is specific!

18 May, 2017 at 6:42 am

Michael M. RossYour English is good, you’re very polite. I think of it as a boardgame with three moves. It’s a probability game with a 100% probability that the piece will land on 1 given the moves permitted by either x-1 or x+1 being congruent 0 with Mod 8, Mod 4, or the Otherwise case (of 3, prime, or 1).

I am the ultimate amateur. It may be heresy: I don’t see this as a difficult problem. That doesn’t mean a formal proof would be easy or that there is not a lot of interesting work to be done, like yours, but from my POV I feel confident the game has only one solution.

19 May, 2017 at 3:37 pm

yuko.yI agree with you that “think of it as a boadgame.” it is the reason why I soppose that the hierarchy is not so important.

And you say “with three moves”, …Yes!! It might be the same thing to you what I see in there. but I don’t think the conjecture is a probability game, though!

Your point of veiw and the data is very exact, Thank you very much for sharing your study with us!

21 May, 2017 at 5:39 pm

chris3991mSo I’m not sure about my so-called proof, but I have a couple ideas (read if you want Dr. Tao):

1. Notice as I mentioned, in the weak Collatz conjecture, 2^(ak+1) > 3^k. Thus, if we keep repeating this cycle, the ratio (3^k)/(2^(ak+1)) keeps decreasing. Could we use this fact to somehow prove that the cycle also would have to be decreasing (or close), leaving the only option n = 1?

2. Would it be possible to find the maximum of (3^(k-1) + 3^(k-2)*2^(a2) + … + 2^(ak))/(2^(ak+1) – 3^(k)) using calculus or advanced analysis? This is beyond my knowledge, but if we could find this value, and show that every value of n below it converges to 1, we will have proven that the only possible value of n can be 1.

Chris Smith

22 May, 2017 at 2:04 am

chris3991mOne more thing to add: If you can find the maximum of number 2, I have already developed a method to prove that every odd number must converge to 1. This uses a combination of probability and algebra. Hopefully, you will be interested.

5 July, 2017 at 6:39 am

Michael M. RossFive simple ideas for untangling this loopy conjectureIdea 1Every (Collatz-type conjecture) contains an input-output loop for (where is odd). The twist is that this includes .

This is merely a factual statement because:

If then and .

It is only trivial for . Why? Because is the starting point and the endpoint of the loop.

Idea 2The even numbers can be eliminated. Let me call this the function.

Since the next even term following is half, we know that it’s also latex $1$ minus the product of the previous odd and :

For example:

and , and , and

Each smaller is one-quarter of the previous one:

For the odds:

For the evens:

Idea 3All odd-numbered sequences can be reduced to three operations of multiplication:

a.If is divisible by , multiply by , subtractb.if is divisible by , multiply by , addc.Else multiply byWe can call this the a, b, c congruence. It’s important for a number of reasons, including the fact that they are self-switching according the follow rules:

–For

a, has a minimum exponent of for multiplication by . With each product of , the exponent decreases by latex$2$.–For

b, has a minimum prime factor exponent of $latex2^4$ for multiplication by . With each product of , the exponent decreases by .–For

c, which for always has prime factors , is a class that contains the odd terminating numbers, say for :53, 13, 3,5,1.Idea 4All complex loops are determined by the congruence of two successive numbers equaling .

For example, take sequence and :

31→5, 5→13, 13→25, 25→43, 43→35, 35→29, 29→49, 49→79,79→17, 17→31There are two looping pairs: , and , because:

(mod )

(mod )

The amusing twist is that again this must be true for $latex $x = 1$. But unless the modulus is $latex $\geq 3$ this congruence-based looping cannot occur.

Idea 5The regression to occurs because of exponents of , not powers of .

As we know, powers of terminate conventional sequences. For example, to take an extreme case, the entire sequence of is:

262144, 131072, 65536, 32768, 16384, 8192, 4096, 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1

This becomes, in the sequence:

87381, 21845, 5461, 1365, 341, 85, 21, 5, 1

It’s the same pattern described above of division by , quartering in every step: .

There are no common odd numbers save one, .

(Excuse the long post.)

7 November, 2017 at 11:47 am

lz2263546927The algebraic structure of collatz conjecture：Construct the domain transformation: x = 3n + d, y = 3n-d, z = n/2. 1. d = 0, n = 0, x = 3 × 0 + 0 = 0, y = 3 × 0-0 = 0, z = 0/2 = 0. 2. d = 1, n = 0, x = 3 = 0 + 1 = 1, y = 3 × 0-1 = 1, z = 0/2 = 0. 3. If d belongs to Z, n belongs to N+, x = 3 × 1 + d, y = 3 ×1-d, z=n/2; If d belongs to Z and n belongs to N,x= 3× (-1) + d, y = 3 × (-1) -d, z = n / 2. (1) If d belongs to Z, n belongs to N+.【1】 (3 × 1 + d1-1) / 3 = (3 × 1-d1) / 2, d1 = 1; (3 × 1-d2-1) / 3 = (3 × 1 + d2) / 2 , d2 = -1. 【2】 (3 × 1 + d3) / 2 = 2 (3 × 1 + d3), d3 = 9/5; (3 × 1 + d4) / 2 = 2 (3 × 1-d4), d4 = 9/5. 【3】 3 (3 × 1 + d5) + 1 = 2 (3 × 1 + d5), d5 = 4/5; 3 (3 × 1 + d6) + 1 = 2 (3 × 1-d6) ,d6= -4 / 5. Take d = 1, then x = 4, y = 2, eavailable loop A = (4,2,1,4). According to the principle of transformation, when n = 1 satisfies 3 × 1 + 1 = 4,3 × 1-1 = 2, the circular circle F = (4,2,1,4) = A is obtained, so available loop circle(A , A). Therefore, the 3n + 1 transformation on the positive domain has only the loop A = (4,2,1,4). (2) If d belongs to Z, n belongs to N. ＜1＞ Shows that n = 1 when the transformation is equivalent to (1), then d =1, x = -2, y = -4, the loop can be obtained B = (-1, -2, -1), because -4 does not belong to B, so n = -1 does not meet the transformation principle, so take n = -2. ＜2＞【1】[3×(2)-d7-1]/3= [3 × (-2) + d7] / 2, d7 = 4/5; [3 × (-2) + d8 – 1] / 3 = [3 × (-2) – d8] / 2, d8 = -4 / 5. 【2】[3 × (-2) -d9] / 2 = 2 [3 × (-2) + d9], d9 = 18/5; [3 × (-2) + d10] / 2 = 2 [3 × (-2) -d10], d10 = -18 / 5.【3】3 [3 × (-2) – d12] + 1 = 2 [3 × (-2) + d12], d12 = -1. Eavailable loop circle C= (-5, -14, -7, -20, -10, -5), according to the transformation principle, take d =1, x= -5 and y = -7. According to the transformation principle, take n=-14. ＜3＞【1】 [3 × (-14) – d13-1] / 3 = [3 × (-14) + d13] / 2, d13 = 8; [3 × (-14) + d14-1] / 3 = [3 × (-14) – d14] / 2, d14 = -8. 【2】[3 × (-14) + d16] / 2 = 2 [3 × (-14) + d15], d15 = 126/5; [3 × (-14) + d16] × (-14) -d16], d16 = -126 / 5. 【3】3 [3 × (-14) + d17] + 1 = 2[3 × (-14) -d17], d17 = 41/5; 3 [3 × (-14) -d18] +1=2[3× (-14) + d18], d18 = -41 / 5. Take d = 8, then x = -34, y = -50, eavailable loop circl D = ( -34,- 17, -50, -25, -74, -37, -110, -55 ,-164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34), according to the transformation principle, take n = -17. ＜4＞【1】 [3×(-17)-d19-1]/3=[3 × (-17) + d19] / 2, d19 = 49/5; [3 × (-17) + d20 1] / 3 = [3 × (-17) -d20] / 2, d20 = -49 / 5. 【2】 [3 × (-17) + d22] / 2 = 2 [3 × (-17) + d21], d21 = 153/5; [3 × (-17) + d22] × (-17) -d22], d22 = -153 / 5. 【3】3 [3 × (-17) + d2] + 1 = 2 [3 × (-17) -d23], d23 = 10; 3[3 × (-17) -d24] + 1 = 2 [3 × (-17) +d24], d24 = -10. Vailable loop circle E= (-41, -122, -61, …, -41) = D, so that the loop (D, D) can be obtained by taking d = 10, then x = -41, y = -61. So the transformation of each cycle on the negative domain ends in the loop D, and the 3n + 1 transformation on the negative domain has B, C, and D 3 cycles. Conclusion: The 3n + 1 transformation on the whole domain has A, B, C, D 4 cycles.

20 November, 2017 at 8:17 pm

lz2263546927The algebraic structure of collatz conjecture：Construct the domain transformation: x = 3n + d, y = 3n-d, z = n/2。1. d = 0, n = 0, x = 3 × 0 + 0 = 0, y = 3 × 0-0 = 0, z = 0/2 = 0。 2. d = 1, n = 0, x = 3×0 + 1 = 1, y = 3 × 0-1 =-1, z = 0/2 = 0。 3. If d belongs to Z, n belongs to N+, x = 3 × 1 + d, y = 3 ×1-d, z=n/2; If d belongs to Z and n belongs to N-,x= 3× (-1) + d, y = 3 × (-1) -d, z = n / 2. (1) If d belongs to Z, n belongs to N+.【1】 (3 × 1 + d1-1) / 3 = (3 × 1-d1) / 2, d1 = 1; (3 × 1-d2-1) / 3 = (3 × 1 + d2) / 2 , d2 = -1. 【2】 (3 × 1 + d3) / 2 = 2 (3 × 1 + d3), d3 = 9/5; (3 × 1 + d4) / 2 = 2 (3 × 1-d4), d4 = 9/5. 【3】 3 (3 × 1 + d5) + 1 = 2 (3 × 1 + d5), d5 = 4/5; 3 (3 × 1 + d6) + 1 = 2 (3 × 1-d6) ,d6= -4 / 5. Take d = 1, then x = 4, y = 2, eavailable loop A = (4,2,1,4). According to the principle of transformation, when n = 1 satisfies 3 × 1 + 1 = 4,3 × 1-1 = 2, the circular circle F = (4,2,1,4) = A is obtained, so available loop circle(A , A). Therefore, the 3n + 1 transformation on the positive domain has only the loop A = (4,2,1,4). (2) If d belongs to Z, n belongs to N-. ＜1＞ Shows that n = -1 when the transformation is equivalent to (1), then d =1, x = -2, y = -4, the loop can be obtained B = (-1, -2, -1), because -4 does not belong to B, so n = -1 does not meet the transformation principle, so take n = -2. ＜2＞【1】[3×(2)-d7-1]/3= [3 × (-2) + d7] / 2, d7 = 4/5; [3 × (-2) + d8 – 1] / 3 = [3 × (-2) – d8] / 2, d8 = -4 / 5. 【2】[3 × (-2) -d9] / 2 = 2 [3 × (-2) + d9], d9 = 18/5; [3 × (-2) + d10] / 2 = 2 [3 × (-2) -d10], d10 = -18 / 5.【3】3 [3 × (-2) – d12] + 1 = 2 [3 × (-2) + d12], d12 = -1. Eavailable loop circle C= (-5, -14, -7, -20, -10, -5), according to the transformation principle, take d =1, x= -5 and y = -7. According to the transformation principle, take n=-14. ＜3＞【1】 [3 × (-14) – d13-1] / 3 = [3 × (-14) + d13] / 2, d13 = 8; [3 × (-14) + d14-1] / 3 = [3 × (-14) – d14] / 2, d14 = -8. 【2】[3 × (-14) + d16] / 2 = 2 [3 × (-14) + d15], d15 = 126/5; [3 × (-14) + d16] × (-14) -d16], d16 = -126 / 5. 【3】3 [3 × (-14) + d17] + 1 = 2[3 × (-14) -d17], d17 = 41/5; 3 [3 × (-14) -d18] +1=2[3× (-14) + d18], d18 = -41 / 5. Take d = 8, then x = -34, y = -50, eavailable loop circl D = ( -34,- 17, -50, -25, -74, -37, -110, -55 ,-164, -82, -41, -122, -61, -182, -91, -272, -136, -68, -34), according to the transformation principle, take n = -17. ＜4＞【1】 [3×(-17)-d19-1]/3=[3 × (-17) + d19] / 2, d19 = 49/5; [3 × (-17) + d20 1] / 3 = [3 × (-17) -d20] / 2, d20 = -49 / 5. 【2】 [3 × (-17) + d22] / 2 = 2 [3 × (-17) + d21], d21 = 153/5; [3 × (-17) + d22] × (-17) -d22], d22 = -153 / 5. 【3】3 [3 × (-17) + d2] + 1 = 2 [3 × (-17) -d23], d23 = 10; 3[3 × (-17) -d24] + 1 = 2 [3 × (-17) +d24], d24 = -10. Vailable loop circle E= (-41, -122, -61, …, -41) = D, so that the loop (D, D) can be obtained by taking d = 10, then x = -41, y = -61. So the transformation of each cycle on the negative domain ends in the loop D, and the 3n + 1 transformation on the negative domain has B, C, and D 3 cycles. Conclusion: The 3n + 1 transformation on the whole domain has A, B, C, D 4 cycles.

14 June, 2018 at 8:03 am

juststudentwhat if 0 is natural number?

14 June, 2018 at 11:45 am

VincentA bit late to the party here, but I am confused by the statements

“As a crude heuristic, one expects that for a “random” such choice of integers, the expression (1) has a probability 1/q of holding for some integer n. (Note that q is not divisible by 2 or 3, and so one does not expect the special structure of the right-hand side of (1) with respect to those moduli to be relevant.”

that appear just above equation (6). As far as I can see the first sentence in the quote is the first place where the number q is introduced and so the properties of q mentioned in the second sentence should be obvious from this very implicit definition? But I have no idea how to derive any properties of q from this definition as the reciprocal of some ‘heuristic’ probability. For all I know it is not even an integer. Am I missing something? Can the equality that appears somewhere further down be taken as the definition instead?

14 June, 2018 at 12:32 pm

michaelmrossOne can confidently say that 90% of the words expended on this conjecture are hot air, no matter the oracular elevation. I congratulate you on calling the kettle black.

16 July, 2018 at 6:27 pm

shugui xuProof of Collatz Conjecture(3N+1)

https://weibo.com/6058390182/profile?rightmod=1&wvr=6&mod=personnumber&is_all=1#_rnd1531793858470