igorvanloo

def DijkstrasAlgorithm(graph, start_node = 0, INFINITY = 10**10):
    #Takes a weighted adjacency list as input of the graph
    n = len(graph)
    D = [INFINITY]*n
    D[start_node] = 0
    cloud = [False for i in range(n)]
    
    for i in range(n):
        _, v = min((D[i], i) for i in range(n) if cloud[i] == False)
        cloud[v] = True

igorvanloo

def legendre_symbol(a, p):
    t = pow(a, (p-1)//2, p)
    if t == p - 1:
        return -1
    return t

def tonelli_shanks(a, p):
    if legendre_symbol(a, p) != 1:
        return 0
    elif a == 0:

igorvanloo

def admissible_numbers(p, n, primes, limit):
    a_n = [n] #admissible numbers
    i = primes.index(p) #index
    if n > limit:
        return []
    a_n += admissible_numbers(p, n*p, primes, limit)
    if i + 1 < len(primes):
        n_p = primes[i + 1] #next prime
        a_n += admissible_numbers(n_p, n*n_p, primes, limit)
    return a_n

igorvanloo

def k_smooth_numbers(max_prime, limit):
    k_s_n = [1]
    p = list_primes(max_prime)
    while len(p) != 0:
        temp_k_s_n = []
        curr_p = p.pop(0)
        power_limit = int(math.log(limit, curr_p)) + 1
        curr_multiples = [curr_p**x for x in range(1, power_limit + 1)]
        for x in curr_multiples:
            for y in k_s_n:

igorvanloo

def sum_decimals(num, den):
    num_digits = 0
    digit_sum = 0
    while True:
        num *= 10
        temp = math.floor(num/den)
        digit_sum += temp
        num_digits += 1
        num -= temp*den
        if num == 1:

igorvanloo

def compute():
    total = 0
    array = dict()
    for cb in range(2, int(10**(9/3)) + 1):
        for sq in range(2, int(10**(4.5)) + 1):
            t = cb*cb*cb + sq*sq
            if str(t) == str(t)[::-1]:
                if t in array:
                    array[t] += 1
                else:

igorvanloo

def primepi(limit):
  def Prime_sieve(n): #Sieve of Eratosthenes
    result = [True] * (n + 1)
    result[0] = result[1] = False
    for i in range(int(math.sqrt(n)) + 1):
      if result[i]:
        for j in range(2 * i, len(result), i):
          result[j] = False
    return result
  

igorvanloo

def Mobius(n):
    if n == 1:
        return 1
    d = 2
    num_of_primes = 0
    while n > 1:
        while n % d == 0:
            num_of_primes += 1
            if n % (d*d) == 0:
                return 0

igorvanloo

def phi(n):
    if n == 1:
        return 1
    phi = 1
    d = 2 
    while n > 1:
        count = 0 
        while n % d == 0:
            count += 1
            n /= d

igorvanloo

def lcm(numbers):
    n = sorted(numbers) #I want to start with the largest numbers
    curr = n.pop(-1) #Remove the biggest
    while len(n) != 0:
        temp = n.pop(-1)
        curr = int(abs(curr*temp)/math.gcd(curr, temp)) #Continuously find the lcm between the 2 largest numbers
    return curr