My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree27Thanks
Reply
 
LinkBack Thread Tools Display Modes
April 18th, 2017, 11:33 PM   #161
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

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
Mariga is offline  
 
April 22nd, 2017, 05:28 PM   #162
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

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?
Mariga is offline  
April 25th, 2017, 06:40 AM   #163
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

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.
Mariga is offline  
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
curitre is offline  
April 25th, 2017, 09:21 PM   #165
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

Math Focus: Number theory
Quote:
Originally Posted by curitre View Post
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.
Mariga is offline  
April 28th, 2017, 02:03 AM   #166
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

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$\}.
Mariga is offline  
April 28th, 2017, 05:27 AM   #167
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 6,878
Thanks: 2240

Math Focus: Mainly analysis and algebra
Quote:
Originally Posted by Mariga View Post
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.
v8archie is offline  
April 28th, 2017, 07:49 AM   #168
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

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.
Mariga is offline  
April 30th, 2017, 02:58 AM   #169
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

Math Focus: Number theory
I will soon post an edit that doesn't skip any point.
Mariga is offline  
April 30th, 2017, 11:44 AM   #170
Senior Member
 
Joined: Mar 2017
From: .

Posts: 261
Thanks: 4

Math Focus: Number theory
Quote:
Originally Posted by Mariga View Post

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.
Mariga is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
collatz, conjecture, proof



Search tags for this page
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 4th, 2014 11:27 PM
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





Copyright © 2017 My Math Forum. All rights reserved.