CS1001.py

Extended Introduction to Computer Science with Python, Tel-Aviv University, Spring 2013

Recitation 2 - 7-11.3.2013

Last update: 24.4.2013 - added XKCD comic

Getting input from the user

You can get input from the user by calling the input function:

m = int(input("enter a positive integer to apply Collatz algorithm: "))

Note that input returns a string and therefore you are responsible to convert it to the appopriate type.

Collatz Conjecture

The Collatz Conjecture (also known as the 3n+1 conjecture) is the conjecture that the following process is finite for every natural number:

If the number $n$ is even divide it by two ($n/2$), if it is odd multiply it by 3 and add 1 ($3n+1$). Repeat this process untill you get the number 1.

Implementation

We start with the "Half Or Triple Plus One" process:


In [1]:
m = 100 # integer to apply the conjecture on

n = m
while n != 1:
    print(n, end=", ")
    if n % 2 == 0:
        n = n // 2
    else:
        n = 3 * n + 1
print(1) # 1 was not printed
print(m, "is OK")


100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
100 is OK

Next we add another loop that will run the conjecture check on a range of numbers:


In [30]:
limit = 10
m = 1
while m <= limit:
    n = m
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
    print(m, "is OK")
    m += 1


1 is OK
2 is OK
3 is OK
4 is OK
5 is OK
6 is OK
7 is OK
8 is OK
9 is OK
10 is OK

When a loop goes over a simple range it is easier to use the range function with a for loop - and more robust against bugs:


In [35]:
for m in range(111, 98, -2):
    print(m, end=" ")


111 109 107 105 103 101 99 

In [36]:
start, stop = 99, 110
for m in range(start, stop + 1):
    n = m
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
    print(m, "is OK")


99 is OK
100 is OK
101 is OK
102 is OK
103 is OK
104 is OK
105 is OK
106 is OK
107 is OK
108 is OK
109 is OK
110 is OK

Lists

Lists are sequences of values.

Lists can contain a mix of types:


In [2]:
mixed_list = [3, 5.14, "hello", True, [5], range]
print(mixed_list, type(mixed_list))


[3, 5.14, 'hello', True, [5], <class 'range'>] <class 'list'>

Lists are indexable, starting at 0:


In [11]:
mixed_list[0]


Out[11]:
3

In [12]:
mixed_list[2]


Out[12]:
'hello'

Negative indices are counted from the tail:


In [3]:
mixed_list[-1]


Out[3]:
builtins.range

In [4]:
mixed_list[-2] == mixed_list[2]


Out[4]:
False

Lists can be sliced:


In [5]:
mixed_list[1:3]


Out[5]:
[5.14, 'hello']

In [21]:
mixed_list[:2]


Out[21]:
[3, 5.14]

In [6]:
mixed_list[1:]


Out[6]:
[5.14, 'hello', True, [5], builtins.range]

In [7]:
mixed_list[:-2]


Out[7]:
[3, 5.14, 'hello', True]

In [10]:
mixed_list[:1]


Out[10]:
[3]

In [12]:
mixed_list[7:8]


Out[12]:
[]

In [13]:
mixed_list[7]


---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-13-d8a75e7ae27c> in <module>()
----> 1 mixed_list[7]

IndexError: list index out of range

Lists can be concatenated:


In [14]:
mixed_list + [1, 2, 3]


Out[14]:
[3, 5.14, 'hello', True, [5], builtins.range, 1, 2, 3]

But this doesn't change the list, but creates a new list:


In [15]:
mixed_list


Out[15]:
[3, 5.14, 'hello', True, [5], builtins.range]

In [16]:
mixed_list = mixed_list + [1, 2, 3]
mixed_list


Out[16]:
[3, 5.14, 'hello', True, [5], builtins.range, 1, 2, 3]

Some functions can be used on lists:


In [17]:
numbers = [10, 3, 2, 56]
numbers


Out[17]:
[10, 3, 2, 56]

In [18]:
sum(numbers)


Out[18]:
71

In [19]:
sum(['hello','world'])


---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-19-a479ce694266> in <module>()
----> 1 sum(['hello','world'])

TypeError: unsupported operand type(s) for +: 'int' and 'str'

In [51]:
len(numbers)


Out[51]:
4

In [52]:
len(['hi','hello'])


Out[52]:
2

In [53]:
print(sorted(numbers))
print(numbers)
print(numbers.sort())
print(numbers)


[2, 3, 10, 56]
[10, 3, 2, 56]
None
[2, 3, 10, 56]

Lists are iterable:


In [20]:
mixed_list


Out[20]:
[3, 5.14, 'hello', True, [5], builtins.range, 1, 2, 3]

In [55]:
for item in mixed_list:
    if type(item) == str:
        print(item)


hello

In [21]:
for i in range(len(mixed_list)):
    print(i)
    if type(mixed_list[i]) == str:
        print(mixed_list[i])


0
1
2
hello
3
4
5
6
7
8

In [22]:
print(i)


8

In [28]:
i = 0 # important!
while i < len(mixed_list) and type(mixed_list[i]) != int:
    if type(mixed_list[i]) == str:
        print(mixed_list[i])
    i += 1

