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.

## 329 comments

Comments feed for this article

16 December, 2019 at 1:45 am

Giįŗ£ thuyįŗæt 3n+1 | REDSTAR-BLOG DĆNH CHO TOĆN[…] hį»c ÄĘ°Ę”ng Äįŗ”i.” Terence Tao cÅ©ng Äį»ng Ć½ vį»i quan Äiį»m trĆŖn trong bĆ i blog nÄm 2011 cį»§a […]

13 September, 2022 at 11:39 am

Anonymous6/2=3, odd

16 December, 2019 at 4:13 am

JoaoHi. It all cames down to n/2. Because if the number is odd it becomes an even number in the first operation. And if a number is even you divide by 2. Any even number divided by 2 results in a even number, exeption being 2 which results in 1. So all calculations in sequence for n/2 will end in 1. And 1 will be transformed in a even number and so we are back to n/2 resulting in 1 in a cycle. So we can be sure collatz results allways in 1. This reasoning may not mathematicaly prove it, I dont know mathematics enough to understand where I am making my leap of fate, but it sure made it seem unecessary to try to find and exeption by brute force computing. Finding that exception would disporve it, right? But there will not be one.

5 August, 2021 at 4:48 am

Klaus MĆ¶dingerEach uneven number multiplied by 2 gives an even number. So there is an infinite amount of even numbers which, divided by 2, result in an odd number.

17 November, 2021 at 12:24 pm

GastĆ³n Fernando Murillo PlĆŗasTu deducciĆ³n es razonable pero el problema que se pide resolver no es ese pues el algoritmo sigue los pasos que hasta que no se obtiene un resultado de 1 no se detiene. Es decir que se cuestiona si existe un nĆŗmero que utilice el algoritmo de forma infinita que nunca se pueda detener (Ć³rbitas no acotadas) y si no existe otra Ć³rbita recursiva diferente a 4-2-1. Si no existen estas 2 situaciones se entiende que el algoritmo siempre llega a 1 y como dije eso no es de lo que se duda y por lo tanto no se pide una demostraciĆ³n orientada en esa direcciĆ³n.

17 November, 2021 at 12:34 pm

GastĆ³n Fernando Murillo PlĆŗasYour deduction is reasonable but the problem that is asked to solve is not that because the algorithm follows the steps that until a result of 1 is obtained it does not stop. In other words, it is questioned whether there is a number that the algorithm uses infinitely that can never be stopped (unbounded orbits) and whether there is no other recursive orbit other than 4-2-1. If these 2 situations do not exist, it is understood that the algorithm always reaches 1 and as I said that is not in doubt and therefore a demonstration oriented in that direction is not requested.

16 December, 2019 at 1:46 pm

Comments and Collatz Conundrum – Matt Mullenweg[…] Medal-winning mathematician considered one of the best of his generation, got an anonymous comment on his WordPress blog post from 2011 exploring the Collatz conjecture ā one of the most persistent problems in math ā suggesting he explore the problem for […]

16 December, 2019 at 3:34 pm

Mathematician Terence Tao Cracks a āDangerousā Problem – My Blog[…] this past August an anonymous reader left a comment on Taoās blog. The commenter suggested trying to solve the Collatz conjecture for āalmost allā numbers, […]

16 December, 2019 at 10:30 pm

Matt: Comments And Collatz Conundrum - RSSFeedsCloud[…] Medal-winning mathematician considered one of the best of his generation, got an anonymous comment on his WordPress blog post from 2011 exploring the Collatz conjecture ā one of the most persistent problems in math ā suggesting he explore the problem for āalmost […]

18 December, 2019 at 8:30 am

Mathematician Terence Tao Cracks a āDangerousā Problem - CLICK NOW[…] this past August an anonymous reader left a comment on Taoās blog. The commenter suggested trying to solve the Collatz conjecture for āalmost allā numbers, […]

20 December, 2019 at 9:37 am

Marco MagaA “9n+1” problem would be easier to solve?

21 December, 2019 at 12:19 am

zhihao81In order to solve the issue, you might like to use the method of a hologram and taoist concept.

https://www.learnreligions.com/tao-te-ching-verse-42-3183165

You should have noted that odd numbers have a longer lifespan-taoist call them Yang numbers, while even numbers have a shorter lifespan(yin numbers).

21 December, 2019 at 12:33 am

zhihao81You can combine the hologram concept with taoist philosophy to prove the validity of 3x+1.

