by rivasjc » Sat Nov 11, 2017 8:30 am
Maybe a good one, sorry for bothering
The Collatz conjecture as stated in Wikipedia says that if we define the following function over the natural numbers;
\begin{equation}
f(n)= \left \{
\begin{split}
n/2 &\text{ if } n \equiv 0 \pmod{2}\\
3n+1 &\text{ if } n\equiv 1 \pmod{2}
\end{split}
\right .
\end{equation}
And build a sequence, starting in any arbitrary natural number as follows:
\begin{equation}
a_i= \left \{
\begin{split}
n &\text{ for } i=0\\
f(a_{i-1}) &\text{ for } i>0
\end{split}
\right .
\end{equation}
that is: $a_i$ is the value of $f$ applied to $n$ recursively $i$ times; $a_i = f^{(i}(n)$.
The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.
Now, let be $a_j$ an arbitrary number in a sequence built with the specified method. If $a_j$ is an odd number, then $a_{j+1}$ will be even. On the other hand, if $a_j$ is even, then $a_{j+1}$ can be even with a probability $1/2$, $a_{j+2}$ with a probability $1/4$ and so on.
Now let's build the sequence $b_i$ of odd numbers that results of applying function f. Assuming we start with an odd number, and after i iterations we will obtain:
\begin{equation}
b_i= (f_{odd}^{(i}f_{even}^{(\sum_{j=1}^ik(j)})(n)
\end{equation}
Where to obtain each odd element of the sequence from the previous one we had to compose the odd part of f which is $3n+1$ once and the even part of f or $n/2$ at least once.
Now, to prove the Collatz conjecture it is enough proving that the limit when $i\longrightarrow\infty$ is one or lower.
This can be done if we see that:
\begin{equation}
\lim_{i \to \infty} b_i = \lim_{i \to \infty} (f_{odd}^{(i}f_{even}^{(\sum_{j=1}^ik(j)})(n) =
\lim_{i \to \infty} (f_{odd}^{(i}f_{even}^{(i<k>})(n)
\end{equation}
And $<k>=2$ is the average value of $k(i)$, therefore after some algebra:
\begin{equation}
\lim_{i \to \infty} a_i =\lim_{i \to \infty} b_i =
\lim_{i \to \infty} \left (\frac{3^in}{4^i}+ \sum_{j=1}^i {\frac{1}{4^j}} \right ) =\frac{1}{3}
\end{equation}
But the lowest number we can reach with function f is one, and therefore that is the limit of the sequence.
Maybe a good one, sorry for bothering
The Collatz conjecture as stated in Wikipedia says that if we define the following function over the natural numbers;
\begin{equation}
f(n)= \left \{
\begin{split}
n/2 &\text{ if } n \equiv 0 \pmod{2}\\
3n+1 &\text{ if } n\equiv 1 \pmod{2}
\end{split}
\right .
\end{equation}
And build a sequence, starting in any arbitrary natural number as follows:
\begin{equation}
a_i= \left \{
\begin{split}
n &\text{ for } i=0\\
f(a_{i-1}) &\text{ for } i>0
\end{split}
\right .
\end{equation}
that is: $a_i$ is the value of $f$ applied to $n$ recursively $i$ times; $a_i = f^{(i}(n)$.
The Collatz conjecture is: This process will eventually reach the number 1, regardless of which positive integer is chosen initially.
Now, let be $a_j$ an arbitrary number in a sequence built with the specified method. If $a_j$ is an odd number, then $a_{j+1}$ will be even. On the other hand, if $a_j$ is even, then $a_{j+1}$ can be even with a probability $1/2$, $a_{j+2}$ with a probability $1/4$ and so on.
Now let's build the sequence $b_i$ of odd numbers that results of applying function f. Assuming we start with an odd number, and after i iterations we will obtain:
\begin{equation}
b_i= (f_{odd}^{(i}f_{even}^{(\sum_{j=1}^ik(j)})(n)
\end{equation}
Where to obtain each odd element of the sequence from the previous one we had to compose the odd part of f which is $3n+1$ once and the even part of f or $n/2$ at least once.
Now, to prove the Collatz conjecture it is enough proving that the limit when $i\longrightarrow\infty$ is one or lower.
This can be done if we see that:
\begin{equation}
\lim_{i \to \infty} b_i = \lim_{i \to \infty} (f_{odd}^{(i}f_{even}^{(\sum_{j=1}^ik(j)})(n) =
\lim_{i \to \infty} (f_{odd}^{(i}f_{even}^{(i<k>})(n)
\end{equation}
And $<k>=2$ is the average value of $k(i)$, therefore after some algebra:
\begin{equation}
\lim_{i \to \infty} a_i =\lim_{i \to \infty} b_i =
\lim_{i \to \infty} \left (\frac{3^in}{4^i}+ \sum_{j=1}^i {\frac{1}{4^j}} \right ) =\frac{1}{3}
\end{equation}
But the lowest number we can reach with function f is one, and therefore that is the limit of the sequence.