Conference rusure::math

1155.0. "will it ever terminate ?" by RIPPLE::ABBASI_NA () Wed Nov 29 1989 20:21

given a integer n>1 , if n is odd then let n= 3n+1, else let n= n/2
keep repeating this process untill you end with n equall 1.
According to a book I read (1984) edition, there is no algorithm at the time
to determine, given n , if it will eventually terminates in 1 or not,
if you try it out, you dont know how long it will take (if it will) reach
1.


example n=15

 n= 3*15+1 = 46
 n= 46/2   = 23
 n= 23*3+1 = 70
 n= 70/2   = 35
 n= 3*35+1 = 106
 n= 106/2  = 53
 n= 3*53+1 = 160
 n= 160/2  = 80
 n= 80/2   = 40
 n= 40/2   = 20
 n= 20/2   = 10
 n= 10/2   = 5
 n= 3*5+1  = 16
 n= 16/2   = 8
 n= 8/2    = 4
 n= 4/2    = 2
 n= 2/2    = 1    Done !


 so given a number say 237  how do you if this terminates to 1 or not ?
 is there non np-complete algorithm to determin this ?

 

/naser

        This subject has been covered in at least one previous
        topic, for example topic 249.
        
        Dan