Re: Proof... ( After careful thought )

mensanator_at_aol.compost
Date: 02/09/05 

Date: 9 Feb 2005 14:04:48 -0800

jim caprioli wrote:
> Thx
> > The point I was trying to make is that the logic system does not
fail.
> > The
> > argument that shows one process must terminate simply does not
apply to
> > the
> > other process. Do you see why?
>
> Yes, and no. :-(
>
> Looking at this
>
> Let n be a positive integer > 2.
> Repeat until n is 1.
> if n is odd then multiply n by 3 and add 1 to n
> if n is even then divide n by 2
> Algorithm stops for every n.
>
> from various angles I would say this can be proved. I would say that
all
> numbers define a Graph over N. f -> (2k, 2k/2),(2k+1, 3(2k+1)+1)) for
all
> k. Using contradiction I would prove this is in fact a tree. I have
also
> proved an infinite product to be 1.
>
> But... I am not a mathematician, let alone one with authority. ;-)
>
> Why is this an unproved conjecture? That is what I do not understand.
It
> makes math very hard to understand for me.

It might be insightful to generalize to 3n+C instead of
focusing on 3n+1 (where C is any odd positive integer).
>>From that generalization, you will find many cases where the
conjecture appears to be true (any where C is a power of 3,
such as 3n+1, 3n+3, 3n+9, 3n+27, etc.)

There where also be many cases where the conjecture is false,
such as 3n+5 and 3n+7. These fail by producing sequences that
end in a non-trivial loop. If instead of stopping on 1 you
let the 3n+1 sequence continue, it enters a loop consisting
of 4, 2, 1:

10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 ...

All 3n+C sytems contain the trivial loop 4C, 2C, C. When C is
a power of 3, this is the _only_ positive loop (unproved).
The C that fail have more than one positive loop:

3n+5
5 -> 20 -> 10 -> 5 the trivial loop
1 -> 8 -> 4 -> 2 -> 1 a non-trivial loop

3n+7
7 -> 28 -> 14 -> 7 the trivial loop
5 -> 22 -> 11 -> 40 -> 20 -> 10 -> 5 a non-trivial loop

It is easy to see why the failure occurs when C is not a power
of 3 and it is easy to see why all powers of 3 have exactly
the same loops. What's difficult to prove is that there can
only be _one_ positive loop. And it's important to stress
_positive_ loop because every 3n+C system (including 3n+1)
also contains three loops in the negative integers: -C, -5C
and -17C.

Note that the heuristical arguments that are sometimes mentioned
are equally applicable to the systems that fail. That's why
they're not proofs. It's not enough to show that 3n+1 never
enters a non-trivial loop, you must show that it _cannot_
enter such a loop.

Relevant Pages

  • Re: File Closing Problem in 2.3 and 2.4, Not in 2.5
    ... It is very unlikely that there is a bug in Python where it would fail to ... you can use Sysinternal's process explorer. ... Put a print statement in the block that is supposed to close ... they may be out of "the loop" you thought that they were in. ...
    (comp.lang.python)
  • Re: Random numer generation without repetition
    ... if I'd use randperm it'll blow my memory ... redo the few that fail. ... loop will essentially never terminate. ...
    (comp.soft-sys.matlab)
  • Re: copy error
    ... each time through loop ... You are inspecting $! ... along the line, something that "copy" does is failing with that message, ... but the "copy" itself does not fail, ...
    (comp.lang.perl.misc)
  • [PATCH] ISDN: unsafe interaction between isdn_write and isdn_writebuf_stub
    ... I was originally just looking to fix this warning: ... While reading the code I also noticed that the while loop in isdn_write ... the function once more and again fail to alloc an skb, ... To fix these things I first made isdn_writebuf_stubreturn -ENOMEM if it ...
    (Linux-Kernel)
  • Re: Idle Curiosity -- 4-20mA Signalling
    ... 4-20mA signaling loop? ... I'm curious as to how much freedom one has to power ones device when one ... designs some gizmo that flaps in the breeze on the end of a current loop. ... maximum supply voltage and calculate the maximum load resistance. ...
    (sci.electronics.design)