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.

## 131 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 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.

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).

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.