I was discussing the Collatz Conjecture with someone, who mentioned that if you pick a constant whole number, a, and a second whole number, x, and mapped x to $(ax+a)$ if x was odd and to $x/2$ if it was even, $x$ seemed to always hit $a$ at some point. He had no proof of this besides it having worked for all the numbers he had tried. I have proved it for $a=1, 2$. For $a=1$, x will get mapped to either $x+1$ if odd, or $x/2$. Since $x+1$ is even, the next step is division by two. Both $(x+1)/2$ and $x/2$ are less than $x$ for $x>1$. That means that either $x$ will decrease, or it will already equal a. If it decreases, it will get closer, and closer again on the next step. We are constrained to whole numbers, so we will hit a at some point. There is a similar proof for 2. What about higher values of a?
Asked
Active
Viewed 144 times
0
-
1Do you really mean $x\mapsto ax+x$, not $x\mapsto ax+1$ for $x$ odd? – Hagen von Eitzen May 26 '18 at 11:05
-
X is mapped to ax+a – William Grannis May 26 '18 at 11:13
-
1It does not work. If you have $a=5$ and start with $65$, it goes $65,330,165,830,415,2080,1040,520,260,130,65,\dots$. – Sil May 26 '18 at 11:19
-
How did you find that? If you put it in an answer, I'll accept it. – William Grannis May 26 '18 at 13:11
1 Answers
1
For $a=1$ actually $x$ will be mapped to $2x$ if it is odd and then $2x$ will become $x$ again so if $x\ne{}1$ it doesn’t converge to $a=1$. Every odd number indeed repeats itself. Also note that for any odd $a$ you get terms of the form: $((a+1)/2^k)^nx$ Where $2^k$ is the largest power of 2 dividing $a+1$. And thus $d^nx$ which if $d\ne{}1$ ( or equivalently $a+1$ isn’t a power of 2 ) diverges to infinity for any odd x (and even x that isn’t a power of 2).
Μάρκος Καραμέρης
- 1,748
- 11
- 22
-
A is equal to one, and it doesn't need to converge or stay at a, only to hit it. Not every odd number repeats t – William Grannis May 26 '18 at 10:35
-
1
-
-
-