Collatz conjecture 3n+1
So I'm out of my depth here but I thought this was an interesting unresolved mathematical problem which will help me to better understand what is understood as a mathematical proof (yes, you guys are going to have to explain that to me).
The question is: Does the Collatz sequence eventually reach 1 for all positive integer initial values?
The Collatz sequence is, for any positive integer do the following:
As a total math idiot, something I was thinking about. We know dividing by two will always yield either an odd or even number. Once in a while (for larger numbers), we also hit a number that if we divide by 2 we can keep doing that until we reach 1. That series could be infinitely long. So regardless of the number we start with, if we keep going through the two steps of the Collatz sequence we will hit such a number that we can continue to divide by 2 until we reach 1. Obviously, that's not true. Who can tell me more about this? Thanks!
The question is: Does the Collatz sequence eventually reach 1 for all positive integer initial values?
The Collatz sequence is, for any positive integer do the following:
- If the number is even, divide it by two.
- If the number is odd, triple it and add one.
As a total math idiot, something I was thinking about. We know dividing by two will always yield either an odd or even number. Once in a while (for larger numbers), we also hit a number that if we divide by 2 we can keep doing that until we reach 1. That series could be infinitely long. So regardless of the number we start with, if we keep going through the two steps of the Collatz sequence we will hit such a number that we can continue to divide by 2 until we reach 1. Obviously, that's not true. Who can tell me more about this? Thanks!
Comments (19)
EDIT: I guess my question is what constitutes mathematical proof. And why does my example not work as an (inductive) mathematical proof?
A mathematical proof for a target statement is a series of statements which logically/deductively show that statement. It can't show something 'like' the target statement, or even make the target statement almost certainly true, it has to show that the target statement is true. The standard is pedantically high.
Like trying to pass "It's red" implies "It's coloured" as a maths proof... Someone could interject "Only if you assume all red things are coloured". All the background knowledge that goes into the proof in principle should be able to be turned into formal math statements, even something as banal as "It's red implies it's coloured".
Quoting Benkei
The argument there seems to be because there's an infinitely long sequence that hits a number that 2 divides arbitrarily many times; call it "the stack"; that every other sequence must hit the stack. It makes some amount of sense as a conjecture, but there's no proof that a number hits the stack. That the stack is arbitrarily large provides no guarantee for the claim that every sequence hits it is true - there are lots of infinite subsets of the natural numbers, like the even numbers, and there being an infinity of them (even the same size of infinity as the naturals) doesn't entail there are no odd numbers. Even an infinity of sequences hitting your stack, and your stack being infinitely large, doesn't entail that every single number hits the stack right? All it takes is one.
The division by 2 being the only rule in the Collatz conjecture that decreases a given a number, something necessary if we're to end up with a 1.
With some algebraic manipulation,
[math]x = \frac{2^n - 1}{3}[/math]
Now where have I seen [math]2^n - 1[/math]
?
Welcome to my world!
The Greeks, back when Pythagoras was busy avoiding beans and mathematizing music, would've dismissed the above equation as complete nonsense! How can we add area to a line? That's not all, the equation goes on to say that area + line = volume!
Why doesn't it make a difference that it's a sequence? So yes, not every single number hits the stack but as long as the sequence continuously generates a new number, it is bound to?
So then the only real risk of it not being true seems to be the existence of a loop that doesn't contain the number 1. If you take 3n-1 instead of 3n+1 there are two other loops possible early on that don't contain the number 1. Makes me wonder what the meaningful difference is here between those two equations, which don't seem fundamentally different but yield such different results.
I don't see any reason why it should. Can you spell it out for me please?
This only gives an unlimited but partial set of valid values of x. The only values for which 3x+1=2exp(n) are x(k)=sum(0 to k)2exp(2k).
For example 1, 5, 21, 85, 341, 1365, etc. Look at the differences: 2exp2, 2exp4, 2exp6, 2exp8, 2exp10, etc. A very small subset of the integers (but infinite!).
If you could show that for every x the serie following ends up at a value smaller than x, the conjecture would be proven. All integers up to 100 converge to 1.so if the 101 orbit ends on a number between 1 and 100 it will do. 101 goes to 304, which goes to 152, which goes to 76, so yes, it delivers. 102 goes 307, which goes 922, which goes 411, 1234, 617, 1852, 926, 463, 1390, 695, 2086, 1043, 3130, 1565, 4696, 2348, 1174, 587, 1762, 881, 2644, 1322, 661, 1984, 992, 496, 248, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 345, 1036, 518, 259, 778, 389, 1268, 634, 317, 952, 476, 238, 119, 358, 179, 538, 269, 808, 404, 202, 101, heeee, we had that already, so it delivers!
But now the crucial point:
9, 18, 36, 72, 144, 288, 596, 1192, 2384, 4768,.....
and
12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144...
and
15, 30, 60, 120, 320, 640, 1280, 2560, 5120...,
will never be part of a series running backwards nor forwards, except as starting point (you can check this by looking at the numbers in the row above, and I used this in fact to correct a number I calculated wrongly). So you always have to check these numbers separately. Which looks like a considerable reduction, but still are infinite numbers....
You have to be more specific than this to help answer Benk's question "what constitutes mathematical proof?"
A math proof is a series of accepted /proven statements in the form of axioms and theorems such that the collatz assumption is guaranteed a true conclusion. (collatz may not be a good example here).
So, even numbers can be divided evenly by 2 is an axiom -- Benk did not even question that. :up:
So, all numbers 1 to 100, by the Collatz procedure converges to 1. We could use this as a starting point then and a proof would only need to show that for [math]x \geq 101[/math], the Collatz process utlimately takes us to a y such that [math]1 \leq y \leq 100[/math]. Neat trick!
What do you think of the fact that [math]3n + 1[/math] is a straight line and [math]2^m[/math] is an exponential function? As far as I know, a straight line and an exponential graph intersects at a maximum of only two points. Is this relevanat? :chin:
Probably my idea of infinity is mathematically wrong and therefore the above is gibberish.
15, 30, 60, 120, 240, 480, 960, 1920, 3840, 7680.....
The function f(n) = 2*n for any input n generates every even number. It generates infinitely many of them. Putting in n=1 gives you f(1)=2*1=2, putting n=2 gives you f(2) = 2*2=4 etc. But you'll never find an odd number in that list. If you put in "all" the starting numbers:
{1,2,3,4,5,6,7,8,...}
into f, you get:
{2,4,6,8,10,12,14,16,...}
All the even numbers. Both lists are infinite. But the latter list (the even numbers) doesn't contain any odd numbers:
{1,3,5,7,9,11,..}
Odd numbers infinite, even numbers infinite, no overlap. Being infinite doesn't give you a guarantee like that I think.
This is not how it works. All even numbers I mentioned in the previous comment, will orbit back to 9, 12, or 15. But they can't be part of a series except as a starting number.
There are no orbits that include these, except as starting numbers. The chances you hit a power of 2 grow smaller for increasing n. For 21 you already hit it the first time. There are very few numbers. So every backward part of orbits that hits 21 hits 64. You can backwards hit 5, giving 16. But only very few hit one as part of a forward path. So going backwards you have to hit a power of 2, while in going forwards this holds for limited numbers for starter values. Usually 5 gets hit. Which goes from 16 to 8, 4, 2, 1. When numbers grow, 21, 85, 341, 1365, etc. can be hit backwards, giving rise to a direct line to 1 (so they can't be produced forwards).
In fact, the whole problem is reduced to show the conjecture for only the numbers 9x2exp(n), 12x2exp(n), and 15x2exp(n). Still an infinity.
You can compare only the functions 3x+1 and 2exp(x). For comparing 3n+1 and 2exp(m) there are only the solutions I mentioned:
For example 1, 5, 21, 85, 341, 1365, etc. Look at the differences: 2exp2, 2exp4, 2exp6, 2exp8, 2exp10, etc. A very small subset of the integers (but infinite!).
In general: x(k)=sum(0 to k)2exp(2k). This gives rise to the row 1, 21, 85, etc.
The whole point of this proof is that it can only be proven by trying. Like Goldbach's conjecture, i.e, all even numbers can be written as the sum of two even numbers (8=3+5, 16=3+13, 30=13+17, etc). No matter what you try, it must be directly shown.
That's all from me.