3 ms·
I think you are attempting to argue that, for at least some starting inputs (you specify an even initial input in several places), the first several steps will
by waterhouse 14y ago
I think you are attempting to argue that, for at least some starting inputs (you specify an even initial input in several places), the first several steps will produce a strictly smaller number, and therefore, if you repeatedly take several more steps, you must get smaller numbers that eventually reach 1.
For starters, that would only work if your argument applied to the entire set of outputs that you'd feed back in again as inputs. You may prove that 3 cycles will bring an even input to a lower output, but that output may be odd, in which case the next 3 cycles will not necessarily produce a lower output. In fact, after 6 cycles, the output may be greater than the original input. I shall drive the point home that any argument of this form must fail:
If you name any integer n, I can find a starting value such that the first 2n Collatz steps are "3n+1 n/2 3n+1 n/2 3n+1 n/2 ...", so that the output gets up to roughly (3/2)^n * [the input]--which can obviously be much greater than the input--as much greater as I want. This starting value is "any number that is 1 less than a multiple of 2^n", or, in more occult language, "any number that is 1 mod 2^n". Observe:
k * 2^n - 1 is odd.
=> 3n+1, we get 3k * 2^n - 3 + 1
3k * 2^n - 2 is even.
=> n/2, we get 3k * 2^(n-1) - 1
3k * 2^(n-1) - 1 is odd.
=> 3n+1, we get 9k * 2^n-1 - 3 + 1
9k * 2^n-1 - 2 is even.
=> n/2, we get 9k * 2^n-2 - 1
9k * 2^n-2 - 1 is odd.
=> 3n+1, we get 27k * 2^n-2 - 3 + 1
27k * 2^n-2 - 2 is even.
=> n/2, we get 27k * 2^n-3 - 1
27k * 2^n-3 - 1 is odd.
...
3^n * k * 2^0 - 1 might be odd or even, depending on k.
You might try, say, starting with n=127. By the above argument, that will go up to 2186 after 14 steps (and will be at 4372 the step before that).
By the way, I figured that stuff out by recursively saying:
We want the biggest result possible.
Therefore, we want the last step to be 3n+1.
Therefore we want the number before the last to be odd.
This number must have come from an n/2 step.
Therefore the number before that must be 2 mod 4.
We want this to have come from a 3n+1 step.
3n+1 is 2 mod 4; 3n is 1 mod 4; n is 3 mod 4.
n was 3 mod 4.
This must have come from an n/2 step.
n was 6 mod 8.
We want this to have come from 3n+1.
3n+1 is 6 mod 8; 3n is 5 mod 8.
Come to think of it, 5 is -3 mod 8.
Then, clearly, n is -1 mod 8.
n was -1 mod 8.
This came from n/2.
n was -2 mod 16.
We want this to have been 3n+1.
3n+1 = -2 mod 16; 3n = -3 mod 16; n = -1 mod 16.
n was -1 mod 16.
At this point, the pattern of "-1 mod 2^n" is
waving its arms and screaming in our face.
I'm a little embarrassed to admit that I took a much dumber approach, which I automated beyond "15 mod 16" (intending merely to provide some numbers and describe the procedure to get them), and didn't see until I saw the output that it was always 2^n - 1, and didn't know how to prove it until I wrote the above. Oh well.
- vy8vWJlco 14y ago"You may prove that 3 cycles will bring an even input to a lower output, but that output may be odd, in which case the next 3 cycles will not necessarily produce a lower output." Your observation about long "worst-case" strings of "odd even odd even, ..." which grow the input arbitrarily doesn't change the property of evens as I have described to be decreasing. I'm not negating what you said, I follow your reasoning, but it's not clear to me how/if you are negating my claim for evens (and it's just a claim). I said: f(f(f(n:even):odd):even)=(3(n/2)+1)/2=(3/4)n+1/2 is less than the initial (n:even) for n>4 (actually 2 is sufficient) This would still occur in your strings. The fact that you can come up with strings that abitrarily begin with (or contain within them) these "worst case" alternations does not necessarily mean that it can cycle from it: Let's change one of the cases in my original comment (diff-style): < f(f(f(n:even):even):odd)=3((n/2)/2)+1=(3/4)n+1 < is less than the initial (n:even) for n>4 --- > f(f(f(f(n:even):even):odd):even)=(3((n/2)/2)+1)/2=((3/4)n+1)/2=(3/8)n+1/2 > is less than the initial (n:even) for n>4/5... so every valid input You cannot have two odds in a row so that's the only thing that CAN happen to that case, and it is now clearly anchored on an even, requiring that even to still be decreasing with respect to the initial even (now no more than 5 numbers prior) in every case. We can walk down these decreasing even steps until we are back in known territory (n<=8). Of course, I'm happy to hear counter arguments./thoughts.
- waterhouse 14y ago> "it's not clear to me how/if you are negating my claim for evens (and it's just a claim)." I assumed, from context and stuff, that you had thought you had a proof of the Collatz conjecture, or at least a claim that seemed to prove it, or at least a claim that might be tweaked and extended and refined a little to produce a proof. I aimed to show that all claims like yours were unsuitable for a proof of the Collatz conjecture, because either they could not be iterated or they could not show a decrease for all inputs. If all you are saying is "If n is 4 mod 8, then four successive applications of f will produce (3/8)n + 1/2; this is an isolated mathematical fact interesting by itself", and don't believe it's a proof of the Collatz conjecture, then I have no complaint. I've even written a few functions that will tell you what happens to n after k steps, given that n is x mod 2^m. Here is some output for anyone who is interested: http://pastebin.com/MjzahMFV http://pastebin.com/MjzahMFV > "The fact that you can come up with strings that abitrarily begin with (or contain within them) these "worst case" alternations does not necessarily mean that it can cycle from it:" Of course not. If I could produce a cycle that involved n getting bigger, then I would have disproved the Collatz conjecture. I wasn't attempting to do that, merely disproving a class of attempted proofs.