Mystery Guest from Number Theory

Jim Dennis jimd at vega.starshine.org
Wed Feb 20 12:37:49 CET 2002


 Years ago I know I read about a function which exhibits 
 very simple chaotic behavior.  I don't remember where I read
 about it (my first guess was Gleick's Chaos, Penguin Books, 1987,
 but I couldn't find it there).  So it was probably in some other
 tome on Number Theory.

 So, as odd as it sounds, I'd like to post the code that implements
 this here and see if anyone can name our mystery guest:

def next_it(n): 
        """Core function: what is this called in number theory?"""
        if not n % 2:   n=n/2
        else:           n=n*3+1
        return n

def do_it(n): 
        """How many iterations through next_it() to reach 1?"""
        it=0
        while n > 1: 
                it += 1
                n = next_it(n)
        return it

 This should be pretty readable, for any whole number, if it's even 
 cut it in half, otherwise multiply by three and add one.  Iterate until 
 you get to one.  (So far all whole numbers seem to reach 1, but the 
 number of iterations it takes to so is non-trivial.  I guess no one
 back then knew of a formula that would short-circuit the algorithm.

 Here's one more function to go wit those:

def max_it(l,u=None,f=None):
        """Return tuple of tuples: for each new max return the 
           n that generated it and the number of iterations it took to reach
           1; alternatively call function f for each new max found"""
        if u is None: # only one number given
                u=l # set upper bound
                l=2 # set lower bound
        if l < 2 or u <= l:  # check upper and lower bounds
                raise IndexError
                ## is that really the right exception for this case?
        max=0
        if f is None:   result = []
        else:                   result = None
        for i in xrange(l,u):
                x = do_it(i)
                if x > max: 
                        max=x
                        if f is None:   result.append((i,x))
                        else:           f(i,x)
        return result

 ... this one simply iterates over the mystery guest function 
 for all the numbers up to our argument (or between our ordered
 integer arguments and finds successive  "maximal" values for the 
 "do_it" function. 

 (Ooops, I forgot to check for integer and negative values in these; 
 undefined results for those).  

 Not surprisingly the number of iterations returned by do_it does
 get bigger for larger numbers.  However the iterations grow relatively
 slowly, so we have to work every harder to find a new n which returns
 a new maximal do_it().   So in the range 2:10000 (10e5) the last couple
 of tuples is: (3711, 237) and (6171,261), at n=156,159 do_it() reaches
 one in only 382 steps, and it goes from 410011 (@ 448) to 511935 (@ 469)
 to 626331 (@ 508 interations).  So we're taking 100K strides to find
 a mystery function increase of less than 100 iterations.  There's only
 one more n (837799) less than a million, and it reaches zero in only
 524 iterations.

 Whoever our mystery guest is, he won't ever attain the fame, fortune,
 and perrennial intrigue of prime or even perfect numbers, but I'd 
 still like to know his name.




More information about the Python-list mailing list