Taoist are highly sensitive to numbers.

You should have observed by now that odd numbers last longer than even numbers. Taoists call odd number Yang, even numbers yin.

https://www.learnreligions.com/tao-te-ching-verse-42-3183165

Remember that many philosophies mention that so above, as below(universe is holographic).

23 December, 2019 at 9:07 am

Peng Yu (@unameit8626348)n can be even or odd, \vec{n} = (2k, 2k+1). f(\vec{n}) = (k, 3k+2).

we can use a 2×2 matrix A = { {1/2, -1/2}, {0, 2} }, to implement f(\vec{n})= F(\vec{n}) = A * \vec{n} . to prove F(\vec{n}) always converge to (1, 0). we only need to study the convergence of A . which has eigenvalue (2, -1/2).

from the Jordan normal form, A won’t converge.

23 December, 2019 at 9:48 am

Peng Yu (@unameit8626348)nvm… this linear function only applies to the first step :(

28 December, 2019 at 12:50 am

Comments and Collatz Conundrum ā Matt Mullenweg | Wordpress Tutorials[…] Medal-winning mathematician considered one of the best of his generation, got an anonymous comment on his WordPress blog post from 2011 exploring the Collatz conjecture ā one of the most persistent problems in math ā suggesting he explore the problem for āalmost […]

3 January, 2020 at 9:49 am

iiiduncaniiiI don’t know, maybe it’s just me, I think all these attempts to prove this conjecture, is just a bunch of people trying to show off their advanced math skills. The problem starts as 2 simple statements. The only argument you can make that you can’t prove every number will eventually fall to the 4-2-1 loop is because of 1) the amount of time it would take a person to one by one try every possible number to infinity and 2) the limitation on computers to find an answer. Sad story is that computers will never reach infinity no matter how powerful they become. I guess this would mean this conjecture will never be proven. To me though proving this conjecture to not fall to 4-2-1 loop would be like saying try to find 2 numbers x and y where y=x-1 and they are both divisible by 3. Well start using computers until you find that number! I am sure someone out there would attempt this. Probably the same one/ones who try to prove that 1=2 or that infinity =12 or that need 300 pages to prove 1+1=2 (consider that it took Einstein 46 pages to show the theory of relativity).

15 January, 2020 at 7:40 am

GastĆ³n Fernando Murillo PlĆŗasIt’s true, you don’t know it.

19 January, 2020 at 5:29 pm

Zahlentheorie: Das Collatz-Problem, Sirenengesang fĆ¼r Mathematiker – Multilingual Scrapper[…] sollte sich Ć¤ndern, als im AugustĀ 2019 ein anonymer Leser einen Kommentar auf Taos Blog hinterlieĆ. Darin schlug er vor, das Problem nicht allgemein anzugehen, sondern es […]

19 January, 2020 at 5:43 pm

Number theory: The Collatz problem, siren singing for mathematicians - 2NYZ.com[…] ‘d change when in aug 2019 an anonymous reader a comment on tao’s blog. in it, he suggested that the problem ‘d not be tackled in general, […]

2 July, 2020 at 1:09 pm

AnonymousIs it possible to to get a nontrivial separation between power of 2 and 3 by some (specifically designed) sieve method (as was done for twin primes)?

7 July, 2020 at 5:34 pm

Terence TaoI doubt sieving methods are effective for capturing such extremely sparse sets of numbers as powers of 2 and 3; the tools that have proven to be effective for such problems (transcendence theory and diophantine approximation, mostly, and potentially also arithmetic geometry) are quite different from sieve methods.

7 July, 2020 at 1:25 pm

David SYou can use Ellison’s estimate, $|2^x-3^y| \geq 2^x e^{-x/10}$, which holds for $x \geq 12$ with $ x \neq 13, 14, 16 19, 27$ and all $y$. This is based on results by Pillai and Baker. Reference: “WJ Ellison, On a theorem of S. Sivasankaranarayana Pillai, SĀ“eminaire de thĀ“eorie des nombres de

Bordeaux, 1970 (1971), pp. 1ā10.”

9 July, 2020 at 8:32 am

dablerThis post is to let you know that the limit has been raised to which Collatz problem is computationally verified, and at the moment it is 2^68.

Reference: D. Barina. Convergence verification of the Collatz problem. The Journal of Supercomputing, 2020. DOI: 10.1007/s11227-020-03368-x URL: https://rdcu.be/b5nn1

