## 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 [ ]: