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

Click For Summary

Discussion Overview

The discussion revolves around a proposed proof of the Collatz Conjecture, which asserts that repeated application of specific operations on positive integers will eventually lead to the number 1. Participants examine the logical structure of the proof and identify potential flaws or assumptions within it.

Discussion Character

  • Debate/contested
  • Technical explanation
  • Mathematical reasoning

Main Points Raised

  • One participant outlines a proof that assumes the existence of a smallest counterexample to the conjecture and derives contradictions based on the forms of n.
  • Another participant questions the necessity of k being even in the expression 12k - 1, pointing out that the same letter k is used for different quantities, which may lead to confusion.
  • A different participant argues that the number 12k - 1 can be expressed in a way that suggests k must be even, proposing a repeating pattern in the operations.
  • One participant challenges the conclusion that n must have the form 6k - 1, arguing that the proof does not adequately show that this form contradicts the assumption of n being the smallest counterexample.
  • Another participant reiterates their approach of proving that a smaller number can be reached and that n must have a specific remainder for higher powers of 2, while disputing the necessity of k being even in 6k - 1.
  • Concerns are raised about the implications of k being even or odd in the context of the proof, with participants expressing differing views on the validity of these assumptions.

Areas of Agreement / Disagreement

Participants express differing opinions on the validity of the proof and the assumptions made regarding the forms of k. There is no consensus on whether the proof holds or where its flaws lie, indicating ongoing debate and uncertainty.

Contextual Notes

Participants highlight potential issues with the use of the same variable for different quantities, as well as the implications of assuming k must be even or odd in various expressions. These points remain unresolved within the discussion.

raycb
Messages
4
Reaction score
0
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.



Proof:



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.
 
Mathematics news on Phys.org
raycb said:
The result is 12k -1, with k necessarily even.

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.
 
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.
 
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.
 
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.
 
raycb said:
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.

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

Similar threads

Graduate About a natural extension of Collatz conjecture
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad Is this a proof of the Collatz Conjecture?
  • · Replies 8 ·
Replies
8
Views
3K
Undergrad Breakthrough in 3n+1 Problem: Collatz Conjecture
  • · Replies 7 ·
Replies
7
Views
6K
Graduate Is this Recursive Pattern in the Collatz Sequence Known?
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Proving Goldbach's conjecture by induction (or why it doesn't seem to work)
  • · Replies 10 ·
Replies
10
Views
3K
Graduate Can this proposition be proved in the Collatz conjecture?
  • · Replies 9 ·
Replies
9
Views
3K
Undergrad Questions regarding Kurepa's Conjecture
  • · Replies 1 ·
Replies
1
Views
3K
High School What Are the Variations of the Collatz Conjecture and Their Implications?
  • · Replies 11 ·
Replies
11
Views
3K
Graduate Is the Collatz Conjecture Finally Close to a Proof?
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Can this method be used to prove the Collatz Conjecture?
  • · Replies 3 ·
Replies
3
Views
3K