Re: Collatz Problem: An idea for its solution.

A. Boom wrote:
> A. Boom wrote:
> > Hi,
> >
> > I read about the Collatz Problem and then wrote some programs to
study
> > the patterns. Please let me know if the following is sound idea for

> > solving the problem.
> >
> > Although I do not have a solution, I would like to know if the idea
I
> > have is sound. It is a simple idea, really.
> >
> > The idea is that the Collatz Problem can be viewed as a person
either
> > stepping toward or away from a point we label 1.
> >
> > 1) If the current value, P, is an even number then the person walks

> > toward the point and the distance from the person and the point
decreases.
> >
> > 2) If the current value, P, is an odd number then the person will
walk
> > away from the point and the distance from the person and the point
> > increases.
> >
> > The difficult part is 2, but I have an idea of how to deal with it.
> >
> > When P is odd, the next P, P1, will equal 3*P + 1. Thus the
increase in
> > distance, D, is equal to (3*P + 1) - P = 2*P + 1. It is also seen
that
> > P1 will be an even number, hence the next time will involve
division by
> > 2 which is thought of as stepping toward the point 1.
> >
> > If it can be shown that AFTER the distance was increased, at the
odd
> > step, the subsequent decreases in distance is greater, then the
sequence
> > of P's will have been shown to ultimately decrease. It would then
need
> > to also show that the end point is 1. And since a decrease in
distance
> > is always a division by 2, and the numbers are always positive
integers,
> > the last P will be equal 1.
> >
> > The above is the general idea. A more concise way of the idea is
that it
> > need only be shown that when P is odd, the next P, P1, will have
more
> > factors of 2 than the increase in distance, 2P + 1 has. Thus the
next
> > odd number encountered will be less than any previous odd number
> > encountered in the sequence. The sequence will thus have been shown
to
> > ultimately decrease.
> >
> > Again, this is only an idea that I had. One has to risk failure to
learn
> > new things.
> >
> > Thanks, Adam.
>
> Forgive me. An odd number encountered will not necessarily be less
than
> all previous odd numbers in the sequence.

And it won't be if the binary representation of the number has 2 or
more contiguous least significant 1s. When a block of LS 1s is
encountered, the process alternates between [3n+1] and [n/2] consuming
1 bit per pair of operations until the block is consumed. Meanwhile,
propagating carry bits overflow the MS bit at an average rate of
1.585 bits per pair of operations resulting in a net gain of 0.585 bits
for every bit consumed at the LS end.

Thus, if n = 2**1000 - 1, the sequence will diverge (every odd number
larger than the previous) for exactly 1000 [3n+1][n/2] steps at
which point the original 1000 bits are gone and replaced by a 1585-bit
number created by the propagating carry bits. As large as a 1000-bit
number is, a 1585-bit number is a LOT larger, so much larger that you
cannot comprehend how much.

Of course, any finite number can only have a finite number of
contiguous LS 1s, so the divergence must be finite. But who's to say
that somewhere on it's fall from 1585 bits to 1 bit we don't encounter
another Mersenne number in the sequence? And could the Mersenne
numbers occur frequently enough to allow a net divergence forever?

You can rule out a pair of even bit Mersenne numbers from being in the
same sequence (or an even bit one following an odd bit one) since all
even bit Mersenne numbers are congruent to 0 (mod 3) and a Collatz
sequence can have at most 1 odd number congruent to 0 (mod 3).

> I'll work on this though. :)

Here's something else to consider:

does the above work if the sequence is a loop?

For example, in the 3n+1271069 system, if you start at 97, after
315529 iterations you find yourself back at 97. So although your
heuristic argument is true, it doesn't guarantee that you will
reach your termination point (which in this case would be 1271069).

>
> Adam.

.

Relevant Pages

  • Re: Collatz Problem: An idea for its solution.
    ... > I read about the Collatz Problem and then wrote some programs to study ... > toward the point and the distance from the person and the point decreases. ... > 2) If the current value, P, is an odd number then the person will walk ... > of P's will have been shown to ultimately decrease. ...
    (sci.math)
  • Collatz Problem: An idea for its solution.
    ... The idea is that the Collatz Problem can be viewed as a person either stepping toward or away from a point we label 1. ... If the current value, P, is an odd number then the person will walk away from the point and the distance from the person and the point increases. ... If it can be shown that AFTER the distance was increased, at the odd step, the subsequent decreases in distance is greater, then the sequence of P's will have been shown to ultimately decrease. ...
    (sci.math)
  • Re: Collatz Problem: An idea for its solution.
    ... The idea is that the Collatz Problem can be viewed as a person either stepping toward or away from a point we label 1. ... If the current value, P, is an odd number then the person will walk away from the point and the distance from the person and the point increases. ... If it can be shown that AFTER the distance was increased, at the odd step, the subsequent decreases in distance is greater, then the sequence of P's will have been shown to ultimately decrease. ...
    (sci.math)
  • Re: The Collatz-Highway
    ... Given only this sequence --- ... giving the next odd number. ... When I say applicable sequences I mean ... where all entries N2transform to 5 by one step. ...
    (sci.math)
  • Re: Collatz Question
    ... How to Construct a Counterexample to the Collatz ... In the negative domain, the conjecture is false for all C ... Does the Collatz sequence obey the laws of nature? ... But that doesn't mean there are actually more even than odd ...
    (sci.math)
Quantcast