My Math Forum Proof to Collatz conjecture.

 Number Theory Number Theory Math Forum

 April 18th, 2017, 11:33 PM #161 Senior Member   Joined: Mar 2017 From: . Posts: 294 Thanks: 6 Math Focus: Number theory Here is the revised version Proof there is Only One Cycle in the $3n+1$ Problem. Let $x_n$ be a positive integer. From the sequence's formula, $x_{n+1}=\frac{1}{2}x_n$ if $x_n$ is even and $x_{n+1}= \frac{1}{2}(3x_n+1)$ if $x_n$ is odd. \\ For there to exist a cycle in the sequence, there must exist an integer $x_n$ such that $x_n$ mod $x_0$=0. \\ Since $x_{n+1}=\frac{1}{2}x_n$ for even numbers, this doesn't change $x_n$ mod $x_0$ when even outcomes appear in the sequence. So we will consider iterations of odd numbers without minding the even outcomes in between. For example, assume we have a sequence in which $x_3$ is 13. $x_4$ will be 20 and $x_5$ will be 10. If $x_4$ mod $x_0$=0 then $x_5$ mod $x_0$=0 if $x_4\neq x_0$. \\ Let $x_0$ be an odd number. We will show $\frac{x_1}{x_0}=k$ where $k$ is a positive integer and $k\neq0$ to show a one step cycle exists. We will also show all integers that $x_0$ could be.\\ $x_1$ will be given by $\frac{1}{2}(3x_0+1)$. So \begin{align*} \frac{\frac{1}{2}(3x_0+1)}{x_0}&=k\\ 3x_0+1&=2kx_0\\ 1&=x_0(2k-3)\\ \frac{1}{2k-3}&=x_0\\ \end{align*} The only values of $k$ that could satisfy the equation such that both $k$ and $x_0$ are integers is 1 and 2, for which the values of $x_0$ as -1 and 1 respectively. Hence,the only positive integer from which such a cycle can occur is 1.\\ We then consider the second iteration \begin{align*} x_2&=\frac{1}{2}(3x_1+1)\\ &=\frac{1}{2}\{3[\frac{1}{2}(3x_0+1)]+1\}\\ &=\frac{1}{2}\{(\frac{9x_0}{2}+\frac{3}{2})+1\} \\ &=\frac{9x_0}{4}+\frac{3}{4}+\frac{1}{2}\\ &=\frac{9x_0+5}{4}\\ \end{align*} We will then show $\frac{x_2}{x_0}=k$ where $k$ is a positive integer and $k\neq0$ to show a two step cycle exists. We will also show all integers that $x_0$ could be.\\ Hence, \begin{align*} \frac{\frac{9x_0+5}{4}}{x_0}&=k\\ \frac{9x_0+5}{4}&=kx_0\\ 5&=4kx_0-9x_0\\ \frac{5}{4k-9}&=x_0\\ \end{align*} The only values of $k$ that satisfy the equation such that $k$ and $x_0$ are integers is 1 and 2 and $x_0$ will hence be -1 or -5.This proves that no positive integer undergoes a cycle if two of its outcomes are odd.\\ We can iterate n times in general to find a positive $x_0$ that satisfies $\frac{x_n}{x_0}=k$ where $k$ is a positive integer. From the two equations for first and second iteration we can generate a formula for nth iteration. It will be $$\frac{3a_n+2^n}{2^{n+1}k-3^{n+1}}=x_0$$ \\ Such that $k$ and $x$ are integers that satisfy the equation and; \begin{align*} n&=0, 1, 2, 3, ...\\ a_{n+1}&= 3a_n+2^n\\ a_0&=0\\ \end{align*} It can be proven through induction that $3a_n+2^n=3^{n+1}-2^{n+1}$ Hence, the equation can be rewritten as $$\frac{3^n-2^n}{2^{n}k-3^n}=x_0$$ Such that $n=1,2,3,...$ The equation can be written as $$\frac{3.3^{n-1}-2.2^{n-1}}{2.2^{n-1}k-3.3^{n-1}}=x_0$$ Let $a=3^{n-1}$ and $b=2^{n-1}$ $$\frac{3a-2b}{2bk-3a}=x_0$$ For $x_0$ to be a positive integer, then $3a>2b$ and $2bk>3a$\\ This implies, $$2bk>3a>2b$$ The inequality does not hold if $k=1$ and hence $k\geq2$.\\ For all $k\geq2$, $$4b>3a>2b$$ The inequality holds iff $a=b$\\ Hence, $a=3^0$ and $b=2^0$.\\ The equation will therefore be \begin{align*} \frac{3-2}{2k-3}&=x_0\\ \\ \frac{1}{2k-3}&=x_0\\ \end{align*} The only value of $k$ that satisfy the equation such that $k$ and $x_0$ are positive integers is 2 for which $x_0$ is 1.\\ This proves that there is no positive integer greater than 1 from which a cycle occurs. Last edited by Mariga; April 18th, 2017 at 11:40 PM. Reason: For proper visibility and spacing
 April 22nd, 2017, 05:28 PM #162 Senior Member   Joined: Mar 2017 From: . Posts: 294 Thanks: 6 Math Focus: Number theory The proof still doesn't hold because of the last parts. Anyone who can prove $3^n-2^n$ mod $2^nk-3^n$ $\neq$ 0?
 April 25th, 2017, 06:40 AM #163 Senior Member   Joined: Mar 2017 From: . Posts: 294 Thanks: 6 Math Focus: Number theory Guys, you are all silent. I now have the full proof for this. The only cycle in the sequence is at 1. Also, I had earlier shown the sequence doesn't diverge. The conjecture is safe.
 April 25th, 2017, 12:24 PM #164 Newbie   Joined: Apr 2017 From: NH Posts: 1 Thanks: 0 Your formula to generate the nth iteration assumes that every time you perform the "divide by 2", you end up with another odd number. Let O = Odd Let E = Even Take for example 13. 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. O, E, E, E, O, E, E, E, E, O Notice after the first (3x+1)/2, we arrive at 20. Your general formula tries to apply another 3x+1 to an even number. That violates the rules. The only thing your approach would/could prove is there there are no cycles of OEE OEE OEE OEE OEE ... other than the trivial one It says nothing about cycles that might start with OEEE
April 25th, 2017, 09:21 PM   #165
Senior Member

Joined: Mar 2017
From: .

Posts: 294
Thanks: 6

Math Focus: Number theory
Quote:
 Originally Posted by curitre Your formula to generate the nth iteration assumes that every time you perform the "divide by 2", you end up with another odd number. Let O = Odd Let E = Even Take for example 13. 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. O, E, E, E, O, E, E, E, E, O Notice after the first (3x+1)/2, we arrive at 20. Your general formula tries to apply another 3x+1 to an even number. That violates the rules. The only thing your approach would/could prove is there there are no cycles of OEE OEE OEE OEE OEE ... other than the trivial one It says nothing about cycles that might start with OEEE
Thank you. I have given it a careful thought and have seen how it has affected the work.

 April 28th, 2017, 02:03 AM #166 Senior Member   Joined: Mar 2017 From: . Posts: 294 Thanks: 6 Math Focus: Number theory Finally.. 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. \\ For there to exist a cycle in the sequence, there must exist an odd integer $x_0$ such that $x_n=x_0$\\ For an odd integer $x_0$, the next odd integer, $x_1$ will be given by $\frac{3x_0+1}{2^k}$. For $x_1\geq x_0$, $k<2$\\ To check whether a one step cycle exists, \begin{align*} \frac{3x_0+1}{2^k}&=x_0\\ 2^kx_0-3x_0&=1\\ x_0&=\frac{1}{2^k-3}\\ \end{align*} The only value of $k$ such that $x_0$ is a positive integer is 2 to give $x_0=1$. Hence, a one step cycle exists only at 1, and we note that it is the only integer such that $x_1=x_0$ where $k=2$. For any other positive odd integer, for $x_1\geq x_0$, then $k=1$. $k$ cannot be 0 because $3x_0+1$ will always be even.\\ \\ The second odd integer, $x_2$ is given by \begin{align*} x_2&=\frac{3x_1+1}{2^m}\\ &=\frac{3(\frac{3x_0+1}{2^k})+1}{2^m}\\ &=\frac{9x_0+3+2^k}{2^{k+m}} \end{align*} $x_2\geq x_0$ iff $k+m<4$. This is because the we have multiplied $x_0$ by a factor of $3\times 3$ or 9, and hence we can divide the result by $2^3$ or 8 to get a whole number and not $2^4$.\\ To check whether a two step cycle exists, \begin{align*} \frac{9x_0+3+2^k}{2^{k+m}}&=x_0\\ 2^{k+m}x_0-9x_0&=3+2^k\\ x_0&=\frac{3+2^k}{2^{k+m}-9}\\ \end{align*} For $x_0$ to be a positive number, then $2^{k+m}>9$, which means $2^{k+m}>2^3$, a contradiction. Again, the only value that satisfies the equation is such that $x_0$ is 1 for $k=2$ and $m=2$. The equation cannot yield $x_0>1$ because $2^{k+m}>9$\\ \\ The third odd integer will be given by \begin{align*} x_3&=\frac{3x_2+1}{2^p}\\ &=\frac{3(\frac{3x_1+1}{2^m})+1}{2^p}\\ &=\frac{3(\frac{9x_0+3+2^k}{2^{k+m}})+1}{2^p}\\ &=\frac{27x_0+9+3.2^k+2^{k+m}}{2^{k+m+p}} \end{align*} For any $x_0>1$, $x_3>x_0$ iff $k+m+p<5$. This is because we multiply $x_0$ by a factor of $3\times 3\times 3$ or 27, and hence if we divide the result by $2^5$, 32, we would end up with a number less than $x_0$\\ We still check whether there exists an integer $x_0$ from which a three step cycle occurs. \begin{align*} \frac{27x_0+9+3.2^k+2^{k+m}}{2^{k+m+p}}&=x_0\\ 2^{k+m+p}x_0-27x_0&=9+3.2^k+2^{k+m}\\ x_0&=\frac{9+3.2^k+2^{k+m}}{2^{k+m+p}-27} \end{align*} Similarly, for $x_0$ to be a positive integer, $2^{k+m+p}>27$, contradicting our earlier findings. Only one special case holds for this equation too, $x_0=1$ when $k=m=p=2$.\\ \\ In general, when we check $x_0$ for an $n$ step cycle, we generate the following equation $$\frac{x_0=3^{n-1}+3^{n-2}2^{a_1}+3^{n-2}2^{a_1+a_2}+...+3.2^{a_1+a_2+a_3+...+a_{n-1}}+2^{a_1+a_2+a_3+...+a_n}}{2^{a_1+a_2+a_3+...+a_ n}-3^n}$$ For any $x_0>1$, $2^{a_1+a_2+a_3+...+a_n}<3^n$ or $2^{a_1+a_2+a_3+...+a_n}<2^{2n}$ and hence, the equation cannot have any value above 1.\\ $x_0$ can only be 1 iff each $a_i=2$. The values of $a_i$ can be found by equating the numerator to the denominator.\\ This proves that no cycle exists apart from \{$4$, $2$, $1$\}.
