Quiz 1 Solutions

In [1]:
print(3*'ha')
hahaha
In [2]:
99//100
Out[2]:
0
In [3]:
a,b,c = 5,'hi',7
b
Out[3]:
'hi'
In [4]:
i = 10
while i>0:
    i -= 2
    print(i)
print('wow')
8
6
4
2
0
wow
In [5]:
for i in range(4):
    print(i,i**2,i%2)
    
0 0 0
1 1 1
2 4 0
3 9 1
In [1]:
def period(n):  # random function name
    if n<0: return n
    return 0
In [7]:
period(-17)
Out[7]:
-17
In [8]:
period(33)
Out[8]:
0

Testing if a number is a square integer

In [9]:
# Is csq a square
csq = 30
from math import sqrt
sqrt(csq)
Out[9]:
5.477225575051661
In [10]:
type(sqrt(csq))
Out[10]:
float
In [12]:
int(sqrt(csq)) == sqrt(csq)
Out[12]:
False
In [ ]:
5 != 5.4772...
In [13]:
csq = 25
int(sqrt(csq)) == sqrt(csq)
Out[13]:
True

This will work for all sufficiently small square integers.

In [18]:
x = 54783272879898898989**2 #83248927985275498280**2
sqrtx = sqrt(x)
isqrtx = int(sqrtx)
isthisx = isqrtx**2
isthisx == x
Out[18]:
False

We see this test for square integers fails for large numbers. A better way.

Better idea: pre-make a list of all the square integers up to the needed maximum.

In [20]:
# a clunky way: appending to a list

max = 5 # max value for a and/or b
squares = []
for i in range(2*max):
    squares.append(i**2)
squares
Out[20]:
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
In [21]:
# a better way: using a "list comprehension"
# A concise way of building lists
[i**2 for i in range(max)]
Out[21]:
[0, 1, 4, 9, 16]

[ expression for variable in iterableexpression]

In [22]:
['hello' for i in range(max)]
Out[22]:
['hello', 'hello', 'hello', 'hello', 'hello']
In [23]:
[z**2 for z in range(max)]
Out[23]:
[0, 1, 4, 9, 16]
In [4]:
max = 20
squares = [i**2 for i in range(2*max)]
In [5]:
squares
Out[5]:
[0,
 1,
 4,
 9,
 16,
 25,
 36,
 49,
 64,
 81,
 100,
 121,
 144,
 169,
 196,
 225,
 256,
 289,
 324,
 361,
 400,
 441,
 484,
 529,
 576,
 625,
 676,
 729,
 784,
 841,
 900,
 961,
 1024,
 1089,
 1156,
 1225,
 1296,
 1369,
 1444,
 1521]
In [ ]:
Then to test if "csq" is a square, just ask is it in the list?
In [30]:
25 in squares
Out[30]:
True
In [31]:
26 in squares
Out[31]:
False
In [32]:
if 25 in squares: print("Yes it's a square.")
Yes it's a square.
In [33]:
if 25 in squares: print('Yes it\'s a square.')
Yes it's a square.
In [34]:
max = 100
squares = [i**2 for i in range(2*max)]

for a in range(1,max):
    for b in range(a,max):
        csq = a**2 + b**2
        if csq in squares: print(a,b)
3 4
5 12
6 8
7 24
8 15
9 12
9 40
10 24
11 60
12 16
12 35
13 84
14 48
15 20
15 36
16 30
16 63
18 24
18 80
20 21
20 48
20 99
21 28
21 72
24 32
24 45
24 70
25 60
27 36
28 45
28 96
30 40
30 72
32 60
33 44
33 56
35 84
36 48
36 77
39 52
39 80
40 42
40 75
40 96
42 56
45 60
48 55
48 64
48 90
51 68
54 72
56 90
57 76
60 63
60 80
60 91
63 84
65 72
66 88
69 92
72 96
80 84
In [35]:
5%2==0  # odd
Out[35]:
False
In [36]:
56%2==0  # even
Out[36]:
True

Primality testing

A very inefficient brute-force way of testing to see if a number is prime: check to see if it is divisible by all smaller postive integers (>1).

In [37]:
def isprime0(n):
    for i in range(2,n):
        if n%i==0: return False
    return True
In [ ]:
isprime0(2**478237467486-1)

Lists and accessing their elements

In [1]:
mylist = ['a','bb','c','d','z']
In [3]:
mylist[0]
Out[3]:
'a'
In [4]:
mylist[1]
Out[4]:
'bb'
In [5]:
mylist[-1]
Out[5]:
'z'
In [6]:
mylist[-1] = 7777
mylist
Out[6]:
['a', 'bb', 'c', 'd', 7777]

"Slicing" lists

In [7]:
mylist[1:4]
Out[7]:
['bb', 'c', 'd']
In [8]:
mylist[1:4:2]
Out[8]:
['bb', 'd']

How do you find the length of a list (or other list-like thing)?

In [9]:
len(mylist)
Out[9]:
5

How do you get a slice that goes all the way to the end? (Can't use -1 for "stop" because then the very last won't be included.) Answer: omit the "stop".

In [10]:
mylist[2:]  # from 2 to the end
Out[10]:
['c', 'd', 7777]
In [11]:
mylist[:4] # from the beginning to 3
Out[11]:
['a', 'bb', 'c', 'd']

Sieve of Eratosthenes

A more efficient way of generating a list of the primes

In [12]:
# Idea: start with a list of all Trues
# Change all those with non-prime index to False
max = 10
# by hand:
isprime = [False,False,True,True,False,True,False,True,False,False,False]
In [13]:
isprime[7]  # tells us if 7 is prime or not
Out[13]:
True

Want to construct a longer version of this list using code ...

In [14]:
max = 4000
isprime = [True for n in range(max+1)]
In [ ]: