igorvanloo

def xorProduct(x, y):
    prod = 0
    #Note that 0 ^ x = x, ^ = XOR
    while y != 0:
        if y % 2 == 1:
            #If the first bit of y is a 1, prod = prod ^ x
            prod ^= x
        #Then we shift x one bit to the left, essentially adds a 0 behind x
        x <<= 1
        #And we push y one bit to the right, essentially removes the first bit

igorvanloo

import itertools
from functools import lru_cache

@lru_cache(maxsize = 10**5)
def recursiveGenerate(A):
    values = set()
    
    #If our subset has a single element, then that element is the only constructable number
    if len(A) == 1:
        values.add(A[0])

igorvanloo

class P:
    def __init__(self, value, mask, left, right, operation):
        self.value = value
        self.mask = mask
        self.left = left
        self.right = right
        self.operation = operation
        
        if self.left == None and self.right == None:
            self.expression = str(value)

igorvanloo

import numpy as np
from scipy.optimize import linear_sum_assignment

M = [[  7,  53, 183, 439, 863, 497, 383, 563,  79, 973, 287,  63, 343, 169, 583],
    	[627, 343, 773, 959, 943, 767, 473, 103, 699, 303, 957, 703, 583, 639, 913],
    	[447, 283, 463,  29,  23, 487, 463, 993, 119, 883, 327, 493, 423, 159, 743],
    	[217, 623,   3, 399, 853, 407, 103, 983,  89, 463, 290, 516, 212, 462, 350],
    	[960, 376, 682, 962, 300, 780, 486, 502, 912, 800, 250, 346, 172, 812, 350],
    	[870, 456, 192, 162, 593, 473, 915,  45, 989, 873, 823, 965, 425, 329, 803],
    	[973, 965, 905, 919, 133, 673, 665, 235, 509, 613, 673, 815, 165, 992, 326],

igorvanloo

def kpowerful(k, upper_bound, count = True):
    '''
    Inspired by https://rosettacode.org/wiki/Powerful_numbers#Python
    '''
    def prime_powers(k, upper_bound):
        ub = int(math.pow(upper_bound, 1/k) + .5)
        res = [(1,)]
        for p in list_primes(ub):
            a = [p**k]
            u = upper_bound // a[-1]

igorvanloo

def mobius_k_sieve(n, k):
    isprime = [1]*(n + 1)
    isprime[0] = isprime[1] = 0
    mob = [0] + [1]*(n)
    for p in range(2, n + 1):
        if isprime[p]:
            mob[p] *= -1
            for i in range(2*p, n + 1, p):
                isprime[i] = 0
                mob[i] *= -1

igorvanloo

def join_str(alist):
    temp_list = alist
    return "".join(str(temp_list[y]) for y in range(len(temp_list)))

def compute():
    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    final_list = []
    for a in numbers:
        numbers_b = numbers[:]
        numbers_b.remove(a)

igorvanloo

def fermat_primality_test(n, tests):
    for x in range(tests):
        if pow(2*(x + 2), n - 1, n) != 1:
            return False
    return True

igorvanloo

def miller(n, millerrabin = False, numoftests = 2):
    if n == 1:
        return False
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if not millerrabin:

igorvanloo

def ChineseRemainderTheorem(a1, a2, n1, n2):
    #x = a1 (mod n1)
    #x = a2 (mod n2)
    #We find p = n1^-1 (mod n2), q = n2^-1 (mod n1)
    p ,q = pow(n1, -1, n2), pow(n2, -1, n1)
    #The unique solution to this system is a1*q*n2 + a2*p*n1 % n1*n2
    return (a1*q*n2+ a2*p*n1) % (n1*n2)