Mystery Guest from Number Theory
Jim Dennis
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.
Denys Duchier
it as Collatz's problem, Hasse's algorithm, Kakutani's problem,
Syracuse algorithm, Syracuse problem, Thwaites conjecture, and Ulam's
problem. The element of the resulting sequence are called Hailstone
numbers.
Cheers,
--
Dr. Denys Duchier Denys....@ps.uni-sb.de
Forschungsbereich Programmiersysteme (Programming Systems Lab)
Universitaet des Saarlandes, Geb. 45 http://www.ps.uni-sb.de/~duchier
Postfach 15 11 50 Phone: +49 681 302 5618
66041 Saarbruecken, Germany Fax: +49 681 302 5615
Gareth Rees
> this here and see if anyone can name our mystery guest:
>
> cut it in half, otherwise multiply by three and add one. Iterate until
> you get to one.
as the "3x+1" problem. The Collatz Problem is to prove that every positive
integer eventually leads to 1 under the iteration of the function
x -> 3x+1 (x odd)
x -> x/2 (x even).
The problem is unsolved.
See <http://mathworld.wolfram.com/CollatzProblem.html>.