0
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Do you really mean $x\mapsto ax+x$, not $x\mapsto ax+1$ for $x$ odd? $\endgroup$ May 26, 2018 at 11:05
  • $\begingroup$ X is mapped to ax+a $\endgroup$ May 26, 2018 at 11:13
  • 1
    $\begingroup$ It 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$. $\endgroup$
    – Sil
    May 26, 2018 at 11:19
  • $\begingroup$ How did you find that? If you put it in an answer, I'll accept it. $\endgroup$ May 26, 2018 at 13:11

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$ May 26, 2018 at 10:35
  • 1
    $\begingroup$ But it doesn’t it just repeats like so: $x,2x,x,2x,...$ $\endgroup$ May 26, 2018 at 10:36
  • $\begingroup$ Sorry. Typo in the question. $\endgroup$ May 26, 2018 at 11:13
  • $\begingroup$ I fixed it. ax+a $\endgroup$ May 26, 2018 at 11:14
  • $\begingroup$ Ok I will delete this answer then $\endgroup$ May 26, 2018 at 12:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .