Tell me, Veeky Forums: am I retarded or is everyone retarded but me?
Just to state the obvious for the moment, if n is odd 3n+1 will always be even. And with the exception of the number 1, if you take 3n+1 and divide that by 2 twice (or divide it by 4 once if you prefer) the result will be less than n. The larger the number n, the larger the difference between n and (3n+1)/4 will be.
now for the part that I'm a bit iffy about (though I'm not really a mathfag so this might be obviously right or wrong to most of you): In order to prove that this sequence will reach 1, all you really need to prove is that it trends downward until that point since you are only working with integers, correct? Any sequence of integers which trends downward will reach 1 eventually.
Assuming this is true, you only need to prove that there are around twice as many even numbers in the sequence than odds. The larger the number you start with, the smaller the ratio of evens to odds will need to be. Well let me put it this way: 50% of even numbers, when divided by 2, will yield an odd number. 100% of odd numbers, when multiplied by 3 and then added to 1, will yield an even number. So how many more even numbers will tend to be in a sequence than odd numbers? Twice as many. And since (3n+1)/4
It's a probabilistic argument with inevitable results. Let's say you do have a cluster where the number keeps on growing for a while. That will end eventually and then you will be right on course towards the bottom. And the larger the number n, the faster it will tend to shrink. Since you can extend the sequence indefinitely (or until you reach that 1, 2, 4, 1 loop) it appears inescapable to me that, after enough iterations, you will reach the bottom.
Juan Campbell
>1, 2, 4, 1 loop) 1, 4, 2, 1 loop*
Owen Ortiz
and another correction while im at it: there's 3 times as many evens in the sequence, not 2 times.
Hudson Garcia
>it appears inescapable to me that, after enough iterations, you will reach the bottom. it appears inescapable to everybody
if "it feels true" was a proof it would be the Collatz theorem
Jayden Hall
I envision a proof would involve finding some way to quantify a number's "distance" from the sharp drop, then showing that every number necessarily becomes closer with each iteration.
Liam Russell
The whole point is that you have to prove that there is no loop except 1, 2, 4, 1,
Btw, these two sentences are mere assumptions >That will end eventually and then you will be right on course towards the bottom. And the larger the number n, the faster it will tend to shrink.
Jaxon Johnson
>That will end eventually and then you will be right on course towards the bottom That was actually ill placed hyperbole. Obviously, there will be numbers which will grow, then shrink, then grow again. But if you think there's a number which always grow, what you are actually asserting is that there's a number which will make the pattern "even, odd, even, odd, even, odd" indefinitely. since every instance of an even number has a 50% chance of resulting in an odd number, you are looking for a probability of (1/2)^x where x is the number of iterations. Since this is indefinite growth, x would effectively be infinity. this results of a probability of 1/[infinity] or effectively 0.
>And the larger the number n, the faster it will tend to shrink. This isn't an assumption at all. Like I said before: the difference between n and (3n+1)/4 is larger as the number grows larger.
>prove that there is no loop except 1, 2, 4, 1 (3n+1)/4n for all integers shows that, unless your loop contains 1 as one of its integers, it will not loop.
Easton Fisher
>you are actually asserting is that there's a number which will make the pattern "even, odd, even, odd, even, odd" indefinitely. No A pattern which contains 3 even numbers and 2 odd numbers would still grow (since 3*3*n/2/2/2 > n), and there are arbitrarily many such "larger" patterns which are theoretically possible
>since every instance of an even number has a 50% chance of resulting in an odd number, you are looking for a probability of (1/2)^x where x is the number of iterations. Since this is indefinite growth, x would effectively be infinity. this results of a probability of 1/[infinity] or effectively 0. Only if you can prove that a second loop does not exist
>This isn't an assumption at all. Like I said before: the difference between n and (3n+1)/4 is larger as the number grows larger. 3n+1 is not necessarily divisible by 4
>(3n+1)/4n for all integers shows that, unless your loop contains 1 as one of its integers, it will not loop. No, it only shows that there is only one "simple" loop which contains only 3 steps. There could still more loops that contain 20, 37 or 288 steps
Lucas Rivera
>The whole point is that you have to prove that there is no loop except 1, 2, 4, 1, not only that, but you need to prove every number goes into that loop
there's the 'are there any more loops?' question and the separate question of whether some number just goes off to infinity without ever looping
Colton Campbell
>The whole point is that you have to prove that there is no loop except 1, 2, 4, 1, t. brainlet.
Jaxon Hernandez
ITT: OP unironically decided to copy paste the "a probability heuristic" part of the wikipedia page on the Collatz Conjecture, reworded it like if he was retarded (he probably is) and then made a thread about it.
Alexander Ross
induction on size of of prime factors base case, true for n=3^L all L exercise for reader induction let n = p_1*p_2*...*p_r*2^k for p_i odd primes, k+1 in N WLOG p_1 largest of the p_i's n->n/2->...->p_1*...*p_r->(3(p_1)-1)*p_2*...*p_r =2^t*q_1*...*q_l*p_2*...*p_r->...-> but q_i
Joshua Wood
>3 even numbers and 2 odd numbers would still grow well no two odds can be back to back. so you are certainly saying "even, odd, even, odd,even" or "odd, even, odd, even, even" either way, you're wrong.
Christopher Ward
also, there's even even odd even odd, but this will necessarily be followed by an even
Cooper Butler
odd, even, even, odd, even repeat forever
Isaac Fisher
This is what you just said. Think about it.
Leo Smith
fuck, i fucked up
Chase Rodriguez
And? I wasn't talking about loops there, but about the general possibility of growing patterns different from odd, even, odd, even, ....
Justin Williams
The probabilistic is crap. A proof would look like this: lets say we have a function f() and g(). f is doing (an odd number)*3+1 and g is doing (an even number)/2.
so we have O -> f() -> E wich reads like "odd becomes even when applying f()" and E->g()->(O | E) wich reads like "Even becomes odd or stays even when applying g().
Then we need to connect this like O -> f() -> E -> g()->(O | E) ...
Protip: to break the collatz conjecture add the following statement "if an even number -1 is dividable by 3, do *3 and +1 instead of dividing by 2" this will make the sequence grow indefinitely.
I've invented a method to tell the factors of an odd number*3+1 just by counting how often you can apply (x-1) /3 % 3 == 0 to that odd number. But I dont know if its of any value so its just sitting in my drawer until I know its any good.
Colton Carter
all memes aside, apart from the 3^L exercise for reader part, is the rest of the argument coherent assuming the base case is true?
my induction is rusty
Aiden Howard
>is the rest of the argument coherent assuming the base case is true I dont even get the argument. When youre trying to prove the Collatz you have to be extra retarded in your explanation because a) you will notice whats the problem with your approach and b) more people will participate in the conversation.
Evan Lopez
nvm my mistake was pretty silly
Jaxson Barnes
the sequence reaches 1 50% of the time. Either it reaches 1 or it doesn't.
Connor Sullivan
what if n is not an integer
Aiden Russell
Then the conjecture doesnt make any sense
Adam Clark
>all these pointless arguments over odds and evens
Let C:N->N be the usual Collatz recurrence and define the function C':N->N by
C'(n) = 3n+1 if n is odd C'(n) = m if n=m*2^b with b>0
In other words, C' behaves like C for odd n (returning an even number), but if given an even n it does all the halvings in a single iteration, returning an odd number. This replaces at most finitely many iterations of C, since you can only halve a (finite, nonzero) even natural number finitely many times.
Then C' always behaves as odd->even->odd->even ... and has the same property of converging iff C converges, i.e. iff the Collatz conjecture is true.
Andrew Gutierrez
What kind of stupid argument is this? Its also non rigorus as fuck.
Do the same thing with 5x+1 instead of 3x+1 and you will see it will always diverge. Just because you're applying /2 as often as you can doesn't mean the number gets always smaller.