10 July, 2020 at 11:21 am

AnonymousThe reduction of the Collatz iteration into simpler bit operations may indicate the possibility to prove the Collatz conjecture by a similar (entropy based) technique as recently done in the solution of Erdos discrepancy problem.

2 August, 2020 at 9:36 am

mugbuffIt is a fact that you can list all the integers that converge to any integer for up to 6 levels (i. 6 iterations of 3n+1) above that integer without any possibility of a loop. You can then go 6 levels above each integer at those 6 levels, effectively going 12 levels up and so on to infinity. Thus no loop is possible.

A reverse of the argument precludes an endless process.

12 August, 2020 at 5:02 pm

Li JiangThe essence of the 3x+1 conjecture is the iterative operation of odd numbers. It is known from the basic theorem of arithmetic: the number of factors with a value equal to 2 in each even number is determined for the even number, so an iterative operation for odd numbers x can be defined, that is:

, (where is the number of factors whose value in is equal to 2), the result of the operation is still odd number.

According to this definition, the general formula for odd continuous iteration can be derived, that is

(where )

From this, if the odd continuous iteration may cause loops, then we can deduce the equation that

Solving this equation can get the result that the equation has no positive integer solution except 1, which indicates that continuous iteration cannot cause a loop.

On the other hand, the odd-number continuous iterative formula can be transformed into a linear indefinite equation.

(where )

The process of solving the equation reveals that it is impossible for odd numbers to reach infinity through iterative operations. Therefore, all odd numbers will return to 1 after a limited number of iterations.

By extending this result to even numbers, it can be determined that all positive integers will return to 1 after a finite number of iterations, which fully proves the 3x + 1 conjecture.

My article The Collatz conjecture and linear indefinite equation is in the following website

http://www.sciepub.com/tjant/content/8/2

12 August, 2020 at 5:20 pm

Li JiangCorrection:

12 August, 2020 at 11:26 pm

Antoine DeleforgeDear Li Jiang,

The flaw in your paper is that you omit that, according to your own definitions, both a and g depend on x. Hence your “linear equation” in x is in fact not a linear equation. It is very non-linear, and unsolvable with current techniques.

Best regards,

Antoine

13 August, 2020 at 2:51 am

Li JiangDear Antoine Deleforge,

That’s right, because both a and g depend on x, so as parameters, for every certain x, a and g are certain. The linear equation here is a linear indefinite equation, and the value of the parameter does not affect the linear relationship between Y and x.

Best regards,

Li Jiang

13 September, 2020 at 10:33 pm

Lyndon ClarkeI have failed the years of contour integration over multi-dimensional manifolds. I think it is perhaps provable that this problem is unprovable.

25 September, 2020 at 9:16 am

Dick PountainI’ve been doing computational experiments on Collatz sequences, and have found something approaching a power-law relationship between successive numbers with peak Collatz heights: height appears roughly proportional to seventh root of the number. Not exact, subject to random noise, but roughly constant magnitude. A sample:

N Collatz height N N^ā ā / height (x100)

156159 382 1.44502

216367 385 1.50213

230631 442 1.32041

410011 448 1.41432

511935 469 1.39453

626331 508 1.32510

837799 524 1.33915

1117065 527 1.38739

1501353 530 1.43905

1723519 556 1.39907

2298025 559 1.44995

3064033 562 1.50271

3542887 583 1.47895

3732423 596 1.45750

5649499 612 1.50598

6649279 664 1.42073

8400511 685 1.42395

11200681 688 1.47722

14934241 691 1.53251

15733191 704 1.51545

Is this sort of stuff of interest to anyone, or any group?

25 September, 2020 at 10:50 am

AnonymousNo.

25 September, 2020 at 9:32 am

Dick PountainOops, doesn’t like my tabs

N Height N Nā ā / Height

156159 382 1.44502

216367 385 1.50213

230631 442 1.32041

410011 448 1.41432

511935 469 1.39453

626331 508 1.32510

837799 524 1.33915

1117065 527 1.38739

1501353 530 1.43905

1723519 556 1.39907

2298025 559 1.44995

3064033 562 1.50271

3542887 583 1.47895

3732423 596 1.45750

5649499 612 1.50598

6649279 664 1.42073

8400511 685 1.42395

11200681 688 1.47722

14934241 691 1.53251

15733191 704 1.51545

