5 ms·

Whether or not this converges for all inputs is a famous unproved math problem, so it is somewhat humorous that you think you have a proof of convergence. Take

• vy8vWJlco 14y ago
  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.