News for hackers. Stuff that matters.
Re:The 3n+1 problem by vy8vWJlco on Thursday October 25, 2012 @09:04PM (#4700372)
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.

Re:The 3n+1 problem by waterhouse on Friday October 26, 2012 @12:10AM (#4700843)
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.
Re:The 3n+1 problem by vy8vWJlco on Friday October 26, 2012 @01:01PM (#4703101)
"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.

Re:The 3n+1 problem by waterhouse on Friday October 26, 2012 @03:58PM (#4703973)
> "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

> "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.

Re:The 3n+1 problem by vy8vWJlco on Sunday October 28, 2012 @06:26AM (#4708610)
"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."

I'm not sure I addressed your criticism fully. Earlier you noted:

"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."

That is precisely the case I am describing. I begin with a universal property of any sequence, then proceed to show that all sequences beginning with an even terminate. I then note that the earlier property requires that all sequences beginning with odd numbers immediately follow this pattern after at most one iteration. A sequence that terminates after a finite number of steps + 1 still terminates after a finite number of steps. I have summarized this in a post above.

The abmiguity you describe in the set of proofs you are disqualifying is not present in my arguement. I begin at the first value for all sequences (evens, and then odds, which is exhaustive of inputs, and outputs, as you note is necessary) and that is exhaustive of sequences.

Is it a variation on the most naive approach that pretty much everyone would start with? Sure, and that's reason enough to be skeptical. But, does it work? It seems to...

Re:The 3n+1 problem by vy8vWJlco on Friday October 26, 2012 @07:20PM (#4704702)
I'm still thinking about your modular perspective. I believe that is an accurate restatement of one of my cases, but it is not all of them and would not be sufficient alone. Whereas all the cases together, however, are exhaustive. To summarize, my above comments/claims boil down to:

1) any even number input taken will produce a sub-sequence ending in an even output, by exhaustion (see above), that is guaranteed to be smaller after a maximum number of steps

2) this new even can be taken again, as often as necessary, to reach the smallest integer in that sequence greater than 8

3) the next even number (at most 1 odd away) is by definition below 8 and, while it may not have a next even by my arguement of necessity, it will still be below 8, and all inputs below 8 terminate

4) there is nothing about this reasoning that limits it to a particular sequence/input (all initially-odd inputs adhere after 1 iteration), so it is true of every sequence

Am I saying anything untrue or ambiguous?

Thanks for taking the time!

Re:The 3n+1 problem by vy8vWJlco on Friday October 26, 2012 @10:31PM (#4705127)
2 slight corrections, for clarity:

...

2) ... smallest even integer in that sequence greater than 8 ...

3) ... by definition less than or equal to 8 ... will still be less than or equal to 8, and all inputs less than or equal to 8 terminate

...

Everything hinges on odds being as or less likely than evens which I believe I show initially "for 2n-1 (clearly odd), f(2n-1) = 3(2n-1)+1 = 2(3n-1), which is clearly even"; at least one even must follow every odd and, additionally, since there are only evens and odds, every odd must have been immediately preceded by an even. It's definitely an innocuous observation, but it justifies a walk all the way down to 8 by exhausting the (3) possible routes through the evens.

Re:The 3n+1 problem by vy8vWJlco on Saturday October 27, 2012 @02:03PM (#4706754)
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.)

Re:The 3n+1 problem by vy8vWJlco on Tuesday October 30, 2012 @10:31AM (#4717462)
Redacted. My permutations do not necessarily terminate on evens, which would have been necessary to draw the conclusions that followed. Ah, Collatz, you've won this round...