21 October, 2020 at 11:04 am

Hashem salarvand rostamyHi

Mr. Terry Tao

I have good news for the world’s mathematicians.

The collatz conjecture was proved.

I endured many hardships and insomnia to prove this extremely difficult conjecture.

When I was 19 years old, I proved a theorem that allowed me to logarithmize numbers directly on a random basis with a regular calculator that could only do multiplication and division. And I did this without using math series. And for some reason I never sent an article about it.

Until in 2018, I stumbled upon the issue of Kolatz’s conjecture. I immediately began my research on this conjecture, and on October 18, 2020, I finally succeeded in proving the Kolatz conjecture mathematically and logically. And I ended the myth of the 83-year-old unsolvable mystery.

I do not want to have my own 19-year-old problem, and I strongly want this method of proof to be registered in my name and to keep the results available to me.

I disagree with this article and can only prove Kolatz’s conjecture live at a math conference or an online webinar in the presence of several mathematicians at the University of Los Angeles or another university at your suggestion and in the presence of several reporters.

I currently live in Iran, Lorestan province, Doroud city, Andisheh neighborhood. And I sent you a message from here.

Hoping to meet in Los Angeles

Ł Ł Ų§Ų² Ł ŲŖŲ±Ų¬Ł ŚÆŁŚÆŁ Ų§Ų³ŲŖŁŲ§ŲÆŁ Ś©Ų±ŲÆŁ

Ł ŁŲŖŲøŲ± Ų¬ŁŲ§ŲØ Ų“Ł Ų§ ŁŲ³ŲŖŁ

Ł ŁŁŁ ŲØŲ§Ų“ŪŲÆ

25 October, 2020 at 9:38 pm

Rafael LealOne thing that I noticed is that at first the numbers seem to climb up (increase) and the number gets bigger and bigger. However, eventually you will get a number that will start a sequence of long even numbers, which means the number decreases in value rather rapidly. Then, the number will continue to increase, but this will happen less and less frequently and the long even sequences will occur more often and often. It seems to me that one trick is to figure out how long will it take a number to reach a point where a long sequence of even numbers will occur. And, then how long will it be to the next cycle and so on. This process of decreasing by half is quick once you start encountering the long even sequences. It becomes clear that the cycles of even numbers increase in frequency (and length) over time while the cycles of odd numbers decrease in length and frequency as well. It follows that the probability that this n number will reach a long number that has already been proven to reach 1 will increase over time. The trick would be to choose a long number and using computers (like Charity Engine) prove that it will reach 1. Then choose an even longer number and prove that it will reach any of the results of the smaller number that reached 1. I would probably choose a handful of numbers to show that this is true of all numbers.

26 October, 2020 at 7:00 am

markmcaNot sure my previous reply worked, but you’re welcome to use our grid for free if it helps. We are very fond of helping pure maths projects that (supposedly) have no “value”. Cheers, MMcA

29 December, 2020 at 6:46 am

BillObservation 1: If this problem has been solved for all numbers up to a certain number, then it should be easy to demonstrate that all even numbers up to double that number will also eventually lead to 1. That’s because the first step would be to divide the starting number in half, thus reaching a number that has already been shown to lead to 1.

Observation 2: If in the sequence, you hit on a power of 2, it will lead to 1 very quickly.

I’m sure I’m not the first one to think of this, but thought I’d share.

21 February, 2021 at 2:29 pm

Anonymous1. I’ve altered 3n+1 to run as 3n+K, where K is odd and greater than 2. Much failure due to trapped inside infinite loops. With K=1 there are no infinite loops and all go to 1. I see why with K=1 there are no infinite loops b/c all new generated values from 3n+1 fall between previous generated values.

2. Analyzed 3n+1 ST to see the numbers that have the same ST (grouping)

ST 2^n

————

1 2

2 4

3 8

4 16

5 32 5

6 64 10

7 128 21 20 3

8 256 42 40 6

9 512 85 84 80 13 12

10 1024 170 168 160 26 24

11 2048 341 340 336 320 53 52 48

12 4096 682 680 672 640 113 106 104 96 17

13 etc etc

3. Have you tried running 3n+1 just on a subset on numbers like all numbers evenly divisible by P, where P is Prime?

23 February, 2021 at 9:20 pm

Anonymousops… must have steps on toes. I’ll stay off your blog. But you problem is NOT n/2, it’s 3n+1.

21 February, 2021 at 11:47 pm

Ngandji TedQuiconque crains ou vĆ©nĆ©re une incertitude fini par l’assimiler Ć Dieu. VĆ©nĆ©rez donc comme tel quiconque dĆ©masquera ce faux Dieu.

La conjecture de Syracuse n’est rien d’autre qu’un enfant turbulent qui se prend pour Dieu.

3 March, 2021 at 9:49 am

NotlikeireallyknowOver thinking it.

Doesnāt matter what number it is, the fact that you add +1 to an odd makes it even. In a decimal system, , once you hit a multiple of 10, it will end the sequence. Since both equations results in an even number and we are working in a decimal system, the equation on each calculation has a 1/5 chance of hitting that magical 0 but because we work in a decimal system, it is guaranteed to hit that magical 0 because 2 is the basis of all even numbers so in an infinite sequence, it will always work out in a decimal system

5 March, 2021 at 3:18 pm

RobertUse Base 6. Let that do the heavy work.

Checkout the last digits in the numbers base 6.

I believe:

1) numbers ending in zero only occur at branch tips unless preceded by a zero

2) numbers ending in 3 only occur once, following a zero or on a branch tip and followed by a number ending in 4

3) numbers ending in 5 always followed by 4

4) numbers ending in 2 always followed by 4

Interesting patterns and long increased values are produced by 55base6 or 555base6 or 5555base6 etc.

This may illustrate some of the underlying mechanisms.

I haven’t realized any relationship between the modulo 2 to recognize even numbers with the 3 used as the multiplier and 1 as an additive. There might be some reason that it works because 2 and 3 are relatively prime and have a difference of 1.

Good hunting.

Robert

25 March, 2021 at 8:33 am

Links – Pug Charlie's Blog[…] hello […]

25 April, 2021 at 12:14 am

Naman TenguriyaI’ve tried to prove collatz conjecture and I don’t think it is incorrect. What should I do…š¤

26 April, 2021 at 12:26 am

hashemmathHi

Today I am trying to submit the first article on collatz conjecture to a journal of the American Mathematical Society.

What made the Collatz problem confusing and Unproven was the unpredictability of the number of steps divided by two.

I got formulas for calculating the exact number of “divisibles” and the exact number of “triples plus one”.

Which are in fact the reasons for proving collatz conjecture.

If the American Mathematical Society accepts my article, then wait for the good news in mathematics.

Thanks

26 April, 2021 at 1:04 pm

AnonymousGo to a dungeon and don’t come out until you prove it.

2 May, 2021 at 2:43 am

AnonymousYou should read https://frankheyne.de/collatz

There is an amazing new view at the Collatz conjecture, which might be quite eye opening. And there is the proof that when the Collatz conjecture would be wrong, there should be an infinite number of different paths not leading to 1.

It is in German language, though.

12 May, 2021 at 4:31 pm

Bob-8000https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/

The above article mentioned that you encountered some sort of skewing. Could this be related to prime numbers? At least to me it seems like one always ends up with a prime-number after one repeated the divide by two steps reaching an uneven number.

5 August, 2021 at 12:04 am

WalterDr. Tao,

I have found families of Collatz type conjectures that may be of interest to you.

For any integer n >= 2, each n has a family of conjectures. Starting with initial value X, the sequences for each member in the family of n will eventually reach 1.

Rule set for generating the sequences for each family member of n with starting value X and positive integer k:

1. If X is divisible by n then the next value of the sequence is X/n

2. If X is not divisible by n then the next value of the sequence is (n^k)*X + n^k

I have written python programs that tested several values of n. Some of the values of n tested were 2, 3, 5, 6, 7, 10, 11, 13, 16, 101, and 210. For each of these n values, the values of k tested were 1, 2, 12, and 22. The sequences with starting values X that were tested all eventually reached 1.

Sorry if this was an inappropriate place to post the conjectures. I wasn’t sure how to address this.

6 August, 2021 at 5:13 am

WalterOn reflection. The construction above is trivially true. My bad

6 August, 2021 at 5:38 am

ĪĻĪ½ĻĻĪ±Ī½ĻĪÆĪ½ĪæĻ ĪĪæĻ ĻĪæĻ Ī¶ĪÆĪ“Ī·ĻAs professor Kontorovich said, it’s unlikely that more progress will be made to this problem. There are so many problems out there for people to try…

