The 3n + 1 Sequence¶

As another example of indefinite iteration, let’s look at a sequence that has fascinated mathematicians for many years. The rule for creating the sequence is:

to start from some given number, call it n, and
to generate the next term of the sequence from n, either by:
- halving n, whenever n is even,
- or else by multiplying it by three and adding 1 when it is odd.
The sequence terminates when n reaches 1.

This Python function captures that algorithm. Try running this program several times supplying different values for n.

def seq3np1(n):
    """ Print the 3n+1 sequence from n, terminating when it reaches 1."""
    while n != 1:
        print(n)
        if n % 2 == 0:        # n is even
            n = n // 2
        else:                 # n is odd
            n = n * 3 + 1
    print(n)                  # the last print is 1

seq3np1(3)

(ch07_indef1)

Since n sometimes increases and sometimes decreases, there is no obvious proof that n will ever reach 1, or that the program terminates.
For some particular values of n, we can prove termination.
For example, if the starting value is a power of two, then the value of n will be even each time through the loop until it reaches 1.

Particular values aside, the interesting question is whether we can prove that this sequence terminates for all values of n. So far, no one has been able to prove it or disprove it!

Think carefully about what would be needed for a proof or disproof of the hypothesis “All positive integers will eventually converge to 1”. With fast computers we have been able to test every integer up to very large values, and so far, they all eventually end up at 1. But this doesn’t mean that there might not be some as-yet untested number which does not reduce to 1.

You’ll notice that if you don’t stop when you reach one, the sequence gets into its own loop: 1, 4, 2, 1, 4, 2, 1, 4, and so on. One possibility is that there might be other cycles that we just haven’t found.

Choosing between for and while

Use a for loop if you know the maximum number of times that you’ll need to execute the body. For example, if you’re traversing a list of elements, or can formulate a suitable call to range, then choose the for loop.

So any problem like “iterate this weather model run for 1000 cycles”, or “search this list of words”, “check all integers up to 10000 to see which are prime” suggest that a for loop is best.

By contrast, if you are required to repeat some computation until some condition is met, as we did in this 3n + 1 problem, you’ll need a while loop.

Next Section - Newton’s Method