Our reader Eswar Chellappa has sent his work on the solution of ‘3X+1’ problem, also called Collatz Conjecture. He had been working on the proof of Collatz Conjecture off and on for almost ten years. The Collatz Conjecture can be quoted as follow:

Let $\phi : \mathbb{N} \to \mathbb{N}^+$ be a function defined  such that:
$$\phi(x):= \begin{cases} \frac{x}{2}, & \text{if } x \text{ is even } \\ 3x+1, & \text{ if } x \text{ is odd} \end{cases}$$

Then the iterates of $\phi(x)$ will eventually reach $1$ for any initial value of $x$.

See this post about Collatz Conjecture for more details.

 Plenty of proof attempts were made by various mathematicians. But none of those could flawlessly prove the statement. Mr. Chellappa’s attempt is based upon the famous Sieve of Eratosthenes. Despite of his experience & confidence, I can not guarantee if this work is perfect. I invite readers to cross check the flawlessness and tell what they think.

 

Introduction

Let, $f(x) = x/2$ if $x$ is even and  $g(x) = 3x + 1$ if $x$ is odd. Since $3x+1$ is an even number for any odd $x$, we can replace any odd number by an even number which equals to $3x+1$. And when, $3x+1$ is an even number, we can successfully halve it according to first step of the function defined in the conjecture.

The method proposed below is similar to the famous Sieve of Eratosthenes

To start with the proof, choose the natural numbers from 1 to 100.

Since we have $$f(x) = x/2$$ for even $x$. Let’s strike out all even numbers for each of them reduces to another odd or even number (less than x) by f(x), by exactly one iteration. This we do from 100 to 2, in the decreasing order.

  • We strike out 100 as $f(x)$ reduces it to 50.
  • Then we strike out 98 keeping 49 as the result of one iteration.
  • 50 is also struck out giving 25 as result of one iteration.

Now all it remains, the odd numbers and natural number $1$. As $1$ automatically verifies the conjecture, we start from 3 and end to 99.

  • We have $g(3) := 10$. Since $10$ has already been struck out, we can simply say that $3$ satisfies the conjecture. Hence we strike out 3.
  • $g(5) := 16$, so 5 can also be struck out.

By this process we can strike out all odd numbers up to 33 as we have taken only numbers up to 100 and $g(35) >100$.

By suitably increasing the range of numbers we can conclude that ultimately $\phi (x)$ has to reach 1 irrespective of the starting natural number $x$.

Any possible worries?

The only possibility that might worry us was falling in to a loop. This happens only if $\phi_i(x) = \phi_j(x) \neq 1$ where $i\neq j$. But that is not possible since $\phi (x)=x/2$ is one to one.

Remark

  • By striking out the numbers, we verify that they have images under $f(x)$. That is to say, more iterations are possible until the sequence reaches $1$.
  • Concerned about $\mathbb{N}^+$ notation?

 

PS: This isn’t a paper.

Total
0
Shares