April 28th, 2017, 05:27 AM   #167
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,232
Thanks: 2411

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Mariga For an odd integer $x_0$, the next odd integer, $x_1$ will be given by $\frac{3x_0+1}{2^k}$. For $x_1\geq x_0$, $k<2$
Where do you get the claim that $k \lt 2$?

Last edited by skipjack; April 28th, 2017 at 05:44 AM.

 April 28th, 2017, 07:49 AM #168 Senior Member   Joined: Mar 2017 From: . Posts: 294 Thanks: 6 Math Focus: Number theory You multiply an odd number by 3 and add 1. The result would be an even number and hence we divide by two. What we get would still be greater than the initial number, because we have divided by a smaller factor than the factor we multiply with. If the number is still even and we divide it again by 2, that would be same as first multiplying the number by 3 and then dividing it by 4, or $2^2$ where k is 2. The integer we get will be lesser than the initial value.
 April 30th, 2017, 02:58 AM #169 Senior Member   Joined: Mar 2017 From: . Posts: 294 Thanks: 6 Math Focus: Number theory I will soon post an edit that doesn't skip any point.
April 30th, 2017, 11:44 AM   #170
Senior Member

Joined: Mar 2017
From: .

Posts: 294
Thanks: 6

Math Focus: Number theory
Quote:
 Originally Posted by Mariga For any $x_0>1$, $x_3>x_0$ iff $k+m+p<5$. This is because we multiply $x_0$ by a factor of $3\times 3\times 3$ or 27, and hence if we divide the result by $2^5$, 32, we would end up with a number less than $x_0$\\
There is an error here.

 Tags collatz, conjecture, proof

,

,

,

,

,

progress collatz

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post JwClaassen Number Theory 0 March 18th, 2017 08:47 AM isaac Number Theory 6 March 15th, 2016 01:12 AM vlagluz Number Theory 10 November 4th, 2014 11:27 PM lwgula Number Theory 2 October 30th, 2014 02:02 PM Aika Number Theory 6 April 29th, 2012 06:34 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top