I have the proof to Collatz conjecture.

[Mariga]

Hi people, yes I have the proof. In fact it is quite simple and the technique used can be used to prove other sequences.. I don't know who to trust with this information or where to submit it.

[Guest]

Please share your proof...

[Mariga]

Hi people, yes I have the proof. In fact it is quite simple and the technique used can be used to prove other sequences.. I don't know who to trust with this information or where to submit it.

Here it is..


Proof to Collatz conjecture.

Consider any positive integer n from which the sequence is formed. n has a probability of 0.5 of either being odd or even. If even, we divide it by two. If odd, we multiply it by three, add one and then divide the result by two since the resulting number must be even. This is same as multiplying n by 1.5 and adding 0.5. The resulting integer, say m, will hence either be n/2 or 1.5n+0.5 and also has a probability of 0.5 of being either even or odd. The 0.5 that is added has considerable effect on outcome only if n is 1 (which can explain the repeating cycle when the sequence reaches 1). In this case we will neglect it.
Since n has equal chances of being odd or even, it therefore has equal chances of being divided by 2 or being multiplied by 1.5, and so is m and the rest of the outcomes. The factor by which the outcomes are divided by is greater than the factor they are multiplied with and hence, the sequence will converge.

[Guest]

Let $x_n$ be an odd positive integer. From the sequence’s formula, $x_{n+1}=\frac{3x_n+1}{2^k}$, $x_{n+2}=\frac{3x_{n+1}+1}{2^m}$ and so forth, $m,k\in \mathbb{Z^+}$
For there to exist a cycle in the sequence, there must exist an odd integer $x_0$ such that $x_n=x_0$.
Let $x_1$, the next odd integer after $x_0$,be given by
$$x_1=\frac{3x_0+1}{2^{a_1}}$$
$x_2$ will be given by
$$x_2=\frac{3x_1+1}{2^{a_2}}$$
$x_2$ in terms of $x_0$ will be
$x_2=\frac{3(\frac{3x_0+1}{2^{a_1}})+1}{2^{a_2}}=\frac{9x_0+3+2^{a_1}}{2^{a_1+a_2}}$
$x_3$ will be given by
$x_3=\frac{3x_2+1}{2^{a_3}}=\frac{3(\frac{3x_1+1}{2^{a_2}})+1}{2^{a_3}}=\frac{3(\frac{9x_0+3+2^{a_1}}{2^{a_1+a_2}})+1}{2^{a_3}}=\frac{27x_0+9+3.2^{a_1}+2^{a_1+a_2}}{2^{a_1+a_2+a_3}}$
From the three examples, we can generate a formula for $x_n$ in terms of $x_0$,which will be
$$x_n=\frac{3^nx_0+3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}}{2^{\sum\limits_{n=1}^na_i}}$$
Let $x_n=x_0$, hence
$$x_0=\frac{3^nx_0+3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}}{2^{\sum\limits_{n=1}^na_i}}$$
Let $\sum\limits_{n=1}^na_i$ be $k$
$$2^kx_0-3^nx_0=3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}$$
$$x_0(2^k-3^n)=3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}$$
$2^k$ can be expressed as $(2^{\frac{k}{n}})^n$
$$x_0[(2^{\frac{k}{n}})^n-3^n]=3^{n-1}+3^{n-2}2^{a_1}+3^{n-3}2^{a_1+a_2}+\cdots +3.2^{\sum\limits_{n=1}^{n-2}a_i}+2^{\sum\limits_{n=1}^{n-1}a_i}\tag{1}$$
When factoring,
$$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots +a.b^{n-2}+b^{n-1})$$
This is same as
$$a^n-b^n=(a-b)(b^{n-1}+b^{n-2}a+b^{n-3}a^2+\cdots +b.a^{n-2}+a^{n-1})$$
We therefore notice the polynomial in equation (1) is regular.
Hence, $x_0[(2^{\frac{k}{n}})^n-3^n]$ can be expressed as,
$$x_0[(2^{\frac{k}{n}})^n-3^n]=x_0(2^{\frac{k}{n}}-3)(3^{n-1}+3^{n-2}2^{\frac{k}{n}}+3^{n-3}(2^{\frac{k}{n}})^2+\cdots +3(2^{\frac{k}{n}})^{n-2}+(2^{\frac{k}{n}})^{n-1})$$
$$=3^{n-1}(2^{\frac{k}{n}}-3)x_0+3^{n-2}2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)x_0+3^{n-3}(2^{\frac{k}{n}})^2(2^{\frac{k}{n}}-3)x_0+\cdots +3(2^{\frac{k}{n}})^{n-2}(2^{\frac{k}{n}}-3)x_0+(2^{\frac{k}{n}})^{n-1})(2^{\frac{k}{n}}-3)x_0$$
Each term in this polynomial corresponds to the terms in the polynomial in equation (1).
$\begin{align*}
3^{n-1}\quad &:\quad 3^{n-1}(2^{\frac{k}{n}}-3)x_0\\
3^{n-2}2^{a_1}\quad &:\quad 3^{n-2}2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)x_0\\
3^{n-3}2^{a_1+a_2}\quad &:\quad 3^{n-3}(2^{\frac{k}{n}})^2(2^{\frac{k}{n}}-3)x_0\\
\vdots\qquad &:\qquad \vdots \\
3.2^{\sum\limits_{n=1}^{n-2}a_i}\quad &:\quad 3(2^{\frac{k}{n}})^{n-2}(2^{\frac{k}{n}}-3)x_0\\
2^{\sum\limits_{n=1}^{n-1}a_i}\quad &:\quad (2^{\frac{k}{n}})^{n-1})(2^{\frac{k}{n}}-3)x_0
\end{align*}$
Hence, each of these corresponding terms will be equal. Hence,
$3^{n-1}=3^{n-1}(2^{\frac{k}{n}}-3)x_0\\ 1=(2^{\frac{k}{n}}-3)x_0\\ x_0=\frac{1}{(2^{\frac{k}{n}}-3)} $
Substituting this in the next pair of terms,
$3^{n-2}2^{a_1}=3^{n-2}2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)\frac{1}{(2^{\frac{k}{n}}-3)}\\2^{a_1}(2^{\frac{k}{n}}-3)=2^{\frac{k}{n}}(2^{\frac{k}{n}}-3)\\2^{a_1}=2^{\frac{k}{n}}$
Substituting this in equation (2),
$$x_0=\frac{1}{(2^{a_1}-3)}$$
The only value that satisfies this equation such that $x_0$ and $a_1$ are both positive integers is $a_1=2$ to give $x_0=1$.