Feel free to ask questions, send feedback and even point out mistakes. Great conversations start with just a single word. How to write better comments?
12 comments
  1. This isn’t remotely a proof. Everything you wrote also applies word-for-word to the function $f(x) = x/2$ if x is even and $f(x) = 5x+1$ (instead of 3x+1) if x is odd. But the conjecture is false for this different function, since it contains the following loop: 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13

    In other words: you barely wrote a single thing that involves more than the fact that f sends even numbers to odd numbers and odd numbers to even numbers, and no such argument is going to be enough to prove the Collatz conjecture.

  2. Methyboy states precisely why this is not even remotely a proof.

    Let’s give an example based on the famous Collatz-number 27.

    Is 54 safe because it reduces to 27, which amounts to 82 only, which reduces again to a smaller number 41? Not at all, since 41 amounts to 124, which is outside the range 0..100. Since 3×41+1 exceeds 100, the proof does not apply to 41, but since since 41 can be reached from 54, the proof does not apply to 54 either.

  3. I was expecting to see some attempts using mathematical induction which restricts the case that disporves the conjucture to a number of the form 4n+3.
    Progressing through 1,2,3,4,5 etc. which we know support the conjecture, if we assume there is a number x that defies the conjecture, that number has to be of the form 4n+3. Because , 4n and 4n+2 will reduce to an already passed number. 4n + 1 will become (12n + 4)/2 = 6n + 2 in the next step and 3n+1 in next., again a number aready passed. Since the cycles of random length, it cannoot be supposed that 4n+3 will get reduced to diffent number mod 4 or a product of a suitable power of 2 in a predictable number of steps. Eager to learn about attempts in this route if any.

    1. Babu, you at least provide us with some notions of general applicability for attacking the problem, some of which it should be fairly easy to state and prove as lemmas. By collecting a group of lemmas of sufficient scope and power, we should then be able to reduce the problem cases to a handful or less.

      The sieve notion mentioned by the OP, if combined with mathematical induction as you suggest, could perhaps provide one such reduction or simplification of the problem domain. I invite all readers to try combining them to good effect!

      Elsewhere, I’ve seen statements to the effect that the most problematic cases all involve infinite cycles. (How hard that would be to show, I haven’t yet tried to ascertain. There’s a nice little project – best done oneself, for the benefit of the exercise! – before checking out others’ work.)

      In such a case, there would exist integers n>1 and x>1, such that ϕ^n(x)=x, but also, for all 1<i<n, ϕ^i(x)>1. Obviously, if we could show that this never happens, it would be a great step forward. Equally obviously, showing that won’t be easy, or it would have been done already by one or more of the thousands who’ve cracked their brains over the Collatz Conjecture. However, it’s worth thinking about how to break this problem down into different cases; for example, would any such n necessarily be even?

  4. Striking out in a sieve is not fun. We strike out composites in sieve after we know an integer is divisible by some smaller one. Here, 100 going to 50 doesn’t mean 100 will go to 1.. it means that 100 will go to 1 if 50 will go to 1 . So, it is nothing near a proof. But the idea is appreciable. But one should learn the concept of sieve before working ten years on a problem of such merit.

  5. You disappoint me. I really thought you had a proof for The Collatz Problem. Please stop creating click baits.

  6. I too have spent years on the solution. Recently I developed an infinite matrix that is remarkably fascinating. The matrix reveals clearly many insights that no one yet has discovered though solutions in calculus. Through it I have proven that for every number that divides a specific number of times, there is a closely associated number that goes up the exact same amount of times. The matrix also clearly proves why when we start at any number, no matter how large, it must ultimately descend back down to 1. It also shows why loops are not possible with the 3n+1 function, and makes clear why there are indeed loops if we replace the 3n+1 function with the 3n-1 function. My predicament it that no one in the mathematical elite group of individuals associated with math organizations will even take me seriously enough to see my proof by infinite matrix, and all that it reveals …much more than the three I posted here. I am inspired by your Blog here and will more than likely be creating one myself to post in great detail and explanation my infinite Colatz Conjecture proof by Matrix. Glad to have become a follower of you Blog!

  7. By striking out you mean that you are assuming that an even number will fall into an odd number and vice-versa, but i don’t think this in any way shows that this operation will converge to 1. from even it could go to odd and vice versa and this way this series could tend to infinity.

  8. This isn’t evenr remotely a proof. You fall in a circular idea. You can set aside the even numbers because they will automatically converge to 1 if the odd numbers converge to 1. But then you say the odd numbers are covered because they converge to an even number. In other words, You say that 10 holds the conjecture, and then 5 must hold it because it converges to an even number. But the reality is that you MUST prove first that it’s true for odd numbers, and then it will be automatically true for even numbers, not the other way around.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

You May Also Like

Irrational Numbers and The Proofs of their Irrationality

“Irrational numbers are those real numbers which are not rational numbers!” Def.1: Rational Number A rational number is a real number which can be expressed in the form of where $ a$ and $ b$ are both integers relatively prime to each other and $ b$ being non-zero. Following two statements are equivalent to the definition 1. 1. $ x=\frac{a}{b}$…

Analysis of Meteorological Data of Pantnagar Weather Station

About This post is actually a summary of a research project I took under INSPIRE-SHE Scholarship Program by Dept. of Science and Technology, Govt. of India. My plan was to make the content open-source on the web that faults could be corrected by time. The language is simple and very easy to understand and the ease of understanding is focused on…

Equations- A Basic Introduction

Applied mathematics is one which is used in day-to-day life, in solving troubles (problems) or in business purposes. Let me write an example: George had some money. He gave 14 Dollars to Matthew. Now he has 27 dollars. How much money had he? If you are familiar with day-to-day calculations – you must say that George had 41 dollars, and…

TeXStudio is the most complete LaTeX Editor

A detailed and practical review of one of the most amazing LaTeX editors available for all desktop platforms like Windows, Mac and Linux. TeXStudio is a team project of Benito van der Zander, Jan Sundermeyer, Daniel Braun and Tim Hoffmann, forked from the TeXMaker application, a non-open source application, which open-source development stalled in 2009.

Fox – Rabbit Chase Problems

Part I: A fox chases a rabbit. Both run at the same speed $ v$ . At all times, the fox runs directly toward the instantaneous position of the rabbit , and the rabbit runs at an angle $ \alpha $ relative to the direction directly away from the fox. The initial separation between the fox and the rabbit is…

Just another way to Multiply

Multiplication is probably the most important elementary operation in mathematics; even more important than usual addition. Every math-guy has its own style of multiplying numbers. But have you ever tried multiplicating by this way? Exercise: $ 88 \times 45$ =? Ans: as usual :- 3960 but I got this using a particular way: 88            45…