4 ms·

I immediately regretted myself and backed out my comment -- but just to address your note about even:odd:even:odd, since you have a point: you are considering a

I immediately regretted myself and backed out my comment -- but just to address your note about even:odd:even:odd, since you have a point: you are considering a 5 number string (starting with an even) when the skipping-monotonicity property I was toying with only applied to strings 4 long (again, beginning with an even number). It might look like a spike, but it's not a valid application. I'm not asserting it's strictly monotonic, of course -- as your other note implied -- but rather that every 4th (starting on an even, for n>=8) is less than n. But, IANAM. I don't even claim it's right ATM -- I redacted it to chew on more -- but for the sake of conversation, I'll reproduce it, and people can debug or ignore. Original comment: ---- Ok... ok ok ok. ok. Assume: n>1. I claim: an odd output can only occur after an even input. 'Cause: for 2n-1 (clearly odd), f(2n-1) = 3(2n-1)+1 = 2(3n-1), which is clearly even. [This made me redact my thoughts initially -- and they're just that -- thoughts. I thought I'd try to come at this property from a different angle...] Implying: an odd input can only come initially or immediately after a prior even event... There can't be two sequential odd results during normal (non-initial) iterations. For that matter, if the initial input is odd, the output will be even after at most two iterations (3(3n+1)+1=6n+4=2(3n+2), which is even), after which it's business as usual. So, we only really have to consider sequences beginning from an even n to see what's really going on. f(n:even) can yield an odd or an even value. Permuted: f(f(f(n:even):odd):odd) is impossible (see above). f(f(f(n:even):even):even)=((n/2)/2)/2=n/8 is less than the initial (n:even) for n>8 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(n:even):odd):even)=(3(n/2)+1)/2=(3/4)n+1/2 is less than the initial (n:even) for n>4 I conclude: no cycles while n>8 and no infinite divergent trajectories while n>8. You can't have cycles OR divergent infinite trajectories while n>8 since no output, after 3 iterations, may exceed the initial (even) input. In other words, pick any 4 sequential numbers BEGINNING with an EVEN number (the initial even input and the results of 3 consecutive iterations) and the 4th number will always be smaller than the 1st number - whether the final number is even OR odd, or there were some biggies in the middle of the list. It's like... monotonic.

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.
vy8vWJlco 14y ago
Some of my initial constraints were looser than necessary (though still true), so I have tightened them up below and can get all the way to 2 now. Here's my proof of the Collatz conjecture. I hope someone will call me on it if there's any problem. Given the function: f(n)={n/2 if n=0 mod 2, 3n+1 if n=1 mod 2}, for integers n >= 1 And the set of sequences: a_i={n if i=0, f(a_[i-1]) if i>0}, for integers i >= 0 and integers n >= 1 Lemma: In any given sequence, any given odd must be followed by an even. Proof: a_[k-1]=2n-1 (clearly odd), for k >= 1 a_[k]=f(2n-1)=3(2n-1)+1=2(3n-1) (clearly even) Corrollary: The elements of both the domain and range of f (namely, the elements of the positive integers) are trivially either even or odd, so every non-initial odd in a sequence must also have been immediately preceded by at least one even. We can now exhaustively describe all the shortest sub-sequences that start and end on evens. These can be found simply by assuming an even start and fully permuting the the next two iterations of f to find the next two numbers in a sequence. Specifically, there are 4 cases: 1) f(f(f(n:even):even):even), which contains a repeated sub-sequence: f(f(n:even):even)=(n/2)/2=n/4 Which is less than the first (n:even) for n>0. 2) f(f(f(n:even):even):odd), which ends with an odd and can only be followed by an even (Lemma), and so describes the same sub-sequence as: 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 Which is less than the first (n:even) for n>4/5. 3) f(f(f(n:even):odd):even)=(3(n/2)+1)/2=(3/4)n+1/2 Which is less than the first (n:even) for n>2. 4) f(f(f(n:even):odd):odd) Which is impossible (Lemma) as it contains 2 consecutive odds. I have included this case merely to illustrate the completeness of the permutations. The 3 valid cases above (cases 1 through 3) show that for any initial even greater than 2 there exists an even that is both strictly lower than the original even and is within 4 iterations of f (within a sub-sequence of 5 numbers, beginning with the first even) beyond the first even. Now consider any full sequence beginning with an even. By the above exhaustion, all such full-length sequences begin with one of the above sub-sequences. The end of that sub-sequence is even and, when taken again as the first even in one of the above sub-sequences, as many times as necessary, shows that the evens, with certainty, reach some smallest even integer greater than 2, after only a finite number of steps. This smallest even integer greater 2 is followed by exactly 1 odd (Lemma and Corrollary) and is, by definition, less than or equal to 2. All inputs less than or equal to 2 terminate trivially in the well-known 1-cycle (2, 1, 4, 2, 1, ...), therefore all sequences beginning with an even number end in this 1-cycle. Furthermore, all odd inputs are followed by an even after at most 1 iteration (Lemma), so sequences beginning with odd numbers also terminate in this 1-cycle. Q.E.D(ammit). This argument is not qualitatively different from the one in my original comment. I have only attempted to connect the intermediary steps more clearly, in addition to tightening up the constraints to lower the original boundary condition. I'm not sure if anybody's still reading this, but I would welcome any further analysis. (For example, I'm sure it could be written more professionally, and with less English.)

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.

vy8vWJlco 14y ago

Some of my initial constraints were looser than necessary (though still true), so I have tightened them up below and can get all the way to 2 now. Here's my proof of the Collatz conjecture. I hope someone will call me on it if there's any problem. Given the function: f(n)={n/2 if n=0 mod 2, 3n+1 if n=1 mod 2}, for integers n >= 1 And the set of sequences: a_i={n if i=0, f(a_[i-1]) if i>0}, for integers i >= 0 and integers n >= 1 Lemma: In any given sequence, any given odd must be followed by an even. Proof: a_[k-1]=2n-1 (clearly odd), for k >= 1 a_[k]=f(2n-1)=3(2n-1)+1=2(3n-1) (clearly even) Corrollary: The elements of both the domain and range of f (namely, the elements of the positive integers) are trivially either even or odd, so every non-initial odd in a sequence must also have been immediately preceded by at least one even. We can now exhaustively describe all the shortest sub-sequences that start and end on evens. These can be found simply by assuming an even start and fully permuting the the next two iterations of f to find the next two numbers in a sequence. Specifically, there are 4 cases: 1) f(f(f(n:even):even):even), which contains a repeated sub-sequence: f(f(n:even):even)=(n/2)/2=n/4 Which is less than the first (n:even) for n>0. 2) f(f(f(n:even):even):odd), which ends with an odd and can only be followed by an even (Lemma), and so describes the same sub-sequence as: 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 Which is less than the first (n:even) for n>4/5. 3) f(f(f(n:even):odd):even)=(3(n/2)+1)/2=(3/4)n+1/2 Which is less than the first (n:even) for n>2. 4) f(f(f(n:even):odd):odd) Which is impossible (Lemma) as it contains 2 consecutive odds. I have included this case merely to illustrate the completeness of the permutations. The 3 valid cases above (cases 1 through 3) show that for any initial even greater than 2 there exists an even that is both strictly lower than the original even and is within 4 iterations of f (within a sub-sequence of 5 numbers, beginning with the first even) beyond the first even. Now consider any full sequence beginning with an even. By the above exhaustion, all such full-length sequences begin with one of the above sub-sequences. The end of that sub-sequence is even and, when taken again as the first even in one of the above sub-sequences, as many times as necessary, shows that the evens, with certainty, reach some smallest even integer greater than 2, after only a finite number of steps. This smallest even integer greater 2 is followed by exactly 1 odd (Lemma and Corrollary) and is, by definition, less than or equal to 2. All inputs less than or equal to 2 terminate trivially in the well-known 1-cycle (2, 1, 4, 2, 1, ...), therefore all sequences beginning with an even number end in this 1-cycle. Furthermore, all odd inputs are followed by an even after at most 1 iteration (Lemma), so sequences beginning with odd numbers also terminate in this 1-cycle. Q.E.D(ammit). This argument is not qualitatively different from the one in my original comment. I have only attempted to connect the intermediary steps more clearly, in addition to tightening up the constraints to lower the original boundary condition. I'm not sure if anybody's still reading this, but I would welcome any further analysis. (For example, I'm sure it could be written more professionally, and with less English.)