In [27]:
print(i)


9

A list of numbers can be created using list comprehension. The syntax is:

[**statement** for **variable** in **iterable** if **condition**]

The if **condition** part is optional, the statement and the condition can use variable.

Create a list of the squares of numbers between 1 and 10:


In [29]:
[x ** 2 for x in range(1, 11)]


Out[29]:
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

Create a list of the square roots of odd numbers between 1 and 20:


In [30]:
[x ** 0.5 for x in range(1, 21) if x % 2 == 1]


Out[30]:
[1.0,
 1.7320508075688772,
 2.23606797749979,
 2.6457513110645907,
 3.0,
 3.3166247903554,
 3.605551275463989,
 3.872983346207417,
 4.123105625617661,
 4.358898943540674]

In [1]:
l = []
l += [1]
l.


Out[1]:
[1]

Grades problem

Given a list of grades, count how many are above the average.


In [4]:
grades = [33, 55,45,87,88,95,34,76,87,56,45,98,87,89,45,67,45,67,76,73,33,87,12,100,77,89,92]

In [5]:
avg = sum(grades)/len(grades)
above = 0
for gr in grades:
    if gr > avg:
        above += 1
        
print(above, "grades are above the average", avg)


15 grades are above the average 68.07407407407408

Using list comprehension:


In [6]:
avg = sum(grades)/len(grades)
above = len([gr for gr in grades if gr > avg])
        
print(above, "grades are above the average", avg)


15 grades are above the average 68.07407407407408

Functions

Maximum and minimum


In [8]:
def max2(a,b):
    if a >= b:
        return a
    else:
        return b

def min2(a,b):
    if a <= b:
        return a
    else:
        return b
    
def max3(a,b,c):
    if a >= b and a >= c:
        return a
    elif b >= a and b >= c:
        return b
    else:
        return c

def max3v2(a,b,c):
    max_ab = max2(a,b)
    return max2(max_ab,c)

print(max2(5,10))
print(min2(5,10))
print(max3(5,10,10))
print(max3v2(5,10,10))


10
5
10
10

In [9]:
%timeit max3(100,45,67)
%timeit max3(45,67,100)
%timeit max3v2(100,45,67)
%timeit max3v2(45,67,100)


1000000 loops, best of 3: 905 ns per loop
1000000 loops, best of 3: 893 ns per loop
1000000 loops, best of 3: 1.54 us per loop
1000000 loops, best of 3: 1.53 us per loop
  • Which should be faster, max3 or max3v2?
  • How would you implement max4?

Perfect numbers

A perfect number is a number that is equal to the sum of its divisors:


In [62]:
def is_perfect(n):
    '''
    is_perfect(integer) -> bool
    Return True iff n equals the sum of its divisors
    '''
    if n == sum(divisors(n)):
        return True
    else:
        return False

help(is_perfect)


Help on function is_perfect in module __main__:

is_perfect(n)
    is_perfect(integer) -> bool
    Return True iff n equals the sum of its divisors


In [12]:
def divisors(n):
    '''
    divisors(integer) -> list of integers
    Return the proper divisors of n (numbers less than n that divide evenly into n).
    '''
    return [div for div in range(1,n) if n % div == 0]

Notes

  • Functions that return a boolean are named with is_ as a prefix.
  • Use ''' after the function definition to create function documentation
  • in is_perfect we can return the condition value instead of using the if-else clause:

In [64]:
def is_perfect(n):
    '''
    is_perfect(integer) -> bool
    Return True iff n equals the sum of its divisors
    '''
    return n == sum(divisors(n))

In [67]:
print("perfect numbers in range(1,1000)\n")
print([n for n in range(1,1001) if is_perfect(n)])


perfect numbers in range(1,1000)

[6, 28, 496]

Complexity

We can write another version of divisors that is more efficient by iterating only on numbers between 1 and $\frac{n}{2}$, but this function is more complex and bugs are crawling in it:


In [19]:
def divisors2(n):
    divs = []
    for m in range(2,round(n * 0.5)):#1 and n**0.5 will be handled separately. why?
        if n % m == 0:
            divs += [m, n // m]
    divs += [1] # 1 surely divides n
    return divs

In [20]:
print(divisors(6))
print(divisors2(6))


[1, 2, 3]
[2, 3, 1]

In [78]:
%timeit -n 100 divisors(10**4)
%timeit -n 100 divisors2(10**4)


100 loops, best of 3: 6.83 ms per loop
100 loops, best of 3: 3.33 ms per loop

Fin

This notebook is part of the Extended introduction to computer science course at Tel-Aviv University.

The notebook was written using Python 3.2 and IPython 0.13.1.

The code is available at https://raw.github.com/yoavram/CS1001.py/master/recitation2.ipynb.

The notebook can be viewed online at http://nbviewer.ipython.org/urls/raw.github.com/yoavram/CS1001.py/master/recitation2.ipynb.

The notebooks is also available as a PDF at https://github.com/yoavram/CS1001.py/blob/master/recitation2.pdf?raw=true.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.