Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've had a thought about the Collatz conjecture (the 3n+1 problem).
Suppose some number, C, diverges under the iteration. We first note that C must be odd because if C were even it would be halved immediately, and so $\frac {C}{2}$ would be the lowest.

Take some arbitrary power of 2, $2^a, a>1$, and let us perform the iteration on $2^a +1$
$2^a+1$ is odd, so we go to $3*2^{a}+4$, then to $3*2^{a-1}+2$ and to $3*2^{a-2}+1$
Since we observe that $3*2^{a-2}+1 < 2^{a}+1$, C cannot be of the form $2^a+1$.

Now suppose we have some number n which definitely goes to 1. We now perform the Collatz iteration on $2^{a}+n$. The parity of this number is identical to the parity of n.
If we were to perform 3n+1, then we would have $3*2^{a}+3n+1$
Indeed, since the parity of the number is determined by n, the iteration (i.e. whether we triple and add one or halve) is identical to that of n.

If we say there are $\alpha$ '3n+1's and $\beta$ '$\frac{n}{2}$'s, this gives us the expression
$\frac{3^{\alpha}}{2^{\beta}}*2^{a}+1 < 2^{a}+1 < 2^{a}+n$ (provided $\frac{3^{\alpha}}{2^{\beta}}<1$)

We know this is the same iteration which n must undergo, and we know that when n is iterated, we will arrive at the following:
$\frac{3^{\alpha}}{2^{\beta}}n+k=1 > \frac{3^{\alpha}}{2^{\beta}}n$
Where k is some positive constant dependent on the order of the iterations. This implies that $\frac{3^{\alpha}}{2^{\beta}}<1$.
So, as we had with the case n=1, provided that n goes to 1, $2^{a} +n$ goes to 1.

Now suppose we had verified the case of the collatz conjecture for some small numbers; say 1 and 3. Not only is it true for n=1 & 3, but it is also true for 5,7,9,11,17,19, etc.
And since it is true for 1,3,5,7... it must be true for 9,11,13 and 15, from which we can say it is true for 17,19,21 and so on for all odd whole numbers.

And therefore our number C at the start is neither odd nor even, and so there is no smallest number which diverges to infinity. In fact, if we say that C could be the smallest element in a cycle then we would also have a contradiction.

Is this legit? I've probably made an error somewhere, but I figured it was worth putting it on here since it might get some attention. Thank you for your time.

UPDATE: It has been pointed out that there is a flaw in the argument. Specifically, that we have assumed that a, the power on 2, Is larger than $\beta$ when, in general, it is not. The consequence of this is that certain numbers, specifically those of the form $2^{a}-n$ where a is any integer greater than 1 and n is either 1, 5 or 17. For example, if we take $2^{4}-5=11$, we have:
$2^{4}-5 \rightarrow 3*2^{4}-14 \rightarrow 3*2^{3}-7 \rightarrow 3^{2} * 2^{3}-20 \rightarrow 3^{2} * 2^{2}-10 \rightarrow 3^{2} * 2^{1}-5 \rightarrow 3^{3} * 2^{1}-14 \rightarrow 3^{3}-7 $
Apologies for the rather messy notation but it helps us to see what is going on. First of all, we see that 4 has been reduced to nothing without us learning very much about the number (certainly not whether it decreases). We also note that in the 1st and 6th terms 5 appears on the end - this is because when we extend the iteration into negative integers, there are more cycles than 1-2-4, and their smallest elements are precisely -1, -5 and -17.

share|improve this question
    
What is the "parity" you speak of? Neither of the two meanings of that word I know are preserved by the addition of arbitrary powers of 2. –  Henning Makholm Apr 26 '12 at 19:45
    
Whether a number is odd or even. The power of 2 is even, so the parity is that of n. –  Daniel Littlewood Apr 26 '12 at 19:56
    
$2^0$ was not even last I checked. And even if you take $a>1$, it may be that $3n+1$ is a multiple of $2^b$ where $b>a$. In that case, as you divide by $2$ repeatedly, suddenly the $3\cdot2^a$ term is going to reach 1 before the $3n+1$ term does. –  Henning Makholm Apr 26 '12 at 19:57
    
This is true, but note that if a>1 and b>1, then we will have 2 consecutive divisions by 2 and only only multiplication by 3, which decreases the number to less than we started with. I think your issue is the same gap we have realised below. –  Daniel Littlewood Apr 26 '12 at 20:05
    
Just a sidenote: it is usually "better" to consider the function which sends odd numbers $n$ to $(3n + 1)/2$. Note that this can be done, since $3n + 1$ is always even for odd $n$. Then it is also obvious that $n$ and $2^a + n$ follow the same pattern for exactly $a$ iterations. –  TMM Apr 28 '12 at 15:10

2 Answers 2

up vote 5 down vote accepted

The following part of the argument seems to be problematical.

"Now suppose we have some number n which definitely goes to $1$. We now perform the Collatz iteration on $2^{a}+n$. The parity of this number is identical to the parity of $n$.
If we were to perform $3n+1$, then we would have $3*2^{a}+3n+1$
Indeed, since the parity of the number is determined by $n$, the iteration is identical to that of $n$."

The first example I tested had $n=3$ and $2^a=8$. So $2^a+n=11$.

The Collatz sequence with first entry $3$ goes $$3, 10, 5, 16, 8, 4, 2, 1.$$

The Collatz sequence with first entry $11$ goes $$11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.$$

The iterations are not identical.

It is true that if $a$ is fairly large, and $n$ is not, then the patterns of odd and even will, for a while, be the same. In our example above, they were the same until the sixth number.

share|improve this answer
    
The sequence for 3 is: 3n+1, n/2, 3n+1, n/2, n/2 The sequence for 11 is: 3n+1, n/2, 3n+1, n/2, n/2 The reason that past this the iterations are not identical is because we have halved 3 times and the power of 2 (8) isn't there any more. This reveals a hidden assumption - that a is sufficiently large. I don't know if this would have any serious consequences for the argument. –  Daniel Littlewood Apr 26 '12 at 19:47
    
The actual size of n isn't relevant - it's how many times we divide by 2. The number of divisions by 2 must be less than the value of a we choose. In other words, $a>\beta$ –  Daniel Littlewood Apr 26 '12 at 19:55
    
@DanLitt: The answer pointed to a gap in the argument. Perhaps that gap can be filled. –  André Nicolas Apr 26 '12 at 19:59
    
While I haven't yet found a way to eliminate these problematic numbers, I think I can show that they are of the form $2^{a}-n$ where n is either 1, 5 or 17. This is because -1, -5 and -17 are the lowest elements of cycles in collatz on the negatives. –  Daniel Littlewood Apr 28 '12 at 13:59
    
It is not an area in which I have research experience. The literature is large, and there has been a lot of computation, so I am not hopeful of "small" regularities. However, I would not be shocked if a clever argument settled the problem. –  André Nicolas Apr 28 '12 at 14:11

If I got your thinking correctly, then the key, or better:the general aspect, for your observation is the following transfertable (where $k$ is a nonnegative integer): $$ \small \begin{array}{r|rrcrr||r|rrcrr} \text{class} &a&&\to&b&&\text{class}&a&&\to&b\\ \hline \\ 1& 2^1 \cdot 2k &+ 3 &\to& 3 \cdot 2 k &+5 & 2& 2^2 \cdot 2k &+ 1 &\to& 3 \cdot 2 k &+1 \\ 3& 2^3 \cdot 2k &+ 13 &\to& 3 \cdot 2 k &+5 & 4&2^4 \cdot 2k &+ 5 &\to& 3 \cdot 2 k &+1 \\ 5& 2^5 \cdot 2k &+ 53 &\to& 3 \cdot 2 k &+5 & 6&2^6 \cdot 2k &+ 21 &\to& 3 \cdot 2 k &+1 \\ ...&... &&\to&...&& & ...&&\to&...\\ A& 2^A\cdot 2k&+{5 \cdot 2^A-1\over3} & \to & 6k&+5& B& 2^B\cdot 2k&+{ 2^B-1\over3} & \to & 6k&+1& \end{array}$$ where $A\in \{1,3,5,7,...\}$ and $B \in \{2,4,6,8,...\}$
So what you seem to have observed is that if you have some (say "residue") $r \in \{3,13,53,213,853,...\}$ or $r \in \{1,5,21,85,341,...\}$ then you can add an associated power of $2$ and the transformation might be called to be of the same "class".
The table above shows that this observation might even be generalized: not only is it possible to add a suitable power of $2$ but even arbitrary many version with $k$'th multiples of that power can be said to "belong to the same class".
Your additional observations involving the domain of the negative numbers are still matched if you introduce negative $k$ in the above table. And moreover: once we allow negative numbers, then it might be interesting, that the residue-class $3$ means also $-1 \pmod 4$ and thus $+1$ and $-1$ form the "trivial cycles" in class $1$ with $k=-1$ and class $2$ with $k=0$


If this is indeed what you were discussing then you might be interested in my (older and a bit imperfect) treatize where I've dealt with this observation. (Note that a similar table exists for all modifications $wn+1$ instead of the $3n+1$ in the Collatz-problem )

share|improve this answer
    
Wow, I didn't expect a comment on here after so long! This does look similar to what I had thought about the problem, and I'll be sure to look into it when I have the chance. –  Daniel Littlewood May 28 at 0:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.