15 August, 2021 at 5:25 am

Giovanni Di SavinoThe Collatz conjecture. We take any whole number, if it is even we divide it by two, if it is odd we multiply it by three and add one unit to the result. Repeating this algorithm, after a certain number of steps, one always obtains 1. It is trivial to think of being able to represent or verify all integers that are infinite but Collatz applying a 3 * n + 1 algorithm, to each of the infinite integers, obtains l ‘nth odd number that generates the result of a power of 2 ^ n_pari which, by halving it for a known number of steps, we obtain 1. pdf of the display and simulation of the pdf how, when and why in https://www.facebook.com/groups/280310948785723

Dott: Cinzia Di Savino

student: Silvana Di Savino

75 enne: Giovanni Di Savino

17 November, 2021 at 12:17 pm

GastĆ³n Fernando Murillo PlĆŗasTu deducciĆ³n es razonable pero el problema que se pide resolver no es ese pues el algoritmo sigue los pasos que hasta que no se obtenga un resultado de 1 no se detiene. Es decir que se cuestiona si existe un nĆŗmero que utilice el algoritmo de forma infinita que nunca se pueda detener (Ć³rbitas no acotadas) y si no existe otra Ć³rbita recursiva diferente a 4-2-1. Si no existen estas 2 situaciones se entiende que el algoritmo siempre llega a 1 y como dije eso no es de lo que se duda y por lo tanto no se pide una demostraciĆ³n orientada en esa direcciĆ³n.

17 November, 2021 at 12:35 pm

GastĆ³n Fernando Murillo PlĆŗasYour deduction is reasonable but the problem that is asked to solve is not that because the algorithm follows the steps that until a result of 1 is obtained it does not stop. In other words, it is questioned whether there is a number that the algorithm uses infinitely that can never be stopped (unbounded orbits) and whether there is no other recursive orbit other than 4-2-1. If these 2 situations do not exist, it is understood that the algorithm always reaches 1 and as I said that is not in doubt and therefore a demonstration oriented in that direction is not requested.

29 December, 2021 at 7:58 am

GastĆ³n MurilloIt is not necessary to process all the numbers. There are limits that can give a general solution, so a test is requested to show that all the orbits are bounded.

15 December, 2021 at 2:20 am

sacirisiWith the Collatz algorithm it is not possible to process all natural numbers because we do not know: quantities and values āāof even and odd numbers and all their factors. From Tartaglia’s triangle we can detect odd numbers which are the sum of the results of the infinite powers of 2 which have an even index and which are also equal to the previous odd * 4 + 1. These are all the odd numbers that * 3 + 1 generate an even number that is the result of a base power 2 and even index 2 ^ (2 * nā„1) and that, the nth half, ends at 1 because Ā½ of 2 ^ 1 = 2 ^ 0 = 1. https://vixra.org/abs/2112.0004

24 August, 2021 at 11:28 pm

Wulf RehderRephrase the Collatz Conjecture: If m is the number of multiplications by 3 and m+k die number of divisions by 2 at index N=m+m+k of a Collatz sequence, then the sequence reaches its stopping time at N (i.e. the first time the sequence dips below its starting value) iff 2^(m+k) divided by 3^m is larger than 1 at this N for the first time, i.e., here the powers of 2 āwin outā for the first time. Taking logs, this happens beyond the threshold t= [log3/log2]/[log3/log2+1]=0.613147ā¦ for every Collatz sequence, regardless of starting value. Therefore: For a sequence, find the index N=m+m+k where the ā2-densityā d=(m+k)/N exceeds t for the first time: this N is the stopping time. If in a sequence no d exists that exceeds t, then the Conjecture fails. No such sequence has been found.

25 August, 2021 at 3:20 pm

āā°ā¬Ć āāāBonjour

27=3.2Ā²āŗĀ¹ + 2Ā²-1

31=0.2āµāŗĀ¹ + 2āµ-1 …

121, 91, 103, 175, 445, 167, 283, 319, 911, 577, 433, 325, 61, 23, 5, 1

Amicalement

16 November, 2021 at 1:10 pm

āā°ā¬Ć āāāBonjour

00.2āµāŗĀ¹ + 2āµ-1=_31_______011111

01.2ā“āŗĀ¹ + 2ā“-1=_47______101111

04.2Ā³āŗĀ¹ + 2Ā³-1=_71____1000111

13.2Ā²āŗĀ¹ + 2Ā²-1=107___1101011

