Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Project: Math 367-17S
Views: 209
Image: ubuntu2204
Tweet
Share
Share
##############################################################################
###
### MATH 201 FALL 2017 SAGEMATH (COCALC) PYTHON EXAMPLES
###
###############################################################################

###### TABLE OF CONTENTS
#
#      use the toolbar button to the right of the large letter A to go to the line indicated.
#
#
#     57  Birthday problem
#     79  Pascal's Triangle
#    123  Prime numbers and modular arithmetic
#    180  Mod m multiplication, etc. tables
#    216  Euclidean algorithm
#    317  RSA baby examples










































nDays =365
listOfDays = [1..nDays]

classSize =25

nTrials = 1000
successCount =0
for _ in range(nTrials):
    #make a random sample of dates of size classSize
    sample=[]
    for _ in range(classSize):
        index=randint(0,nDays-1)
        sample.append(listOfDays[index])
    successCount += len(sample)>len(set(sample))
successCount
558 


p=[[1],[1,1]]
r = 12
for _ in range(r):
    
    previousRow=p[-1]
    l = len(previousRow)
    newRow =[1]
    for k in range(l-1):
        newRow.append(previousRow[k]+previousRow[k+1])
    newRow.append(1)
    p.append(newRow)

p                      

for r in p:
    print r
[1] [1, 1] [1, 2, 1] [1, 3, 3, 1] [1, 4, 6, 4, 1] [1, 5, 10, 10, 5, 1] [1, 6, 15, 20, 15, 6, 1] [1, 7, 21, 35, 35, 21, 7, 1] [1, 8, 28, 56, 70, 56, 28, 8, 1] [1, 9, 36, 84, 126, 126, 84, 36, 9, 1] [1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1] [1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1] [1, 12, 66, 220, 495, 792, 924, 792, 495, 220, 66, 12, 1] [1, 13, 78, 286, 715, 1287, 1716, 1716, 1287, 715, 286, 78, 13, 1] 
p=[[1],[1,1]]
m = 2
r = 15
for _ in range(r):
    
    previousRow=p[-1]
    l = len(previousRow)
    newRow =[1]
    for k in range(l-1):
        newRow.append(mod(previousRow[k]+previousRow[k+1],m))
    newRow.append(1)
    p.append(newRow)

for r in p:
    print r
[1] [1, 1] [1, 0, 1] [1, 1, 1, 1] [1, 0, 0, 0, 1] [1, 1, 0, 0, 1, 1] [1, 0, 1, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 0, 0, 0, 0, 0, 1] [1, 1, 0, 0, 0, 0, 0, 0, 1, 1] [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1] [1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1] [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1] [1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1] [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] 
for r in p:
    for v in r:
        print v,
    print
1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 
Mod(5, 12)
prime_range(100)
prime_pi(10^6)
5 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 78498 
j=8675309
j.is_prime()
True 
plot(prime_pi(x),(x,1,1000))

m=[[mod(a^k,17) for k in range(1,17)]for a in range(1,17)]

matrix_plot(m,cmap='seismic', colorbar=true)


j.is_prime()
True 
trials = 10000
n = 1000000000
counter = 0
for _ in range(trials):
    k = randint(1,n)
    k= floor(k)
    counter += k.is_prime()
counter
497 
prime_pi(10^9)
50847534 


m = 7
a = mod(3,7)
a
3 
a^67
3 
a^5
5 
for k in [1..10]:
    print k, a^k
1 3 2 2 3 6 4 4 5 5 6 1 7 3 8 2 9 6 10 4 
1/a
5 
m=15
headerRow=['x']+range(1,m)
data=[headerRow]
for r in range(1,m):
    data.append([r]+[mod(r*c,m) for c in range(1,m)])
table(data,header_row=True, header_column=True)
x | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 1 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 | 2 4 6 8 10 12 14 1 3 5 7 9 11 13 3 | 3 6 9 12 0 3 6 9 12 0 3 6 9 12 4 | 4 8 12 1 5 9 13 2 6 10 14 3 7 11 5 | 5 10 0 5 10 0 5 10 0 5 10 0 5 10 6 | 6 12 3 9 0 6 12 3 9 0 6 12 3 9 7 | 7 14 6 13 5 12 4 11 3 10 2 9 1 8 8 | 8 1 9 2 10 3 11 4 12 5 13 6 14 7 9 | 9 3 12 6 0 9 3 12 6 0 9 3 12 6 10 | 10 5 0 10 5 0 10 5 0 10 5 0 10 5 11 | 11 7 3 14 10 6 2 13 9 5 1 12 8 4 12 | 12 9 6 3 0 12 9 6 3 0 12 9 6 3 13 | 13 11 9 7 5 3 1 14 12 10 8 6 4 2 14 | 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
m=15
nums = m.coprime_integers(m)
headerRow=['x']+nums
data=[headerRow]
for r in nums:
    data.append([r]+[mod(r*c,m) for c in nums])
table(data,header_row=True, header_column=True)
x | 1 2 4 7 8 11 13 14 +----+----+----+----+----+----+----+----+----+ 1 | 1 2 4 7 8 11 13 14 2 | 2 4 8 14 1 7 11 13 4 | 4 8 1 13 2 14 7 11 7 | 7 14 13 4 11 2 1 8 8 | 8 1 2 11 4 13 14 7 11 | 11 7 14 2 13 1 8 4 13 | 13 11 7 1 14 8 4 2 14 | 14 13 11 8 7 4 2 1 


m=7
headerRow=['+']+range(m)
data=[headerRow]
for r in range(m):
    data.append([r]+[mod(r+c,m) for c in range(m)])
table(data,header_row=True, header_column=True)
+ | 0 1 2 3 4 5 6 +---+---+---+---+---+---+---+---+ 0 | 0 1 2 3 4 5 6 1 | 1 2 3 4 5 6 0 2 | 2 3 4 5 6 0 1 3 | 3 4 5 6 0 1 2 4 | 4 5 6 0 1 2 3 5 | 5 6 0 1 2 3 4 6 | 6 0 1 2 3 4 5 
m=24
headerRow=['^']+range(1,m)
data=[headerRow]

for r in range(1,m):
    data.append([r]+[mod(r^c,m) for c in range(1,m)])
table(data,header_row=True, header_column=True)
^ | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 +----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+ 1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 | 2 4 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 3 | 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 9 3 4 | 4 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 5 | 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 1 5 6 | 6 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 | 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 1 7 8 | 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 9 | 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 10 | 10 4 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 11 | 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 1 11 12 | 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 | 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 1 13 14 | 14 4 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 15 | 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 9 15 16 | 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 17 | 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 1 17 18 | 18 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 19 | 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 1 19 20 | 20 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 16 8 21 | 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 9 21 22 | 22 4 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 23 | 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 1 23 
m=24
nums = m.coprime_integers(m)

headerRow=['x']+nums
data=[headerRow]

for r in nums:
    data.append([r]+[mod(r*c,m) for c in nums])
table(data,header_row=True, header_column=True)
x | 1 5 7 11 13 17 19 23 +----+----+----+----+----+----+----+----+----+ 1 | 1 5 7 11 13 17 19 23 5 | 5 1 11 7 17 13 23 19 7 | 7 11 1 5 19 23 13 17 11 | 11 7 5 1 23 19 17 13 13 | 13 17 19 23 1 5 7 11 17 | 17 13 23 19 5 1 11 7 19 | 19 23 13 17 7 11 1 5 23 | 23 19 17 13 11 7 5 1 

def EALengthPrint(a,b):
    #count number of steps in Euclidean Algorithm
    #if a<b then switch em
    if a < b:
        temp = a
        a = b
        b = temp
        
    
    
    steps =0
    r=b
    while r>0:
        q= floor(a/b)
        r = a%b
        print('%s=%s*%s+%s'%(a,q,b,r))
        temp = b
        r = a% b
        a = temp
        b = r
        
        steps += 1
    print('number of steps = %s'%steps)

EALengthPrint(1999,2000)
2000=1*1999+1 1999=1999*1+0 number of steps = 2 
def EALengthOut(a,b):
    #count number of steps in Euclidean Algorithm
    #if a<b then switch em
    if a < b:
        temp = a
        a = b
        b = temp
        
    
    
    steps =0
    r=b
    while r>0:
        q= floor(a/b)
        r = a%b
        #print('%s=%s*%s+%s'%(a,q,b,r))
        temp = b
        r = a% b
        a = temp
        b = r
        
        steps += 1
    return steps

EALengthOut(144,34)
3 
n=100000
g=sqrt(2)
float(log(n,g))
lengthData = [EALengthOut(n,k) for k in [1..n]]
histogram(lengthData)
max(lengthData)
33.21928094887362
19 
lengthData.index(19)
53532 
EALengthPrint(53533,100000)
100000=1*53533+46467 53533=1*46467+7066 46467=6*7066+4071 7066=1*4071+2995 4071=1*2995+1076 2995=2*1076+843 1076=1*843+233 843=3*233+144 233=1*144+89 144=1*89+55 89=1*55+34 55=1*34+21 34=1*21+13 21=1*13+8 13=1*8+5 8=1*5+3 5=1*3+2 3=1*2+1 2=2*1+0 number of steps = 19 


n=500000000
x=randint(1,n); y=randint(1,n)
EALengthOut(x,y)
18 
matrix_plot(m,figsize=9,origin='lower',cmap='GnBu',colorbar=true)

for x in [1..n]:
    for y in [1..n]:
        if EALengthOut(x,y)==9:
            print x,y
55 89 89 55 
m=13
m.coprime_integers(m)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 
a=mod(13,60)
a^(-1)
37 
13*37
481 
n=77

e=17   #encoder exponent
f=53  #decoder exponent

for x in range(n):
    y=mod(x^e,n)
    print x, y, mod(y^f,n)
0 0 0 1 1 1 2 18 2 3 75 3 4 16 4 5 3 5 6 41 6 7 28 7 8 57 8 9 4 9 10 54 10 11 44 11 12 45 12 13 62 13 14 42 14 15 71 15 16 25 16 17 19 17 18 72 18 19 24 19 20 48 20 21 21 21 22 22 22 23 67 23 24 40 24 25 9 25 26 38 26 27 69 27 28 63 28 29 50 29 30 46 30 31 26 31 32 65 32 33 66 33 34 34 34 35 7 35 36 64 36 37 60 37 38 47 38 39 30 39 40 17 40 41 13 41 42 70 42 43 43 43 44 11 44 45 12 45 46 51 46 47 31 47 48 27 48 49 14 49 50 8 50 51 39 51 52 68 52 53 37 53 54 10 54 55 55 55 56 56 56 57 29 57 58 53 58 59 5 59 60 58 60 61 52 61 62 6 62 63 35 63 64 15 64 65 32 65 66 33 66 67 23 67 68 73 68 69 20 69 70 49 70 71 36 71 72 74 72 73 61 73 74 2 74 75 59 75 76 76 76 
43^17
5874403106360420018879553643 
mod(54^17, 77)
10 
mod(10^53,77)
54 
#another baby example
n= 13*67;n
871 
e= 31 #public encoder
x= 574
y= mod(x^e,n) #encoded message
y
440 
phi = 12*66;phi
792 
f = mod(31^(-1),phi);f
511 
31*511
15841 
float(31*511/792)
20.001262626262626 
20*792
15840 
mod(440^511,871)
574 
#new example
p=61; q= 17
n=p*q; phi= (p-1)*(q-1)
e=19 #encoder exponent
print n, phi
1037 960 
#find the decoder
f = mod(1/e, phi);f
859 
x= 826 #message
y= mod(x^e,n); y #encoded message
830 
#decode message
mod(y^f,n)
826 


#homework 9.5.2
mod(1/52,77)
40 
(52*40-1)/77
27 
gcd(77,52)
1 
xgcd(77,52)
(1, 25, -37) 

# FERMAT'S LITTLE THEOREM AND ITS FRIENDS

p= 31
a =23
mod(a^(p-1),p)
1 
120.next_prime()
127 
mod(66666^752272,752273)
1 
n=13*127;n
1651 
mod(211^1512,n)
1 
phi = 12*126;phi
1512 
mod(10^phi,n)
1