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 :
The Collatz conjecture says that, for any positive integer
, the sequence
contains 1. This conjecture is still open. Some people have described it as the easiest unsolved problem in mathematics.
Properties of ![$f(n)$](//latex.artofproblemsolving.com/e/e/f/eef0203e65664bd00b5f0325c5c5fcd81bcead8d.png)
Self similarity of follows from generalizing
to an integral, integer coefficient polynomial. If
for example, it can be shown by parity argument, that
has the same parity as
. It then follows, that same conditional path will be followed by
as it was for
; any time the lead coefficient still has a factor of 2.
Observing that if then
, as well as:
we can then observe that; only if
is even will another division by 2 be possible.
The above observation leads to 2 important points about ; 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.