Lab 3: while revisited

Comp 150, Dordal, Feb 10, 2006

Start with a positive integer, N = N0. Define the following sequence:
    Nk+1 = 3*Nk+1 if Nk is odd
    Nk+1 = Nk/2 if Nk is even

As an example, suppose we start with N=7. The sequence then is
    7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
It took 16 steps to reach 1.

Many mathematicians have looked at this sequence, and this sequence as a result has been associated with all these names: Collatz, Kakutani, Thwaites, Hasse, Ulam. Because the numbers tend to move up and down for a while before reaching 1, just as hailstones move up and down in a cumulonimbus cloud before reaching the ground, this has also been called the "hailstone" sequence.

The basic conjecture (still unproven) is that, no matter what N you start with, you always eventually end up at 1. The time it takes to get there, however, varies widely.

Step 1: how long

Write a function collatz in python that, given a number N, returns the number of steps it takes for the Collatz sequence to reach 1. For example, collatz(7) should return 16, as in the example above.

You will need a while loop. Note that, unlike the loop last week, we do not know in advance how long the loop will go.

The body of your function will contain the following central if..else. Note that we test if n is even by dividing by 2 and looking at the remainder; a % b, read "a mod b", means to divide a by b and give the remainder. 

        if n % 2 == 0:             # if n is even
            n = n/2
        else:
            n = 3*n+1

Verify your work with the following values: collatz(7)=16, collatz(9)=19, collatz(25)=23, collatz(27)=111.

Step 2: maxing out

Find the N≤1000 that gives the longest sequence, that is, for which collatz(N) has the maximum value.

This could take some work. However, python has a function map to the rescue. map(f, lis) takes a function f and applies it to every element of the list, returning the list of results. For example, if you define sqr(x) = x2, then map(sqr, [1,2,3,4,5]) returns [1,4,9,16,25]. And map(collatz, range(1,10)) returns the list of collatz(n) for 1≤n≤9. Furthermore, given any list L, max(L) is the largest number in the list: max([2,7, 5, 11, 3]) = 11. Putting this together, it's easy to get the largest value of collatz(N) for N≤1000.

You still need to find out which N gives that largest value. One way is to find the position in the list CL = map(collatz, range(1,1001)) where that value occurs. One way to do get this, if M = max(CL), is with CL.index(M). Be sure to note, though, that CL[0] represents N=1, CL[1] represents N=2, etc. Another thing you can do is 

	for i in range(0,1000):         # why 0 and not 1?
	    if CL[i]==M: print i        # one-line form of if
This has the advantage of printing all i, and you can change it to print i+1 instead. For N=100 and N=1000 there's only one i at which the max occurs; try N=60 or N=300 or N=700 if you want to see the max occuring more than once.

Reloading

I think I've got it right now. Initially:
    from lab3 import *
Then, to reload:
    reload(lab3)
    from lab3 import *