[Guest]

I'm not sure about equating the powers of three.

Your term by term equation implies all the a's are equal, when I think the point is that should be arbitrary.

To put it another way, I think equating terms is not always right.

[Guest]

Equating the coefficients the way you do it is not correct, because they depend on the same variable, [tex]x_{0 }[/tex]
You do that way only by looking the powers of 3, but for the entire solution you must do all the sum...
You also have numbers in your expressions that can be irrational, there is no proof of k can be divided by n.

Also assuming x_{0 }=x_{n } is not correct, there can be odd numbers generating a crescent sequence (it was calculated that an ipotetica number with this property if exist, must be extremely large, but this is not a "it doesn't exist"

I do not understand you initial assumption about the N odd and the 1.5n+0.5 with 0.5 being irrelevant as you say. It is a part of the next result, big or small.
Take n=23 and we go to 35, odd so we must repeat the 3n+1/2 operation, that increase the value. With n=21 we obtain 32, a perfect power of 2, so we rapidly go to 1 by the sequence rules.

[Guest]

The "proof" isn't correct. People often say that the Collatz conjecture intuitively ought to be true, because half the time you multiple by 1.5 and half the time you divide by 2, so it seems like on average it should be going down. But that isn't a proof. It's just an intuitive argument. And that kind of argument sometimes gives the wrong result.

Here's how to use a similar "proof" to prove something false. Define f(n) to be n+5 if n is a multiple of 10, and n-1 otherwise. You could say that a random n has only a 10% chance of increasing by 5, and a 90% chance of decreasing by 1, and so on average it will decrease. And so this function shouldn't have any cycles at high numbers. But the truth is that EVERY starting number reaches a small cycle!

Why is the "proof" wrong? Because we are not handling the probabilities correctly.

First, you can't say that a random number is odd 50% of the time, unless you first describe how you plan to generate the random number. You have to say what the probability distribution is. And you can't just say "every number is equally likely". That would be a uniform probability distribution over an infinite set, which is mathematically impossible.

Second, even if you could define the probability distribution of n where you're starting, you'd also having to define the distribution after you've iterated the f() function many times. In my example, after iterating f() many times, you're guaranteed to be at a multiple of 10 or within 5 greater than it. Definitely not a number like 107. So the true probability distribution after many steps isn't as simple as it was on the first or second step.

Third, even if you could somehow prove that a random starting number n has a 100% probability of satisfying Collatz, that wouldn't necessarily prove that all numbers satisfy Collatz. This is something weird about probabilities over infinite sets. Just because something is true 100% of the time, that doesn't mean it's true all the time. Yes, that's strange. In math terms, there's a difference between "true with probability one" and "true". A mathematician would say that if you flip a fair coin repeatedly, forever, then you will eventually see heads, with probability 1 (which is a 100% probability), but that you are not guaranteed to ever flip heads. Because it is theoretically possible to flip only tails forever. Flipping tails forever has a probability of zero, but it is not impossible.

TL;DR: probabilities are tricky, which is why the "proof" was incorrect.

[Guest]

The "proof" isn't correct. People often say that the Collatz conjecture intuitively ought to be true, because half the time you multiple by 1.5 and half the time you divide by 2, so it seems like on average it should be going down. But that isn't a proof. It's just an intuitive argument. And that kind of argument sometimes gives the wrong result.

Here's how to use a similar "proof" to prove something false. Define f(n) to be n+5 if n is a multiple of 10, and n-1 otherwise. You could say that a random n has only a 10% chance of increasing by 5, and a 90% chance of decreasing by 1, and so on average it will decrease. And so this function shouldn't have any cycles at high numbers. But the truth is that EVERY starting number reaches a small cycle!

Why is the "proof" wrong? Because we are not handling the probabilities correctly.

First, you can't say that a random number is odd 50% of the time, unless you first describe how you plan to generate the random number. You have to say what the probability distribution is. And you can't just say "every number is equally likely". That would be a uniform probability distribution over an infinite set, which is mathematically impossible.

Second, even if you could define the probability distribution of n where you're starting, you'd also having to define the distribution after you've iterated the f() function many times. In my example, after iterating f() many times, you're guaranteed to be at a multiple of 10 or within 5 greater than it. Definitely not a number like 107. So the true probability distribution after many steps isn't as simple as it was on the first or second step.

Third, even if you could somehow prove that a random starting number n has a 100% probability of satisfying Collatz, that wouldn't necessarily prove that all numbers satisfy Collatz. This is something weird about probabilities over infinite sets. Just because something is true 100% of the time, that doesn't mean it's true all the time. Yes, that's strange. In math terms, there's a difference between "true with probability one" and "true". A mathematician would say that if you flip a fair coin repeatedly, forever, then you will eventually see heads, with probability 1 (which is a 100% probability), but that you are not guaranteed to ever flip heads. Because it is theoretically possible to flip only tails forever. Flipping tails forever has a probability of zero, but it is not impossible.

TL;DR: probabilities are tricky, which is why the "proof" was incorrect.

Your arguments are non-mathematical, illogical, and fictional. What we need is a sound mathematical argument (proof) or a conterexample which explains why the Collatz conjecture is true or false. You have not prove not disprove the conjecture... Your efforts are fruitless. Please stop.

[Guest]

...
TL;DR: probabilities are tricky, which is why the "proof" was incorrect.

Your arguments are non-mathematical, illogical, and fictional. What we need is a sound mathematical argument (proof) or a conterexample which explains why the Collatz conjecture is true or false. You have not prove not disprove the conjecture... Your efforts are fruitless. Please stop.

He isn't trying to prove or disprove the conjecture, he is trying to show that mariga's proof is incorrect

[Guest]

...
TL;DR: probabilities are tricky, which is why the "proof" was incorrect.

Your arguments are non-mathematical, illogical, and fictional. What we need is a sound mathematical argument (proof) or a conterexample which explains why the Collatz conjecture is true or false. You have not prove not disprove the conjecture... Your efforts are fruitless. Please stop.

He isn't trying to prove or disprove the conjecture, he is trying to show that mariga's proof is incorrect

His approach is flawed, and therefore, it should be ignored.

[Guest]

guest

His approach is flawed, and therefore, it should be ignored.[/quote]

this approach is not wrong. instead of treating it as 2 possibilities, it should be treated as 2 different cases.

[Guest]

I am pretty sure it will always be true. If the number is even, it will be divided by 2, which will be a number already proven to work. If it is odd, it will eventually become an even number, bringing it back down, and becoming a number already proven to work. Please correct me if I am wrong. If I am right, that would be pretty cool.

[Guest]

If you really wonder what a harmonious system is formed by odd natural numbers and how it relates to the Collatz Conjecture, then in March 2019 a book was published

Paperback

https://www.amazon.com/Proof-Collatz-co ... 1090639279

EBook

https://www.amazon.com/Proof-Collatz-co ... B07PR2J3F8

[Guest]

If the construction were different it might hold, but one can't often neglect things in mathematics. I find that with these kinds of problems, breaking down the logic is most effective.

For f(n), {n/2 if n is even; 3n + 1 if n is odd}
As noted, the conjecture claims that all positive integer values converge to 1 in a finite number of steps.

It may be noted that all power-of-two conditions are fatal ("fatal" here meaning that the fate of convergence to one is set) if there is any point at which one appears, most decisively if in the perfect form 1*2ⁿ. It will be demonstrated in a bit that all single-digit whole numbers lead to convergence which plays a role in further conjecture.

The cycle at 9 is the longest of the single digit loss conditions, running through what could be called the "extended single-digit fatal cycle":
9-28-14-7-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1 (Note that the "pure power of two" condition is forced to occur at the end, which occurs after a piece of the fatal condition 5*2ⁿ).

Because of the case of the cycle at 9, all single-digit conditions involving 1 (obvious), 2, 4, 5, 7, 8, and 9 (obvious) are fatal. Of the two single-digit potentialities remaining (3 and 6), one leads to the other (part of the fatal condition 3*2ⁿ) and they both lead to 10, which is part of the extended single-digit fatal cycle. Therefore, there is no single-digit integer condition that avoids convergence to 1.

Because of the power-of-2 extension condition, any number that may be perceived as a single-digit whole number multiplied by a power of 2 (i.e. {1-9}2ⁿ) is guaranteed to converge under the given constraints. Of these, the prime numbers give the most efficient tracking as they expose the greatest number of whole numbers that would converge. We may take this a step further and assert that any number divisible by two leads to convergence because the conditions guarantee even parity every time an odd number is encountered--the "+1" part of the odd condition is doing the code breaking work, the "3*" multiplier just makes the numbers more interesting but ultimately changes nothing about the gravity of descent once a power of two is reached. (Of great importance is the fact that this multiplier is an odd number; if it were even, all terms would become odd, and all values would grow without bound.) Because each set of numbers will hit a multiple of two at least once in every pair of iterations, achieving the "x + 1 = {1-9}*2ⁿ" condition is a matter of when, not if. All values will eventually converge to a single-digit number by landing on a multiple of a power of two. There must certainly be other known fatal spirals that can be mapped out as a result of the above conditions, at which point further calculations need not be run.

The demonstration of the long single-digit spiral, the proof that all single-digit values inevitably converge, and the exposure of the underlying modulo-2 condition in which all values are either even or becoming even makes it clear that for any and all positive whole values of n, the Collatz conjecture does in fact converge to 1--logically,at least. But, representing that purely mathematically may prove more troublesome.
-D. Sheppard

[Guest]

I tried the same approach as Mariga; however, I converted every number to log base 2.
1) Let n be the log base 2 of the starting number.
On the average, half of the time the number is even, which results in a change to n of -1 base 2 (÷2).
2) 1/2 the time, on the average, the number is odd which means a change of + 1.58496250072 base 2 (x 3)
3) Of course, following the operation 3n+1, the new number is even so there will be a subsequent change in the log base 2 of -1 (÷2)
4) The total change will be 1.58496250072 - 1= + .58496250072 each time the number is odd.
5) The average change for even and odd numbers will be :
(-1 + .58496)/2 = -.20752 log base 2.

5) However, we must account for the + 1 in the term 3n + 1. Mariga didn't consider that. The worst case scenario is where n=1 and 3n + 1 = 4. The +1 accounts for the transition from 3 to 4. The difference in log base 2 is the log base 2 of 4 = 2 - the log base 2 of three = 1.58496.
So the difference of the log base 2 resulting from the -1 in the equation 3n + 1 is .4150375.
6) We apply 3n+1 = 4 half the time so we divide by 2.
.4150375/2 = .20752 .
7) In the trivial case of n= 1 the average change is -.20752 + .20752 = 0.
8 For every other case of applying 3n + 1, you will see that the total average change in the log base 2 (for positive and negative cases) is negative. For example, the change in the log base 2 from 9 -10 (the next possible number 3n where n is negative is .152. Using that number, the average change base 2 of an iteration is - .2075 + .152 = -.03595. By the mathematics of log base 2, every +1 in the formula 3n+1 makes an even smaller change in log base 2 as you look at higher numbers. So by the law of averages, the log base 2 over time will be heading to zero and log base 2 of 0 = 1.

[Guest]

Let f(n) be the Collatz function.
Starting with n is odd,
1. f(n) = (3n + 1)/2^x_1 (where x_1 = the power of two that divides the value of the function after the first iteration.
2. ((3n +1)/2^x_1)) x 3 + 1
= (9n + 3/2^x_1) + 1
and ((9n + 3/x1) + 1)/2^x_2) where x_2 is the power of two that divides the even number produced after the second iteration.
= (9n + 3)/ (2^x_1+x_2) + 1/2^x_2
3. ((9n + 3)/(2^x_1+x_2) + 1/2^x_2)) x 3 + 1
= ((27n + 9)/(2^x_1+x_2) + (3/2^x_2) + 1
From this we can derive the general formula for the ith iteration of the series started with the odd number n generated by the Collatz conditions:
f(n_i) = ((3^i)n/ (2^x_1+x_2 + ...x_i) + (3^i-1)/ (2^x_1+x_2 + ...x_i) + (3^i-2)/(2^x_2 + ...x_i) + ...3^0/2^x_i

What if there's a loop? Then

f(n_i) = ((3^i)n/ (2^x_1+x_2 + ...x_i) + (3^i-1)/ (2^x_1+x_2 + ...x_i) + (3^i-2)/(2^x_2 + ...x_i) + ...3^0/2^x_i = n

Divide both sides by n and you get:
((3^i)/ (2^x_1+x_2 + ...x_i) + ((3^i-1)/ (2^x_1+x_2 + ...x_i) + (3^i-2)/(2^x_2 + ...x_i) + ...(3^0)/(2^x_i)/n = 1

Is it right to assert that the second term drops out as n approaches infinity? Therefore we would have

((3^i)/ (2^x_1+x_2 + ...x_i) = 1 or

((3^i) = (2^x_1+x_2 + ...x_i)
which is impossible. So therefore, you can't have a loop as n gets very large.

Also, maybe you can generalize since the formula (before dividing through with n) starts with n on the left and ends with n on the right, so the total value of the series must be very small with the first term close to 1.

[Guest]

The secret falls with 2^n. If ever the iteration of this problem falls on 2^n it automatically goes to one. (the only reason we see the 4,2,1 cycle is because we see 1 as an odd number). If numbers are infinite using this formula must eventually land you on a number that is 2 to the n'th power. Submitted by David Pobst, I might be an idiot.

[Guest]

Hello everybody,
I guess you have heard this statement before, but I have to repeat it: I think I have a proof for the Collatz conjecture.
Please take a look on my proof and tell me where are the flaws (if any).
Thanks a lot
Dror

[Guest]

If your proof looks anything like this: albeit yours being given in a more sophisticated manner, then maybe you have a proof?

For mine, here it is:

In math, two rules apply for this function:
1 - Any number multiplied by an even integer will result in an even integer.
2 - Any odd integer multiplied by an odd integer will result in an odd integer.
(If multiplying odd by even, see rule 1.)

The first step of the function will always reduce the even integer by half, thus a continual decrease until it reaches 1, or an odd integer.

The second step, due to only applying to odd integers, and when the "X" in "Xn+1" is an odd integer as well, the result will always be an odd integer, and then made even by adding 1. If the "X" is an even integer, the output will even, and then made odd by the "+1", thus resulting in an endless series of odd integers.

Although the function is "3n+1", the "3" only results in an increased number of steps, for some odd integers, to reach "1". Any odd value of "X" in the "Xn+1", will have all integers, end up at "1". This allows the second step "n+1" to be the quickest for giving a data set:

If even, (n/2).
If odd, (n+1).

This creates a series where every positive integer descends to 1, by being halved, or when unable to be
halved, due to being an odd integer, increased by 1, and then halved, until only a 1 remains.

10-5-6-3-4-2-1
9-10-5-6-3-4-2-1
8-4-2-1
7-8-4-2-1
6-3-4-2-1
5-6-3-4-2-1
4-2-1
3-4-2-1
2-1
1

I'm not a mathematician, so be kind on any criticism of this layout. - Jeff W.

[Guest]

Using the largest semi-prime, from the RSA Factoring Challenge,

25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

Function - 3n+1 - Steps until reaching 1 -- 15195

Function - 1n+1 - Steps until reaching 1 -- 3067

Both functions resulted in 1.

Jeff W.