See if you can find a small starting number that needs more than a hundred steps before it terminates.

This chapter introduces the Collatz sequence. If you're interested, I recommend reading section 7.5 of it. The basic operation of the Collatz sequence is to take a number and, if it is even, divide it by two. If it is odd, multiply it by three and add one. We can express it as a function like so:

def next_collatz(n):
    if n % 2 == 0:
        return n // 2
    else:
        return 3*n + 1
Copy

Iterating it can yield a "Collatz sequence". So, for example, for the number 3, we get the sequence [3, 10, 5, 16, 8, 4, 2, 1]. When you reach 1, the sequence terminates. The textbook has a perfectly good function that prints out a Collatz sequence for a given number. But I'd like to build a function based on my little next_collatz function that assembles a list, and then print that list. We can do that like so:

def collatz_sequence(n):
    assert type(n) == int
    assert n > 0
    sequence = [n]
    while n != 1:
        n = next_collatz(n)
        sequence.append(n)
    return sequence

for i in range(1, 10):
    print(collatz_sequence(i))
Copy

Those last two lines print

[1]
[2, 1]
[3, 10, 5, 16, 8, 4, 2, 1]
[4, 2, 1]
[5, 16, 8, 4, 2, 1]
[6, 3, 10, 5, 16, 8, 4, 2, 1]
[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
[8, 4, 2, 1]
[9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Copy

But ultimately, we're not interested in printing Collatz sequences. We're interested in measuring the number of steps it takes, given some starting number, to terminate at 1. And we can measure that with this function:

def collatz_steps(n):
    """For an integer, n, returns the number of steps before the 
    Collatz function terminates at 1."""
    steps = 0
    while n != 1:
        n = next_collatz(n)
        steps += 1
    return steps
Copy

We can test this with:

for x in range(1, 10):
    print("{} takes {} steps to resolve.".format(x, collatz_steps(x)))
Copy

And we get

1 takes 0 steps to resolve.
2 takes 1 steps to resolve.  
3 takes 7 steps to resolve.  
4 takes 2 steps to resolve.  
5 takes 5 steps to resolve.  
6 takes 8 steps to resolve.  
7 takes 16 steps to resolve.  
8 takes 3 steps to resolve.  
9 takes 19 steps to resolve.  
Copy

Now that we've got collatz_steps working, we can zero in on the whole purpose of this exercise. Let's find the smallest number that takes over 100 steps to solve.

for x in range(1, 100):
    if collatz_steps(x) > 100:
        print("{} takes {} steps to resolve.".format(x, collatz_steps(x)))
        print(print_collatz(x))
        break
Copy

We get

27 takes 111 steps to resolve.  
[27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
Copy

So collatz_steps(27) is 111. But as we test bigger and bigger numbers, interestingly, the number of Collatz steps doesn't grow every fast. Now, if 27 takes 111 steps to resolve, we can know for certain that this record of 111 steps will be broken. If nothing else, 54 will yield 112 steps, because 54 is one step away from 27. We can say, in general, that if n takes s steps, 2n takes s + 1 steps. So, out of curiosity, let's try a bit of code that can find successive "records" -- numbers that produce a longer Collatz sequence than any lesser number:

high = 0
for x in range(1, 10**6):
    this_result = collatz_steps(x)
    if this_result > high:
        high = this_result
        print(x, "takes", high, "steps.")
Copy

This prints:

2 takes 1 steps.  
3 takes 7 steps.  
6 takes 8 steps.  
7 takes 16 steps.  
9 takes 19 steps.  
18 takes 20 steps.  
25 takes 23 steps.  
27 takes 111 steps.  
54 takes 112 steps.  
73 takes 115 steps.  
97 takes 118 steps.  
129 takes 121 steps.  
171 takes 124 steps.  
231 takes 127 steps.  
313 takes 130 steps.  
327 takes 143 steps.  
649 takes 144 steps.  
703 takes 170 steps.  
871 takes 178 steps.  
1161 takes 181 steps.  
2223 takes 182 steps.  
2463 takes 208 steps.  
2919 takes 216 steps.  
3711 takes 237 steps.  
6171 takes 261 steps.  
10971 takes 267 steps.  
13255 takes 275 steps.  
17647 takes 278 steps.  
23529 takes 281 steps.  
26623 takes 307 steps.  
34239 takes 310 steps.  
35655 takes 323 steps.  
52527 takes 339 steps.  
77031 takes 350 steps.  
106239 takes 353 steps.  
142587 takes 374 steps.  
156159 takes 382 steps.  
216367 takes 385 steps.  
230631 takes 442 steps.  
410011 takes 448 steps.  
511935 takes 469 steps.  
626331 takes 508 steps.  
837799 takes 524 steps.  
Copy

Please ignore the bad grammar in that first line; it's not worth our time right now to avoid it. So the first number to take over 100 steps is 27. We pass 200 steps at 2463, 300 steps at 26,623, and 400 at 230,631. The Wikipedia page on Collatz sequences says this slow growth continues: every number under 100 quadrillion has a sequence length of 2091 steps or less.

Write a function to count how many odd numbers are in a list.

def odd_nums_in_list(xs):
    counter = 0
    for x in xs:
        if x % 2 == 1:
            counter += 1
    return counter

assert odd_nums_in_list([]) == 0
assert odd_nums_in_list([1]) == 1
assert odd_nums_in_list([-1]) == 1
assert odd_nums_in_list([0]) == 0
assert odd_nums_in_list([1, 7, -3]) == 3
assert odd_nums_in_list([1, 2, 3, 4, 5]) == 3
Copy

Sum up all the even numbers in a list.

def sum_even_nums(xs):
    sum = 0
    for x in xs:
        if x % 2 == 0:
            sum += x
    return sum

assert sum_even_nums([]) == 0
assert sum_even_nums([2]) == 2
assert sum_even_nums([9]) == 0
assert sum_even_nums([1, 2, 3, 4]) == 6
assert sum_even_nums([1, 2, 3, 7, -4, 12]) == 10
Copy

Sum up all the negative numbers in a list.

def sum_neg_nums(xs):
    sum = 0
    for x in xs:
        if x < 0:
            sum += x
    return sum

assert sum_neg_nums([]) == 0
assert sum_neg_nums([1]) == 0
assert sum_neg_nums([-1, -2, -3]) == -6
assert sum_neg_nums([1, 7, -6, -14, 12, 87]) ==  -20
Copy

Count how many words in a list have length 5.

def len_5_words(wds):
    counter = 0
    for wd in wds:
        if len(wd) == 5:
            counter += 1
    return counter

assert len_5_words([]) == 0
assert len_5_words(["Jim"]) == 0
assert len_5_words(["Jimmy"]) == 1
assert len_5_words(["The", "quick", "brown", "fox", 
                          "jumped", "over", "the", "lazy", 
                          "dog"]) == 2
Copy

Sum all the elements in a list up to but not including the first even number. (Write your unit tests. What if there is no even number?)

def up_to_even(xs):
    counter = 0
    for x in xs:
        if x % 2 != 0:
            counter += x
        else:
            return counter
    return counter

assert up_to_even([]) == 0
assert up_to_even([2]) == 0
assert up_to_even([7, 3, 4]) == 10
assert up_to_even([6, 5, 5, 5, 5]) == 0
assert up_to_even([-4, 1, 3, 5]) == 0
assert up_to_even([-3, 1, 6]) == -2
assert up_to_even([1.5, 3, 4]) == 4.5
assert up_to_even([1, 3, 5, 7]) == 16
Copy

Count how many words occur in a list up to and including the first occurrence of the word “sam”. (Write your unit tests for this case too. What if “sam” does not occur?)

def words_before_sam(wds):
    counter = 0
    for wd in wds:
        if wd == "sam":
            return counter
        else:
            counter += 1
    return counter

assert words_before_sam([]) == 0
assert words_before_sam(["sam"]) == 0
assert words_before_sam(["i", "am", "sam"]) == 2
assert words_before_sam(["sam", "i", "am"]) == 0
assert words_before_sam(["to", "be", "or", "not", "to", "be"]) == 6
Copy

Add a print function to Newton’s sqrt function that prints out better each time it is calculated. Call your modified function with 25 as an argument and record the results.

def sqrt(n):
    approx = n/2.0     # Start with some or other guess at the answer
    while True:
        better = (approx + n/approx)/2.0
        print(better)
        if abs(approx - better) < 0.001:
            return better
        approx = better

print(sqrt(25.0))
Copy

This yields:

7.25
5.349137931034482
5.011394106532552
5.000012953048684
5.000000000016778
5.000000000016778
Copy

Write a function print_triangular_numbers(n) that prints out the first n triangular numbers. A call to print_triangular_numbers(5) would produce the following output:

1       1  
2       3  
3       6  
4       10  
5       15  
Copy

def print_triangular_numbers(n):
    counter = 0
    for x in range(1, n + 1):
        counter += x
        print(x, "t", counter)
Copy

Write a function, is_prime, which takes a single integer argument and returns True when the argument is a prime number and False otherwise. Add tests for cases like this:

test(is_prime(11))
test(not is_prime(35))
test(is_prime(19911121))
Copy

The last case could represent your birth date. Were you born on a prime day? In a class of 100 students, how many do you think would have prime birth dates?

Here's a function that checks for primeness:

from math import sqrt

def is_prime(x):
    """Takes a positive integer and tells if it's prime."""
    if x == 1:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    for i in range(3, int(sqrt(x) + 1), 2):
        if x % i == 0:
            return False
    
    return True
Copy

We can also answer the question about the 100 students, which I've done here.

Revisit the drunk pirate problem from the exercises in chapter 3. This time, the drunk pirate makes a turn, and then takes some steps forward, and repeats this. Our social science student now records pairs of data: the angle of each turn, and the number of steps taken after the turn. Her experimental data is [(160, 20), (-43, 10), (270, 8), (-43, 12)]. Use a turtle to draw the path taken by our drunk friend.

As the textbook suggests, we can basically rework some code from exercise 3.8.7 to do this. (For my solutions to chapter 3 exercises, see here.)

# Make a simulated pirate and a place for him to stumble around.
import turtle
wn = turtle.Screen()
pirate = turtle.Turtle()

# The raw data about how he stumbled.
turns_and_steps = [(160, 20), (-43, 10), (270, 8), (-43, 12)]

# Simulate the actual stumbling around.
for x in turns_and_steps:
    # The pirate turns.
    pirate.left(x[0])
    # He walks a number of steps forward. We'll move him forward
    # ten 'turtle units' per step, so that the image produced
    # is conveniently sized.
    pirate.forward(10*x[1])

# Keep the screen open till the user closes it.
wn.mainloop()
Copy

The pirate's path looks like this:

Many interesting shapes can be drawn by the turtle by giving a list of pairs like we did above, where the first item of the pair is the angle to turn, and the second item is the distance to move forward. Set up a list of pairs so that the turtle draws a house with a cross through the centre, as show here. This should be done without going over any of the lines / edges more than once, and without lifting your pen.

The comment about "Many interesting shapes" suggests we'll want to set up our code so that we can easily run it with different sets of steps and turns. We can do so as follows:

import turtle

def travel(ttl, turns_and_steps):
    """Takes a turtle ttl and a specially formatted list of turns_and_steps,
    and causes the turtle to trace out lines determined by the turns
    and steps."""
    for x in turns_and_steps:
        ttl.left(x[0])
        ttl.forward(x[1])

wn = turtle.Screen()
tess = turtle.Turtle()

s = 100                     # sets scale of the drawing we'll make
turns_and_steps = [(180, s), 
                   (-135, s*2**0.5,),
                   (135, s),
                   (135, s*2**0.5),
                   (135, s),
                   (45, s*.5**0.5),
                   (90, s*.5**0.5),
                   (45, s)]
travel(tess, turns_and_steps)

# Keep the screen open till the user closes it.
wn.mainloop()
Copy

This draws like so:

Not all shapes like the one above can be drawn without lifting your pen, or going over an edge more than once. Which of these can be drawn?

Now read Wikipedia’s article (http://en.wikipedia.org/wiki/Eulerian_path) about Eulerian paths. Learn how to tell immediately by inspection whether it is possible to find a solution or not. If the path is possible, you’ll also know where to put your pen to start drawing, and where you should end up!

As it turns out, only four of the shapes can be drawn:

The code to do this is tedious, but simple in form. We use a function travel to move tess around. I wasn't sure how big I wanted to draw all the parts early on in the programing, so I invented a variable, regular_line, which I would play around with till things looked right. Due to the geometry involved in these shapes, we need three basics lengths for the lines, which for clarity I call little_diagonal, regular_line, and big_diagonal. Also due to reasons of geometry, little_diagonal = regular_line / 2**0.5 and big_diagonal = little_diagonal * 2. We could instead manually write in all the numbers, but it's better for code to be readable.

So here is the code: it's tedious but not especially mysterious.

import turtle

def travel(ttl, turns_and_steps):
    """Takes a turtle ttl and walks it through a series of turns_and_steps."""
    for x in turns_and_steps:
        ttl.left(x[0])
        ttl.forward(x[1])

# Set up turtle, window, and attributes.
wn = turtle.Screen()
tess = turtle.Turtle()
tess.speed(1)
tess.pensize(3)

# Move tess into place for first drawing.
tess.penup()              
tess.backward(300)
tess.pendown()

# Set sizes of the lines we'll need.
# The relations between these lengths are 
# dictated by the pythagorean theorem.
regular_line = 60
little_diagonal = regular_line / 2**0.5
big_diagonal = little_diagonal * 2

# First drawing.
turns_and_steps = [(0, regular_line), 
                   (135, little_diagonal),
                   (90, little_diagonal),
                   (45, regular_line),
                   (90, regular_line),
                   (90, regular_line)
]
travel(tess, turns_and_steps)

# Get in place for second drawing.
tess.penup()                       
travel(tess, [(-90, regular_line), 
              (-45, big_diagonal), 
              (45, 0)])

# Second drawing.
tess.pendown()       
travel(tess, [(180, regular_line),
              (-90, regular_line),
              (-135, big_diagonal),
              (135, regular_line),
              (90, regular_line),
              (-135, little_diagonal),
              (-90, little_diagonal)
])

# Get in place for third drawing.
tess.penup()                           
travel(tess, [(0, big_diagonal), (45, 0)])

# Third drawing.
tess.pendown()                        
travel(tess, [(90, regular_line),
              (135, little_diagonal),
              (90, little_diagonal),
              (45, regular_line),
              (90, regular_line),
              (90, regular_line),
              (-135, little_diagonal),
              (-90, big_diagonal),
              (-90, little_diagonal)
])

# Get in place for fourth drawing.
tess.penup()                        
travel(tess, [(135, regular_line * 1.5),
              (45, big_diagonal)
])

# Fourth drawing.
tess.pendown()        
travel(tess, [(135, regular_line),
              (90, regular_line),
              (90, regular_line),
              (90, regular_line),
              (135, big_diagonal),
              (-90, little_diagonal),
              (-90, little_diagonal),
              (-90, big_diagonal),
              (90, little_diagonal),
              (90, little_diagonal),
              (0, little_diagonal),
              (90, little_diagonal)           
])

# Keep the screen open till the user closes it.
wn.mainloop()
Copy

What will num_digits(0) return? Modify it to return 1 for this case. Why does a call to num_digits(-24) result in an infinite loop? (hint: -1//10 evaluates to -1) Modify num_digits so that it works correctly with any integer value. Add these tests:

test(num_digits(0) == 1)
test(num_digits(-12345) == 5)
Copy

This is a reference to a function found in 7.7, which reads like this:

def num_digits(n):
    count = 0
    while n != 0:
        count = count + 1
        n = n // 10
    return count
Copy

Rather than running through a loop, we can recognize that at root, this is a "string"-type question about the number of characters in a collection of digits. So we can simply take the absolute value of n to strip off the negative symbol so it doesn't get evaluated as a digit, convert the absolute value to a string, and count the number of characters in that string.

def num_digits(n):
    return len(str(abs(n)))

assert num_digits(-100) == 3
assert num_digits(-99) == 2
assert num_digits(-11) == 2
assert num_digits(-10) == 2
assert num_digits(-9) == 1
assert num_digits(-1) == 1
assert num_digits(0) == 1 
assert num_digits(1) == 1
assert num_digits(2) == 1
assert num_digits(9) == 1
assert num_digits(10) == 2
assert num_digits(11) == 2
assert num_digits(99) == 2
assert num_digits(100) == 3
assert num_digits(101) == 3 
assert num_digits(-12345) == 5
Copy

Write a function num_even_digits(n) that counts the number of even digits in n. These tests should pass:

test(num_even_digits(123456) == 3)
test(num_even_digits(2468) == 4)
test(num_even_digits(1357) == 0)
test(num_even_digits(0) == 1)
Copy

These tests pass with the following code:

def num_even_digits(n):
    n = abs(n)              # Strip off any potential negative symbol.
    n = str(n)              
    list_of_even_digits = ["0", "2", "4", "6", "8"]

    counter = 0
    for char in n:
        if char in list_of_even_digits:
            counter += 1
    return counter

assert num_even_digits(123456) == 3
assert num_even_digits(2468) == 4
assert num_even_digits(1357) == 0
assert num_even_digits(0) == 1
Copy

Write a function sum_of_squares(xs) that computes the sum of the squares of the numbers in the list xs. For example, sum_of_squares([2, 3, 4]) should return 4+9+16, which is 29.

def sum_of_squares(xs):
    sum = 0
    for x in xs:
        sum += x**2
    return sum

assert sum_of_squares([2, 3, 4]) == 29
assert sum_of_squares([]) == 0
assert sum_of_squares([2, -3, 4]) == 29
Copy

This page is released under the GNU Free Documentation License, any version 1.3 or later produced by the Free Software Foundation. I am grateful to the authors of the original textbook for releasing it that way: Peter Wentworth, Jeffrey Elkner, Allen B. Downey, and Chris Meyers.