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 1 One 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
-adic integer, 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 about generic orbits, but not about all orbits. 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 integers
such 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 6 Suppose 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 7 Suppose 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.
325 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 […]
16 December, 2019 at 4:13 am
Joao
Hi. 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ƶdinger
Each 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úas
Tu 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úas
Your 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 Maga
A “9n+1” problem would be easier to solve?
21 December, 2019 at 12:19 am
zhihao81
In 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
zhihao81
You 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
iiiduncaniii
I 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úas
It’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
Anonymous
Is 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 Tao
I 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 S
You 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
dabler
This 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
Anonymous
The 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
mugbuff
It 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 Jiang
The 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.
(where
)

(where
)
According to this definition, the general formula for odd continuous iteration can be derived, that is
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.
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 Jiang
Correction:
12 August, 2020 at 11:26 pm
Antoine Deleforge
Dear 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 Jiang
Dear 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 Clarke
I 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 Pountain
I’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
Anonymous
No.
25 September, 2020 at 9:32 am
Dick Pountain
Oops, 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 rostamy
Hi
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 Leal
One 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
markmca
Not 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
Bill
Observation 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
Anonymous
1. 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
Anonymous
ops… 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 Ted
Quiconque 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
Notlikeireallyknow
Over 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
Robert
Use 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 Tenguriya
I’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
hashemmath
Hi
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
Anonymous
Go to a dungeon and don’t come out until you prove it.
2 May, 2021 at 2:43 am
Anonymous
You 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-8000
https://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
Walter
Dr. 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
Walter
On 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 Savino
The 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úas
Tu 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úas
Your 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 Murillo
It 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
sacirisi
With 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 Rehder
Rephrase 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 Watson
Here 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
Anonymous
Dr. 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 Croft
re 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
Anonymous
Can 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
Anonymous
The formula (1) from conjecture 3 works for negative cycles ?
14 December, 2021 at 7:33 pm
Dennis Estenson
I 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 […]