Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83 based; site houxm.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxl!houxm!dis2
From: dis2@houxm.UUCP (A.NESTOR)
Newsgroups: net.math
Subject: Re:Yet another puzzle
Message-ID: <882@houxm.UUCP>
Date: Tue, 4-Sep-84 14:37:38 EDT
Article-I.D.: houxm.882
Posted: Tue Sep  4 14:37:38 1984
Date-Received: Thu, 6-Sep-84 03:22:33 EDT
Organization: AT&T Bell Labs, Holmdel NJ
Lines: 95


     
Will the following ALWAYS STOP?:
   step1:  if(i=1) then STOP:
   step2 :  if ( i is even) i=i/2 else i=3i*i1+1;
   step3:   go to step1;
____________________________________________________________
State the problem as:
    Define f :
		f(n)=n/2 for n even
		f(n)=3n+1 for n odd
          where n is a postive integer (i.e. Z+)
   
    Define fM(n) as the Mth composition of f(n)  
       i.e. fM=f o f o f o .......f(n) 
                                   Mth composition
  
    Define sM(n) as the sequence:
		f(n),f o f(n), f o f o f(n),.,.,fM
  
    Defintion:
	sM(j)(n) for j<=n is the jth member of sM(n)
  
    Definition:
        sM(n) "terminates" iff sM(n)=1.
   
    PROVE: For all n, there exists M such that fM(n)=1.
		i.e. sM(n) "terminates".
  
    Consider the Quotient Set Z+/3:
	It partitions Z+ into three subsets:
               {0} n mod[3]=0 i.e. n=3k 
               {1} n mod[3]=1 i.e. n=3k+1
               {2} n mod[3]=2 i.e. n=3k+2
   
Example:
   n=6
   S9(n)=6,3,10,5,16,8,4,2,1
   f1(n)=6      s9(1)(n) a member of {0}
   f2(n)=3      s9(2)(n) a member of {0}
   f3(n)=10     s9(3)(n) a member of {1}
   f4(n)=5      s9(4)(n) a member of {2} also f4(n)=(2**4 -1)/3
   f5(n)=16     s9(5)(n) a member of {1}
   f6(n)=8      s9(6)(n) a member of {2}
   f7(n)=4      s9(7)(n) a member of {1}
   f8(n)=2      s9(8)(n) a member of {2}
   f9(n)=1      s9(9)(n)=1    
   
 
   Outline of Proof:
   Prove Lemma I:
          If
              1. i is a member of sM(k) for some k
                 ( sM(j)(k) for some j and k)
              2. sM(k) terminates
              3. i is a member of sM(m) for some m
		 ( sM(j)(m) for some j and m)
          then
                there exists MM such that sMM(m) terminates.
      This lemma clumsily says that if k is a member of a terminating
      sequence, then any sequence of which k is a member can be made  
      to terminate. Indeed all sequences terminate after they have
      a member of the form (2**m - 1)/3.
  
   Prove Lemma II:
         If there exists j such that sM(j)(n) is a member of  {0}
         then there exits k such that k>=j and sM(k)(n) is a member of {1}.
  
     This lemma says that if n=3k is in the sequence, then there
     is a later member n=3k+1.
   
   Prove Lemma  III:
         If there exists j such that sM(j)(n) is a member of  {1}
         then there exits k such that k>=j and sM(k)(n) is a member of {2}.
  
     This lemma says that is n=3k+1 is in the sequence, then there
     is a later member n=3k+2.
   
   Prove Theorem 1:
      For all n, members of {2}; there exists M such that fM(n)=1.
      The proof is by Weak Induction:
      For k=1, n=3k+2=5
	s6(5)=5,16,8,2,4,1
        f6(5)=1
   
     Assume:
        n=3k+2 imples there exists M such that fM(n)=1
     Prove:
        n=3(k+1)+2 implies there exists M such that fM(n)=1
   
    Lemma I and Lemmas II and III with j=1 and Theorem 1, provide the desired 
    result.
                                        Creighton Clarke
			sdcsvax!decvax!harpo!eagle!mhuxl!houxm!dis2
                                           201-949-1538