Difference between revisions of "Collatz Problem"

m
 
Line 1: Line 1:
 
Define the following [[function]] on <math>\mathbb{N}</math>: <math>f(n)=\begin{cases} 3n+1 & 2\nmid n, \\ \frac{n}{2} & 2\mid n.\end{cases}</math> The Collatz conjecture says that, for any [[positive integer]] <math>n</math>, the sequence <math>\{n,f(n),f(f(n)),f(f(f(n))),\ldots\}</math> contains 1. This conjecture is still open. Some people have described it as the easiest unsolved problem in mathematics.
 
Define the following [[function]] on <math>\mathbb{N}</math>: <math>f(n)=\begin{cases} 3n+1 & 2\nmid n, \\ \frac{n}{2} & 2\mid n.\end{cases}</math> The Collatz conjecture says that, for any [[positive integer]] <math>n</math>, the sequence <math>\{n,f(n),f(f(n)),f(f(f(n))),\ldots\}</math> contains 1. This conjecture is still open. Some people have described it as the easiest unsolved problem in mathematics.
 +
 +
==Properties of <math>f(n)</math> ==
 +
 +
Self similarity of <math>f(n)</math> follows from generalizing <math>n</math> to an integral, integer coefficient polynomial. If <math>n=2^zx+b</math> for example, it can be shown by parity argument, that <math>n</math> has the same parity as <math>b</math>. It then follows, that same conditional path will be followed by <math>n</math> as it was for <math>b</math>; any time the lead coefficient still has a factor of 2.
 +
 +
Observing that if <math>n=2m+1</math> then <math>3n+1=6m+4</math>, as well as: <cmath>{6m+4\over 2}=3m+2</cmath> we can then observe that; only if <math>m</math> is even will another division by 2 be possible.
 +
 +
The above observation leads to 2 important points about <math>n=4c+3</math>; namely they are the only possible lowest elements of a non-trivial cycle, and also the only possible lowest elements of an infinitely increasing sequence.
  
 
[[Category:Number theory]]
 
[[Category:Number theory]]
 
[[Category:Conjectures]]
 
[[Category:Conjectures]]

Latest revision as of 19:45, 24 February 2020

Define the following function on $\mathbb{N}$: $f(n)=\begin{cases} 3n+1 & 2\nmid n, \\ \frac{n}{2} & 2\mid n.\end{cases}$ The Collatz conjecture says that, for any positive integer $n$, the sequence $\{n,f(n),f(f(n)),f(f(f(n))),\ldots\}$ contains 1. This conjecture is still open. Some people have described it as the easiest unsolved problem in mathematics.

Properties of $f(n)$

Self similarity of $f(n)$ follows from generalizing $n$ to an integral, integer coefficient polynomial. If $n=2^zx+b$ for example, it can be shown by parity argument, that $n$ has the same parity as $b$. It then follows, that same conditional path will be followed by $n$ as it was for $b$; any time the lead coefficient still has a factor of 2.

Observing that if $n=2m+1$ then $3n+1=6m+4$, as well as: \[{6m+4\over 2}=3m+2\] we can then observe that; only if $m$ is even will another division by 2 be possible.

The above observation leads to 2 important points about $n=4c+3$; namely they are the only possible lowest elements of a non-trivial cycle, and also the only possible lowest elements of an infinitely increasing sequence.

Invalid username
Login to AoPS