40.2Ā¹āŗĀ¹ + 2Ā¹-1=161_10100001

\\x=r.2^{n+1}+2^{n}-1\\

3x+1\\

=3.(r.2^{n+1}+2^{n}-1)+1\\

=3.r.2^{n+1}+3.2^{n}-2\\

(3x+1)/2\\

=3.r.2^{n} +3.2^{(n-1)}-1\\

=3.r.2^{n} +2^{n}+2^{(n-1)}-1\\

=(3.r+1).2^{n}+2^{(n-1)}-1\\

Converge vers 4X+1 successeur 3X+1

161=4.40+1 -> 3.40+1=121

5,9,13,17, 21, 25…

{3,5}

{9}

{13}

{7, ā¦, 17}

{21}

{25}

{19,29}

{33}

{37}

{27,41}

{45}

{49}

{15, ā¦ , 53}

etc…

3x+1=2x+x+1

si

1.x=010101

2x =101010

3x =111111

3x+1=1000000 nombre de divisions par 2

Amicalement

16 November, 2021 at 1:13 pm

āā°ā¬Ć āāādĆ©solĆ©

31 August, 2021 at 6:31 pm

Eric WatsonHere is my work that I have done to see if I could prove the Collatz conjecture. Let me know what you think of this work. To some it may seem elementary. To me it is only the beginning of a wonderful journey.

Summary: The Collatz conjecture deals with sequences that are defined in the following manner: Begin with any positive integer x. You will get each value from the previous term according to the following rules: If your previous value is even, the next term is half of the previous term. If the previous value is odd, the next term will be three times the previous value plus one. The conjecture made is that no matter what value of x, the sequence will always reach 1.

Rules of the Collatz Conjecture:

Rule 1: f(x) = 3x + 1 for odd number, x = 2k + 1 for k = 0, 1, 2, 3,… for the sequence of odd numbers.

Rule 2:f(x) = x/2 for even number, x = 2k + 2 for k = 0, 1, 2, 3,… for the sequence of even numbers.

Conjecture: Choose any positive integer, x. If it is odd plug into Rule 1. Else, if it is even plug into Rule 2. No matter what initial value you start with, the sequence will always reduce down to 1.

Step 1: Rewrite Rule 1, and Rule 2 in terms of the sequences for odd, and even numbers.

Rule 1: f(x = 2k + 1) = 3(2k + 1) + 1 = 6k + 3 + 1 = 6k + 4 = 2(3k + 2)

Rule 2: f(x = 2k + 2) = (2k + 2)/2 = k + 1

Step 2: Generate ordered pairs to graph out on the xy-plane.

Example – For k = 0, Rule 1 gives 4, and Rule 2 gives 1 so the ordered pair would be (4, 1). Here is what I found for the values of k from zero, to 101.

k X-values Y-values

0 4 1

1 10 2

2 16 3

3 22 4

4 28 5

5 34 6

6 40 7

7 46 8

8 52 9

9 58 10

10 64 11

11 70 12

12 76 13

13 82 14

14 88 15

15 94 16

16 100 17

17 106 18

18 112 19

19 118 20

20 124 21

21 130 22

22 136 23

23 142 24

24 148 25

25 154 26

26 160 27

27 166 28

28 172 29

29 178 30

30 184 31

31 190 32

32 196 33

33 202 34

34 208 35

35 214 36

36 220 37

37 226 38

38 232 39

39 238 40

40 244 41

41 250 42

42 256 43

43 262 44

44 268 45

45 274 46

46 280 47

47 286 48

48 292 49

49 298 50

50 304 51

51 310 52

52 316 53

53 322 54

54 328 55

55 334 56

56 340 57

57 346 58

58 352 59

59 358 60

60 364 61

61 370 62

62 376 63

63 382 64

64 388 65

65 394 66

66 400 67

67 406 68

68 412 69

69 418 70

70 424 71

71 430 72

72 436 73

73 442 74

74 448 75

75 454 76

76 460 77

77 466 78

78 472 79

79 478 80

80 484 81

81 490 82

82 496 83

83 502 84

84 508 85

85 514 86

86 520 87

87 526 88

88 532 89

89 538 90

90 544 91

91 550 92

92 556 93

93 562 94

94 568 95

95 574 96

96 580 97

97 586 98

98 592 99

99 598 100

100 604 101

