Talamathi

The last time I talked about the 3x+1 Problem, I gave a basic overview of what it is. Today, I will talk about some (basic) ways to speed up the search for a counterexample, and next time I will introduce the Structure Theorem for the 3x+1 Problem. Part I : An introduction to 3x+1 Part II: Basic algorithm speedups (this one) Part III: The Structure Theorem I suggest reading from the beginning if you do not know what the 3x+1 (Collatz) Problem is. To get starting on thinking of some simple reasoning can do in speeding it up, here is some pseudocode of a naïve implementation of an algorithm that forever checks numbers. After it checks that a number goes to 1, it moves on to the next. repeat with x from 1 to forever set testMe to x while testMe is not 1 do if testMe is odd then set testMe to 3*testMe + 1 else -- It must be even set testMe to testMe divided by 2 end if end while end repeat Somewhat ironically, we wil...

Right now, I am currently working on a paper related to the 3x+1 Problem, so I thought I would write up a short primer to a truly beautiful theorem involving a truly interesting mathematics problem that almost certainly has no bearing on anyone’s day-to-day life. Unfortunately, it has ended up being a rather large post, so I have decided to split it up in to a few pieces. As I do them, I will add links here. Part I: An introduction to 3x+1 (this one) Part II: Basic algorithm speedups Part III: The Structure Theorem Wikipedia has a decent primer on the 3x+1 Problem, A.K.A. the Collatz Conjecture. But it's also very easy to state what turns out to be a very difficult problem. Say I tell you to pick any whole number (i.e., an integral number that is 1 or bigger). Now: If the number you picked is odd, multiply it by 3, and then add 1 (hence, 3x+1). If the number you picked is even, divide it by two. Repeat the last two steps until you hit 1. So that is what you do . Before getting t...