moved files to higher directory after split to new repositoryHEADtrunk

1 files changed, 145 insertions, 0 deletions

diff --git a/common.py b/common.py
new file mode 100644
index 0000000..9ca2d9b
--- /dev/null
+++ b/common.py
@@ -0,0 +1,145 @@
+import math
+
+class sieve:
+	def __init__(self, limit):
+		self.limit = limit
+		self.number_list = [False] + [True]*(self.limit-1)
+		self.list_len = len(self.number_list)
+
+	def next_prime(self, i):
+		x = i+1
+		while(x <= self.list_len):
+			if self.number_list[x-1] == True:
+				break
+			x += 1
+		return x
+
+	def primes(self):
+		i = 2
+		while(i*i <= self.list_len):
+			x = i*i
+			while(x <= self.list_len):
+				self.number_list[x-1] = False
+				x += i
+			i = self.next_prime(i)
+
+		primeset = set()
+		for i in xrange(1, self.limit+1):
+			if self.number_list[i-1]:
+				primeset.add(i)
+		return primeset
+
+class pandigital:
+	# create n-digit pandigital numbers
+	def __init__(self, start, end):
+		self.digits = set()
+		for d in range(start, end+1):
+			self.digits.add(d)
+	
+	# return set of digits that are not in x
+	def missing(self, x):
+		d = set()
+		while x > 0:
+			d.add(x % 10)
+			x /= 10
+		return self.digits - d
+
+	def numbers(self, r):
+		result = set()
+		result |= self.digits
+		for i in range(2, r):
+			new = set()
+			for x in result:
+				for y in self.missing(x):
+					new.add(x*10 + y)
+			result |= new
+		return result
+
+def ggt(a, b): # Stein's algorithm
+	k = 0
+	t = 0
+	while a&1==0 and b&1==0:
+		a = a>>1
+		b = b>>1
+		k += 1
+	if a&1==1:
+		t = -b
+	else:
+		t = a
+	while t != 0:
+		while t&1==0:
+			t = t>>1
+		if t>0:
+			a = t
+		else:
+			b = -t
+		t = a - b
+	return a*(1<<k)
+
+def composite(n): # check if n = c^b
+	primes = sieve(int(math.sqrt(n))+1).primes()
+	for c in primes:
+		number = c
+		while number < n:
+			number *= c
+		if number == n:
+			return True
+	return False
+
+def order(n, r):
+	res = n % r
+	k = 1
+	while res != 1:
+		res = (res * n) % r
+		k += 1
+	return k
+
+def phi(x):
+	primes = sieve(x+1).primes()
+	product = x
+	for p in primes:
+		if x % p != 0:
+			continue
+		product *= (1 - 1.0/p)
+	return int(product)
+		
+
+def prime_test(n): # aks test
+	if composite(n):
+		return False
+
+	logn = math.log(n, 2)
+	o = 0
+	r = 0
+	while o <= logn:
+		r += 1
+		o = order(n, r)
+
+	a = 1
+	while a <= r:
+		g = ggt(a, n)
+		if g < n and g > 1:
+			return False
+		a += 1
+
+	if n <= r*r:
+		return True
+
+	#for a in xrange(1, math.floor(math.sqrt(phi(r))*logn)):
+	#	# TODO if math.pow(x+a, n) != 
+	
+	return True
+
+def permutation(p, q): # checks whether p is a permuation of q
+	digits_p = [0]*10
+	digits_q = [0]*10
+	while p > 0:
+		digit = p % 10
+		digits_p[digit] += 1
+		p /= 10
+	while q > 0:
+		digit = q % 10
+		digits_q[digit] += 1
+		q /= 10
+	return digits_p == digits_q
+