Step 3: Graph the ordered pairs you generate, and find that the equation of the line you get is y = x/6 + 1/3.

Step 4: Make some observations.

Observations:

A. The y-values for this equation are always one greater than chosen k-value, (where k = 0, 1, 2, 3,…).

B. The smallest y-value is y = 1.

C. The smallest x-value is x = 4.

D. The x-values increase by six each time (4, 10, 16, 22, 28, 34, 40,…)

Step 5: What happens when you plug in y = k + 1 (even-values), and x = 2(3k + 2)(odd values) into y = x/6 + 1/3?

y = x/6 + 1/3

k + 1 = 2(3k + 2)/6 + 1/3

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

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

k + 1 = (3k + 3)/3

k + 1 = 3(k + 1)/3

k + 1 = k + 1

1 = 1

No matter what value we choose for k (k = 0, 1, 2, 3,…), the sequence will always reach 1 for y = x/6 + 1/3.

9 November, 2021 at 11:49 pm

AnonymousDr. Tao,

On this conjecture,I have a new idea. I have finished an articale in chinese.Can I email it to you?

19 November, 2021 at 6:56 pm

Andrew Croftre Collatz using Syracuse odd numbers only, I note that the cases where N mod 8 is 3 or 7 then the next item is (3N+1)/2 and when N mod 8=1 then next item (3N+1)/4. Only when N mod 8=5, do we potentially have multiple divide by 2s. However when N mod 8=5, the following number in the sequence is the same for N or (N-1)/4. For example 29 and 117 both have 11 as the next number in the sequence. For purpose of demonstrating solution to 1 to the non-mathematicians, it would be clearer to amend Collatz sequence for N mod 8=5 to use (N-1)/4, and then resume as normal. Point being that it really highlights just how stacked the deck is, to stay away from the attractor for any period of time one needs >3 cases where N mod 8 is 3 or 7 for every case where N mod 8 equals 5 … which we see for a while with 27, but eventually not.

25 November, 2021 at 9:25 am

AnonymousCan the Mandelbrot set be used to test Cllatz conjecture? or do the numbers generated by Cllatz conjecture form a Bifurcation diagram?

— I’m not a mathematician just curious

26 November, 2021 at 4:02 am

AnonymousThe formula (1) from conjecture 3 works for negative cycles ?

14 December, 2021 at 7:33 pm

Dennis EstensonI came across your website because I recently decided to try to prove the Collatz conjecture. I found it really boils down to one fairly easy to prove statement. The next odd number in the sequence cannot grow by more than 1 binary digit, and often shrinks by more than one binary digit, and there are no sequences that only grow. One can build a seed that grows an arbitrary number of digits, but no finite seed will cause the sequence to grow forever.

5 May, 2022 at 5:41 pm

A Method to Not Prove the Collatz Conjecture - good fibrations[…] theory is the cocaine of mathematics. The following resulted not from my intention to prove the conjecture, but from the drive to deeply understand its underlying […]

18 May, 2022 at 6:43 pm

AnonymousCollatz looks like a decision tree. I wonder if thereās any dimensional relation with Riemannās.

Also, on a graph, a Collatz sequence looks like the collapse of a particle wave function.

5 August, 2022 at 3:19 am

Alberto IbaĆ±ezHello everyone. Here again trying to help to find the solution to the conjecture.

WE START FROM THE IDEA THAT THE CONJECTURE IS EQUIVALENT TO that for all n odd

where is a positive value of the form(8)

where k is the number of times you multiply by 3 and k+y is the number of times you divide by 2

then there are infinite solutions for and , and ,…

So, how do you find infinite solutions to this equation? Well, I really don’t know, but this is what I have observed.

If there is a solution for

then it exists

(Important note. Perhaps here we are already assuming the truth of the conjecture and everything else is meaningless)

such that

then

and

then

…

So at this point, one might ask if for all odd and there is a value or some other type of relationship or restriction such that there are infinite solutions and establish the validity of the conjecture .

I hope it is of some interest. Thanks

19 September, 2022 at 8:10 am

Leszek MazurekYour observation is the key component of my proof available here -> https://www.researchgate.net/publication/351347153

abstract: In this paper, we prove the Collatz conjecture. We show that if a given number can be represented in a form of a certain specific equation then Collatz conjecture is true for that particular number. Next we propose a procedure that for a given number produces this specific equation and we prove that for every initial positive integer, such equation can be found.