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.
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")
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
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=" ")
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")
In [2]:
mixed_list = [3, 5.14, "hello", True, [5], range]
print(mixed_list, type(mixed_list))
Lists are indexable, starting at 0:
In [11]:
mixed_list[0]
Out[11]:
In [12]:
mixed_list[2]
Out[12]:
Negative indices are counted from the tail:
In [3]:
mixed_list[-1]
Out[3]:
In [4]:
mixed_list[-2] == mixed_list[2]
Out[4]:
Lists can be sliced:
In [5]:
mixed_list[1:3]
Out[5]:
In [21]:
mixed_list[:2]
Out[21]:
In [6]:
mixed_list[1:]
Out[6]:
In [7]:
mixed_list[:-2]
Out[7]:
In [10]:
mixed_list[:1]
Out[10]:
In [12]:
mixed_list[7:8]
Out[12]:
In [13]:
mixed_list[7]
Lists can be concatenated:
In [14]:
mixed_list + [1, 2, 3]
Out[14]:
But this doesn't change the list, but creates a new list:
In [15]:
mixed_list
Out[15]:
In [16]:
mixed_list = mixed_list + [1, 2, 3]
mixed_list
Out[16]:
Some functions can be used on lists:
In [17]:
numbers = [10, 3, 2, 56]
numbers
Out[17]:
In [18]:
sum(numbers)
Out[18]:
In [19]:
sum(['hello','world'])
In [51]:
len(numbers)
Out[51]:
In [52]:
len(['hi','hello'])
Out[52]:
In [53]:
print(sorted(numbers))
print(numbers)
print(numbers.sort())
print(numbers)
Lists are iterable:
In [20]:
mixed_list
Out[20]:
In [55]:
for item in mixed_list:
if type(item) == str:
print(item)
In [21]:
for i in range(len(mixed_list)):
print(i)
if type(mixed_list[i]) == str:
print(mixed_list[i])
In [22]:
print(i)
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)
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]:
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]:
In [1]:
l = []
l += [1]
l.
Out[1]:
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)
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)
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))
In [9]:
%timeit max3(100,45,67)
%timeit max3(45,67,100)
%timeit max3v2(100,45,67)
%timeit max3v2(45,67,100)
max3
or max3v2
?max4
?
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)
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]
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)])
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))
In [78]:
%timeit -n 100 divisors(10**4)
%timeit -n 100 divisors2(10**4)
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.