1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Where's the flaw in this proof of the Collatz Conjecture?

  1. Jul 25, 2013 #1
    The conjecture states that:

    Given a positive integer n,

    If n is even then divide by 2.

    If n is odd then multiply by 3 and add 1

    Conjecture: by repeating these operations you will eventually reach 1.


    Let n be the smallest positive integer that is a counterexample to the conjecture.

    If n is even then it can be divided by two to give a smaller number, leading to a contradiction.

    Assume n = 4k + 1.

    Multiply it by 3, add 1, and divide by 2 twice.

    The result is 3k + 1, a number smaller than n, leading to a contradiction. Therefore n has the form

    n = 4k - 1.

    Multiply by 3, add 1, and divide by 2.

    The result is 6k - 1. If k is odd, then 6k - 1 is one more than a multiple of 4, which is impossible, therefore k is even, and n has the form

    n = 8k - 1

    Multiply by 3, add 1, and divide by 2.

    The result is 12k -1, with k necessarily even. In this manner it can be proved that n must have the form 16k - 1, 32k -1, 64k -1, and so on, requiring n to be infinitely large, which is impossible.
  2. jcsd
  3. Jul 25, 2013 #2
    Why must this k necessarily be even? Keep in mind that you are using the same letter k for two different quantities when you write n=4k-1 and n=8k-1 so showing that k is even in the first expression does not mean that the second k is.
  4. Jul 25, 2013 #3
    Well, I'm trying to say that n has the form of a number with a remainder of -1 for some power of 2.

    The number 12k - 1 can be written as 8k + 4k -1, and the number has to have a remainder of -1 mod 8, therefore 4k is a multiple of 8, and k is even. My argument is that these operations always require k to be even, that there is a repeating pattern. All I can do is post it and see how others see it.
  5. Jul 25, 2013 #4
    Ok, I see your argument now. Can you explain your n=4k-1 case? You conclude that n=6k-1 and that k can not be odd because it would be one more than a multiple of 4. However, you only showed that the smallest counterexample could not have this form but 6k-1>4k-1=n, where n is the smallest counterexample so I don't see the problem.
  6. Jul 25, 2013 #5
    I'm attacking the problem in two different ways:

    One, by proving that a number is reached that is smaller than n; two, by proving that n must have a remainder of -1 for a still higher power of 2.

    The fact that 6k -1 > 4k -1 doesn't apply here. Once it is proven that k is even in 6k -1, then n not only has the form 4k -1, but it necessarily has the form 8k - 1.
  7. Jul 25, 2013 #6
    And I'm disputing that the k in 6k-1 must be even. It doesn't matter whether 6k-1 is a one more than a multiple of four or not since it would not be the smallest counterexample even if it was (4k-1 would be).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook