My Math Forum  

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

Number Theory Number Theory Math Forum


Thanks Tree28Thanks
Reply
 
LinkBack Thread Tools Display Modes
May 3rd, 2017, 11:37 PM   #171
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
Formal proof coming up.
Mariga is offline  
 
May 4th, 2017, 06:27 AM   #172
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
This is a sample of the farthest I have come when trying to simplify the problem. This is for a 1 step cycle.

Let $x_n$ be an odd positive integer. From the sequence's formula, $x_{n+1}=\frac{(3x_n+1)}{2^{a_1}}$, $x_{n+2}=\frac{(3x_{n+1}+1)}{2^{a_2}}$, and so forth, $a_i \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$.\\
For an odd integer $x_0$, the next odd integer, $x_1$ will be given by
\begin{align*}
x_1&=\frac{3x_0+1}{2^{a_1}}\tag{1}
\end{align*}
\begin{lemma}
$x_1\geq x_0$ iff $a_1\leq 2$.
\end{lemma}
\begin{proof}
Let \lambda be any $2^{a_1}.We substitute this in equation (1).
\begin{align*}
x_1&=\frac{3x_0+1}{\lambda}\\
\lambda x_1&=3x_0+1\\
\lambda x_1-3x_0&=1\\
\end{align*}
When $a_1>2$,$\lambda >4$, $\lambda x_1-3x_0=1$ will hold iff $x_1<x_0$.\\
If $a_1=2$, $\lambda =4$. $4x_1-3x_0=1$ holds if $x_0=x_1$.\\
If $a_1=1$, $\lambda =2$.$2x_1-3x_0=1$ will hold only if $x_0>x_1$.\\
$a_1\neq 0$ because the sum of $3x_0+1$ is an even integer for any $x_0$.
\end{proof}
\begin{proposition}
For $x_0>1$, $x_1\neq x_0$.
\end{proposition}
\begin{proof}
Assume there exists $x_0>1$ such that $x_1=x_0$.Then,
\begin{align*}
\frac{3x_0+1}{2^k}&=x_0\\
2^kx_0-3x_0&=1\\
x_0&=\frac{1}{2^k-3}\\
\intertext{From lemma 1,when we substitute $a_1=2$}
x_0&=\frac{1}{2^2-3}\\
&=1
\intertext{When $a_1=1$}
x_0&=\frac{1}{2^1-3}\\
&=-1\\
\end{align*}
$x_0\ngtr 1$ in both cases. Hence, there is no $x_0>1$ such that $x_0=x_1$
\end{proof}



I realised I might need to prove that for $4x_1-3x_0=1$, why the only values that could satisfy the equation is 1 for both $x_1$ and $x_0$.

Also, the problem could easily end up either involving already discovered deep mathematics, or new ones to come.

Last edited by Mariga; May 4th, 2017 at 06:36 AM.
Mariga is offline  
May 4th, 2017, 08:20 AM   #173
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
copy paste that on your latex editor in case it isn't legible.

Last edited by Mariga; May 4th, 2017 at 08:23 AM.
Mariga is offline  
May 4th, 2017, 02:31 PM   #174
Newbie
 
Joined: Jan 2017
From: Slovakia

Posts: 6
Thanks: 0

Seriously?
slickidE is offline  
May 4th, 2017, 09:25 PM   #175
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
What?

I have just found a way for cracking that. Not as complicated as I thought it was.
Mariga is offline  
May 10th, 2017, 11:16 PM   #176
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
Erdős once said mathematics is not ready for such problems. It has always been.

Last edited by skipjack; May 15th, 2017 at 09:34 AM.
Mariga is offline  
May 10th, 2017, 11:39 PM   #177
Senior Member
 
Joined: Feb 2016
From: Australia

Posts: 1,714
Thanks: 597

Math Focus: Yet to find out.
Quote:
Originally Posted by Mariga View Post
Erdős once said mathematics is not ready for such problems. It has always been.
What has always been? Ready or not ready?

Last edited by skipjack; May 15th, 2017 at 09:34 AM.
Joppy is online now  
May 11th, 2017, 08:49 AM   #178
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
Ready. Here is the proof
Mariga is offline  
May 11th, 2017, 09:16 AM   #179
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
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
\begin{align*}
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}}
\end{align*}
$x_3$ will be given by
\begin{align*}
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}}
\end{align*}
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,
\begin{align*}
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)}\tag{2}
\end{align*}
Substituting this in the next pair of terms,
\begin{align*}
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}}
\end{align*}
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$.
Mariga is offline  
May 15th, 2017, 08:41 AM   #180
Banned Camp
 
Joined: Mar 2017
From: .

Posts: 338
Thanks: 8

Math Focus: Number theory
I wouldn't have come this far without your help guys. Thank you.
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 © 2018 My Math Forum. All rights reserved.