I have exciting news today: The first ever joint paper by Monks, Monks, Monks, and Monks has been accepted for publication in Discrete Mathematics.
These four Monks’s are my two brothers, my father, and myself. We worked together last summer on the notorious $3x+1$ conjecture (also known as the Collatz conjecture), an open problem which is so easy to state that a child can understand the question, and yet it has stumped mathematicians for over 70 years.
The $3x+1$ problem asks the following: Suppose we start with a positive integer, and if it is odd then multiply it by $3$ and add $1$, and if it is even, divide it by $2$. Then repeat this process as long as you can. Do you eventually reach the integer $1$, no matter what you started with?
For instance, starting with $5$, it is odd, so we apply $3x+1$. We get $16$, which is even, so we divide by $2$. We get $8$, and then $4$, and then $2$, and then $1$. So yes, in this case, we eventually end up at $1$.
That’s it! It’s an addictive and fun problem to play around with (see http://xkcd.com/710/), but it is frustratingly difficult to solve completely.
So far, it is known that all numbers less than $20\cdot 2^{58}$, or about $5.8$ billion billion, eventually reach $1$ when this process is applied. (See Silva’s and Roosendaal’s websites, where calculations are continually being run to verify the conjecture for higher and higher integers.)
But what about the general case?
Let’s define the Collatz function $T$ on the positive integers by:
$T(x)=\begin{cases}\frac{3x+1}{2} & x\text{ is odd} \\ \frac{x}{2} & x\text{ is even}\end{cases}$.
Then the conjecture states that the sequence $x, T(x), T(T(x)), T(T(T(x))),\ldots$ has $1$ as a term. Notice that $T(1)=2$ and $T(2)=1$, so $1$ is a cyclic point of $T$.
We can draw a graph on the positive integers in which we connect $x$ to $T(x)$ with an arrow for all $x$, and color it red if $x$ is odd and black if $x$ is even. The portion of the graph near $1$ looks like this:
We just want to show that this graph is connected – that there are no other components with very large integers that don’t connect back to $1$.
Last summer, we started out with some previous ideas and partial progress. In 2006, one member of our family research team, my brother Ken M. Monks, demonstrated that it suffices to prove the conjecture for some arithmetic sequence in the Collatz graph. (The paper is available here.) With this as a starting point, we worked to understand how arithmetic sequences are distributed across the Collatz graph. Where do they occur? How far apart are their elements?
By the end of the summer, we realized that there was some beautiful structure in the Collatz graph lying before us. We proved several surprising number-theoretic results, for instance, that every $T$-orbit must contain an integer congruent to $2$ modulo $9$.
We’re not sure if this will lead to a proof of the conjecture, but we found a few big gemstones that might give us a boost in the right direction. A preprint of the paper can be found here:
http://arxiv.org/abs/1204.3904
Enjoy, and feel free to post a comment with any ideas on the conjecture you may have!
This is really cool, and congrats on the publication. I sometimes miss the beautiful things from when I studied math, so I’m glad your blog gives me a taste of it from time to time. I like the picture/design up top too!
Thanks Carola! Glad you’re enjoying it. Hopefully see you some time this fall.
I noticed that you investigated the modulus 2^k. 3*2^k is a good modulus to work with. “Least-residue” trees defined using this modulus have many interesting properties (Terras’ stopping time and admissible parity vectors are even involved). Congratulations on your publication!
I’m not a mathematician, but logic tells me that since there are an infinite number of values available for x, (same as saying you can never run out of values for x) then surely it must be impossible to finally prove the validity of the theory that any value of x will lead you back to 1. You can find ever increasing values for x that will lead you back to 1 without proving the theory, (only, with higher and higher values for x making it more and more probable without ever being able to reach a probability of 1). However, (though such a number may never be found), you only have to find one number that doesn’t lead back to 1, to disprove the theory.
Even though there are an infinite number of values for x there are also an infinite number of moves possible to get back to 1 if it doesn’t connect with pre-existing lines which do lead back to 1. Maybe working out the chances of it meeting or not meeting a pre-existing line is the way to go. From previous experiments that chance seems infinitely small.
Infinity doesn’t solve for everything though and The Collatz conjecture has two outcomes:
1) They all reduce to one
2) There is a magical (large!) number that actually drops into a loop where it gets bigger before dropping back to itself.
Infinity allows (if anything) for more ‘chance’ of a single magic number out there and the maximum steps do grow as you search for bigger numbers.
less than 10 is 9, which has 19 steps,
less than 100 is 97, which has 118 steps,
less than 1000 is 871, which has 178 steps,
less than 104 is 6171, which has 261 steps,
less than 105 is 77031, which has 350 steps,
would it be changing the problem if you made it when even, divide by two and add 1?
I think the point is that it’s either true or it’s false. So just one example of it being false with be sufficient evidence. To disprove the theory.
I just watched a video on this problem and simply thought, instead of looking for a number that doesn’t go down to one, couldn’t we simply start at one and see if it’s possible to get to every number in an attempt to find proof. I know this seems stupid but working backwards on a problem that we know the ending too only seems like the right thing to do.
3x+1 is 2 / 80 it dos not go to 4 2 1
What if the problem is false? If so, what leads you to trying to prove it to be true?
This problem is trivial to solve using binary integer math/logic . Assume you have an arbitrary binary integer of arbitrary length. Now look at only the two least significant bits. There are only four possible states: [00, 01, 10, 11]. A zero-zero state means you double right shift and bring the next upper two digits into our little state machine. This consumes two bits, thus reducing “entropy” towards zero. Sketching this out for each of the possible LSB states we can see that 00 process to XX while consuming two bits off the overall length. 01 consumes one bit, 10 consumes one bit, and 11 consumes zero bits bit is guaranteed to leave 01 in the LSB so will not be dead-locked. Thus, for any arbitrary string of binary digits, the 3x+1 || /2 processing will always consume all the bits. And just before the final bit is consumed the value will be “1”. Q.E.D
Addendum: I meant that the last bit consumed from the third bit and higher. Once we have 00000000.10 in the register, it will cycle back to …..000000.01 over and over per the algorithm.
The x can’t be (-1/3) ?? Or is that too simple to solve the equation? I assume many people must have used this number. Some sites say it must be a positive integer, in which case this answer obviously wouldn’t work.
Well this is like a dog chasing it’s tail. But the dog eventually has to stop to eat, drink or use the restroom.
I think the real point of this problem here is that some of us take longer than others but at some point we all become self-aware
Hi I think the problem answer is -1 and I love this blog