April 18th, 2017, 11:33 PM  #161 
Senior Member Joined: Mar 2017 From: . Posts: 208 Thanks: 2 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(2k3)\\ \frac{1}{2k3}&=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_09x_0\\ \frac{5}{4k9}&=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}k3^{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^n2^n}{2^{n}k3^n}=x_0$$ Such that $n=1,2,3,...$ The equation can be written as $$\frac{3.3^{n1}2.2^{n1}}{2.2^{n1}k3.3^{n1}}=x_0$$ Let $a=3^{n1}$ and $b=2^{n1}$ $$\frac{3a2b}{2bk3a}=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{32}{2k3}&=x_0\\ \\ \frac{1}{2k3}&=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: 208 Thanks: 2 Math Focus: Number theory 
The proof still doesn't hold because of the last parts. Anyone who can prove $3^n2^n$ mod $2^nk3^n$ $\neq$ 0?

April 25th, 2017, 06:40 AM  #163 
Senior Member Joined: Mar 2017 From: . Posts: 208 Thanks: 2 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: 208 Thanks: 2 Math Focus: Number theory  Quote:
 
April 28th, 2017, 02:03 AM  #166 
Senior Member Joined: Mar 2017 From: . Posts: 208 Thanks: 2 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_03x_0&=1\\ x_0&=\frac{1}{2^k3}\\ \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_09x_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_027x_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^{n1}+3^{n2}2^{a_1}+3^{n2}2^{a_1+a_2}+...+3.2^{a_1+a_2+a_3+...+a_{n1}}+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: 6,778 Thanks: 2195 Math Focus: Mainly analysis and algebra  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: 208 Thanks: 2 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: 208 Thanks: 2 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: 208 Thanks: 2 Math Focus: Number theory  

Tags 
collatz, conjecture, proof 
Search tags for this page 
math forum collatz,forum math proof collatz conjecture,forum math collatz,collatz maths forum,collatz math forum
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
On the Collatz Conjecture  JwClaassen  Number Theory  0  March 18th, 2017 08:47 AM 
collatz conjecture  isaac  Number Theory  6  March 15th, 2016 01:12 AM 
About Collatz conjecture  vlagluz  Number Theory  10  November 5th, 2014 12:27 AM 
The marvellous proof of the collatz conjecture  lwgula  Number Theory  2  October 30th, 2014 02:02 PM 
Collatz conjecture & More (Please Help)  Aika  Number Theory  6  April 29th, 2012 06:34 AM 