pbset2.sagews

# Problem set 2

reset

<function reset at 0x7f5816de7050>

#Some useful SageMath commands
#prime_range:
prime_range(20)

[2, 3, 5, 7, 11, 13, 17, 19]

#next_prime, previous_prime
next_prime(15)

17

#ceiling function:
ceil(13^0.5)

4

#Greatest common divisor
gcd(45,27)

9

#Solving the LDE a*x+b*y=gcd(a,b)
#Example. a=7, b=5
xgcd(7,5)

(1, -2, 3)

#Check:
7*(-2)+5*3==1

True

#Including legend into a plot with multiple graphs
#Example.
f(x)=1-x; g(x)=x^2-2*x
p=plot(f(x),0,2,legend_label='line',color='green',thickness=2)
q=plot(g(x),0,2,legend_label='x^2-2x',color='red',thickness=2)
show(p+q,figsize=[4,2])

#Exercise 1 (demo): Goldbach conjecture
def my_goldbach(n): #n must be even
    L=prime_range(n/2)
    S=[]
    for c in L:
        if is_prime(n-c):
            S.append([c,n-c])
    return S
my_goldbach(100)

[[3, 97], [11, 89], [17, 83], [29, 71], [41, 59], [47, 53]]

#Exercise 2(a): Eratosthenes algorithm (template)
reset()
#Simple code snippet
#Input: list of integers L and an integer m
# Output: list L with multiples of m removed
def remove_multiple(m,L):
    for c in L:
        if (c % m)==0:
            L.remove(c)
    return L
#Example
L=[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
remove_multiple(2,L)

[3, 5, 7, 9, 11, 13, 15, 17, 19]

remove_multiple(L[0],L)# Think what L[0] is in this command

[5, 7, 11, 13, 17, 19]

#Exercise 3: Eratosthenes algorithm
def simple_erato(n):#Fill in the blanks
    S=[] # S is a placeholder for primes <k that will be removed
    L=[j for j in range(2,n+1)]# list of numbers <=n with L[0]=2; L will be changing
    k= floor(sqrt(n)) # Fact:for any composite number less or equal n there is a prime factor <=k
    while L[0]<=k:
        S.append(L[0])
        remove_multiple(L[0],L)
    return S+L
simple_erato(20)

[2, 3, 5, 7, 11, 13, 17, 19]

#Alternative template for Eratosthenes algorithm
def fancy_erato(n):
    S=[] # S is a placeholder for primes <k
    L=[j for j in range(2,n+1)]# list of numbers from <=n with L[0]=2; L will be changing
    k= floor(sqrt(n)) # for any composite number less or equal n there is a prime factor <=k
    while L[0]<=k:
        S.append(L[0])
        L=filter(lambda a: a % L[0]!=0, L) # compact form of our function remove_multiple
        # != means "not equal"; when a%L[0]!=0 is False, the element a is filtered (removed)
    S=S+L
    return S

fancy_erato(20)

[2, 3, 5, 7, 11, 13, 17, 19]

#Exercise 3 (template): Fermat's factorization algorithm is based on the following fact:
#Every odd number N is the difference of squares, N=a^2-b^2=(a-b)*(a+b).
def fermat_factors(N): # N should be odd
    a = math.ceil(sqrt(N))# calling math is important. It returns a as decimal number
    b = math.sqrt(a^2-N)
    print(a,b)
    while floor(b)-b!=0:#The condition should verify if b is an integer
        a = a + 1# Alternative Python-like form of this command: a+=1
        b = math.sqrt(a^2-N)
        print a,b
    print "a =", a
    print "b =", b
    print "c =", a+b
    print "d =", a-b
#Test 
fermat_factors(20)

(5.0, 2.23606797749979) 6.0 4.0 a = 6.0 b = 4.0 c = 10.0 d = 2.0

#Exercise 4: Counting primes
#Directions
#Sage uses notation prime_pi for Prime Counting Function. Sage also knows function Li.
#Define the function x/log(x). Make plots of the the three functions and store them under names of your choice.Include legend into each plot. Then plot all three plots in one figure using command show.
f(x)=x/log(x)
p1=plot(prime_pi(x),3,1000,color="green",figsize=[4,3],legend_label="Pi")
p2=plot(li(x),3,1000,color="red",figsize=[4,3],legend_label="Li")
p3=plot(f(x),3,1000,color="blue",figsize=[4,3],legend_label="f(x)")
show(p1+p2+p3,figsize=[4,3])

#Exercise 8: Constructing one PPT (template)
#Input: a rational number r, 0<r<1
#Output: legs of the ppt defined by
def one_ppt(r):
    m=numerator(r)
    n=denominator(r)
    if m%2 - n%2 ==0:
        print('both m and n are odd')
    else:
        a=2*m+1;
        b=2*n+1;
        return [a,b,sqrt(a^2+b^2)]
one_ppt(2/3)

[5, 7, sqrt(74)]

#Check:
sqrt(5^2+12^2)

13