Seminar 04

In [30]:

    

# Some math utility functions

from math import sqrt

'''
Simple primality test
'''
def is_prime(n):
    if n == 2:
        return True
    if n % 2 == 0 or n <= 1:
        return False

    sqr = int(sqrt(n)) + 1

    for divisor in range(3, sqr, 2):
        if n % divisor == 0:
            return False
    return True


from math import gcd as bltin_gcd
'''
Check if two numbers are coprime
'''
def coprime2(a, b):
    return bltin_gcd(a, b) == 1


'''
Check if number is of the form p^k, and return k
TODO: p must be prime !
'''
def is_multiple_of_k(number):
    # copy value ?
    if sqrt(number) == int(sqrt(number)):
        return int(sqrt(number))
    # if number != p^2 -> p^n, n > 2, while p^n > 1.0 ?
    power = 3
    last_good = -1
    while number:
        root = number ** 1/power
#         print('root: ', root)
#         print('power: ', power)
        if root == int(root):
            last_good = int(root)
        elif root <= 1.1:
            if last_good != -1:
                return last_good
            return -1
        power += 1
# alternative, for every number < sqrt(number), check if number % integer == int(...)
        
print(is_multiple_of_k(4))
print(is_multiple_of_k(100))

print(is_multiple_of_k(101))
print(is_multiple_of_k(32))

# recommended: do prime factorization of a number (rule 3), and after that use rule 4


    

    




2
10
-1
2

In [31]:

    

'''
Euler's totient calculator
- costly
'''
def calculate_euler_totient(p):
    if p == 1:
        return 1
    elif is_prime(p):
        return p-1
    #elif 
        #coprime2(a, b):
#     elif is_multiple_of_k(p) != -1:
#         return p - p^e-1
    

print('\nEuler\'s totient function')
print('  \u03D5(%s) = %s ' % ( 1, str(calculate_euler_totient(1)) ))
print('  \u03D5(%s) = %s ' % ( 3, str(calculate_euler_totient(3)) ))


    

    




Euler's totient function
  ϕ(1) = 1 
  ϕ(3) = 2 

In [ ]: