1

Sorry for the long title. I first of all want to say that I'm just a high school student who spent today looking into the Collatz conjecture. I, first of all, would like to know if it's known whether there exist such a cycle that never divides by $2$ more than one time between the increasing parts. I know that the conjecture is still unsolved, so in other words what I'm saying is: has anyone proved that no such cycle exists?

The reason I'm asking is because I believe I may have found a proof of that there can't exist such a cycle that starts with $n$ if $n>4$. But the proof is probably incorrect, or already proved by someone else.

So, does anyone know if someone has proved this, and, can such a proof help solving the whole conjecture? If no one has proved this, I could post the "proof" here so you professionals could find the mistakes.

Note: by "increasing part", I mean the 3n+1 part and not the (3n+1)/2 part.

Regards, John

John
  • 41
  • 6
  • 1
    I do not understand what exactly you are asking about. The conjecture remains unresolved. – davidlowryduda May 09 '17 at 21:57
  • Any cycle must contain an odd number and any odd number in the cycle must be reached by division by $2$...and there is no recognized proof that there are no non-trivial cycles. – lulu May 09 '17 at 22:07
  • I'm sorry, I wrote my post wrong. I have edited it now. Sorry. – John May 09 '17 at 22:11
  • 1
    Since ${3a+1\over 2} \gt a$ for $a \gt -1$ (and this means, the iteration gives increasing values) there cannot be a cycle in the positive integers with only one halving-step between the $3a+1$-steps. – Gottfried Helms May 09 '17 at 23:08

1 Answers1

2

No, there can be no such cycle, and the proof is straightforward (and this might be the one you found - if so, congratulations! coming up with a proof on your own is a great thing):

Suppose there were such a cycle. Remember that each of the odd-number steps immediately yields an even number; so this determines the form such a cycle can have: if $a_1$ is a term in the cycle which is even, then two terms later we're left with $a_2={3a_1\over 2}+1$, which is even and strictly greater than $a_1$; proceeding by induction, if we let $a_n$ be the $(2n-1)$th term, starting with $a_1$, then we have $a_1<a_2<a_3<$...

So this can't be a cycle, since it gets arbitrarily large (any cycle is finite, and thus has an upper bound). Note that the sequence $1, 4, 2, 1, 4, 2, ...$ involves consecutive division-by-twos, and so isn't in fact a counterexample or special case.

A natural next step is to extend this beyond $1$; that is, try to show that there is no cycle containing no more than two consecutive divide-by-twos (presumably by showing that there is no such cycle starting with a number above some certain bound, and then checking the smaller starting numbers by hand). Unfortunately, while this might be true (and of course is true if Collatz is), it won't be as easy to prove - following the odd-number case, two consecutive divide-by-twos can drop us below the starting number since ${3b+1\over 4}<b.$

So frustratingly, this does seem to be a special case - there's no obvious way to rule out broader classes of cycles using the same ideas. As far as I know, this is universally true of all progress made on the problem: while we can rule out certain specific kinds of counterexamples, they're all very special and ultimately the methods used don't give us any insight into the whole problem.

Noah Schweber
  • 245,398
  • That's true, and pretty obvius. I don't know why I didn't think of that. Thanks for the anwer! – John May 09 '17 at 22:26
  • @John How'd you solve it? – Noah Schweber May 09 '17 at 22:27
  • 3
    I made equations like (3((3n+1)/2)+1)/2 = n and found that n = -1. And -1 always gets back to -1 after two operations. So for any cycle that increases, decreases, and the increases again, -1 will be a starting point that gets back to itself after an even number of operations. So for any equation like the one above, -1 will be a solution. And since the equations doesn't get quadratic or something when you solve for n, there can only be one solution. And since -1 is always a solution, there can be no other solutions. – John May 09 '17 at 22:32
  • More to the point, $\frac{3x+1}{2}>x\forall x\in\mathbb{N}$ – it's a hire car baby May 14 '17 at 03:16