From c0d760d809227431347a55207719d0906fe64402 Mon Sep 17 00:00:00 2001 From: Peter Schaefer Date: Tue, 5 Jun 2012 20:15:04 +0200 Subject: [PATCH] [py] euklid euklid_tex gcd lcm phi ordm --- UE/lib.py | 33 +++++++++++++++++++++++---------- 1 file changed, 23 insertions(+), 10 deletions(-) diff --git a/UE/lib.py b/UE/lib.py index a98984a..50d65c9 100644 --- a/UE/lib.py +++ b/UE/lib.py @@ -6,15 +6,13 @@ def summandial(m,base=1): return m*(m+base)/(2*base) # Gibt die naechst kleine Fib zu max zurueck -def fib(m): - a,b = 1,2 +def fib(m,a=1,b=2): while b < m: a,b = b,a+b return a # Gibt die Liste aller Fib zur naechst kleineren Fib von max zurueck -def fibV(m): - a = [1, 2] +def fibV(m,a=[1,2]): i = 1; while a[i] < m: a.append(a[i] + a[i-1]) @@ -107,7 +105,7 @@ def divisors(num): return sum(ebinomial(map(lambda x:test[x],test.keys()))[1:])+1 -#Euklid +#erweiterter Euklid def euklid(a,b): if a < b: tmp = a @@ -115,14 +113,15 @@ def euklid(a,b): b = tmp x = [1, 0] y = [0, 1] - q = int(a / b) + q = a / b while a%b: [a ,b] = [b,a-q*b] x = [x[1],x[0]-q*x[1]] y = [y[1],y[0]-q*y[1]] - q = int(a/b) + q = a/b return [b,x[1],y[1]] +#erweiterter Euklid mit TeX ausgabe def euklid_tex(a,b): if a < b: tmp = a @@ -150,8 +149,22 @@ def euklid_tex(a,b): print "\\end{array}", return [b,x[1],y[1]] +# groesster gemeinsamer Teiler def gcd(a,b): return euklid(a,b)[0] - -#euklid_tex(2124,1764) - \ No newline at end of file + +# kleinstes gemeinsames Vielfaches +def lcm(a,b): + return abs(a*b) / gcd(a,b) + +#eulersche phi-Funktion +def phi(n): + return n*reduce(lambda x,p:x*(1-1./p), factorD(n).keys(), 1) + +def ordm(a,m): + e = 1 + ae = a + while ae%m!=1: + ae=ae*a + e = e+1 + return e -- 2.47.3