## "Fossies" - the Fresh Open Source Software Archive

### Member "NZMATH-1.2.0/nzmath/factor/misc.py" (19 Nov 2012, 7066 Bytes) of package /linux/misc/old/NZMATH-1.2.0.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Python source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. For more information about "misc.py" see the Fossies "Dox" file reference documentation.

```    1 """
2 misc functions using factorization.
3 """
4
5 import nzmath.gcd as gcd
6 import nzmath.arith1 as arith1
7 import nzmath.prime as prime
8 import nzmath.factor.methods as methods
9
10
11 def primePowerTest(n):
12     """
13     This program using Algo. 1.7.5 in Cohen's book judges whether
14     n is of the form p**k with prime p or not.
15     If it is True, then (p,k) will be returned,
16     otherwise (n,0).
17     """
18     if n & 1:
19         q = n
20         while True:
21             if not prime.primeq(q):
22                 a = 2
23                 while prime.spsp(n, a):
24                     a += 1
25                 d = gcd.gcd(pow(a,q,q) - a, q)
26                 if d == 1 or d == q:
27                     return (n, 0)
28                 q = d
29             else:
30                 p = q
31                 break
32     else:
33         p = 2
34
35     k, q = arith1.vp(n, p)
36     if q == 1:
37         return (p, k)
38     else:
39         return (n, 0)
40
41
42 class FactoredInteger(object):
43     """
44     Integers with factorization information.
45     """
46     def __init__(self, integer, factors=None):
47         """
48         FactoredInteger(integer [, factors])
49
50         If factors is given, it is a dict of type {prime:exponent}
51         and the product of prime**exponent is equal to the integer.
52         Otherwise, factorization is carried out in initialization.
53         """
54         self.integer = long(integer)
55         if factors is None:
56             self.factors = dict(methods.factor(self.integer))
57         else:
58             self.factors = dict(factors)
59
60     @classmethod
61     def from_partial_factorization(cls, integer, partial):
62         """
63         Construct a new FactoredInteger object from partial
64         factorization information given as dict of type
65         {prime:exponent}.
66         """
67         partial_factor = 1
68         for p, e in partial.iteritems():
69             partial_factor *= p**e
70         assert not integer % partial_factor, "wrong factorization"
71         return cls(integer // partial_factor) * cls(partial_factor, partial)
72
73     def __iter__(self):
74         """
75         Default iterator
76         """
77         return self.factors.iteritems()
78
79     def __mul__(self, other):
80         if isinstance(other, FactoredInteger):
81             integer = self.integer * other.integer
82             new_factors = self.factors.copy()
83             for p in other.factors:
84                 new_factors[p] = new_factors.get(p, 0) + other.factors[p]
85             return self.__class__(integer, new_factors)
86         else:
87             return self * FactoredInteger(other)
88
89     __rmul__ = __mul__
90
91     def __pow__(self, other):
92         new_integer = self.integer**other
93         new_factors = {}
94         for p in self.factors:
95             new_factors[p] = self.factors[p] * other
96         return self.__class__(new_integer, new_factors)
97
98     def __pos__(self):
99         return self.copy()
100
101     def __str__(self):
102         return str(self.integer)
103
104     def __eq__(self, other):
105         return self.integer == int(other)
106
107     def __hash__(self):
108         return hash(self.integer)
109
110     def __ne__(self, other):
111         return self.integer != int(other)
112
113     def __long__(self):
114         return self.integer
115
116     __int__ = __long__
117
118     def copy(self):
119         return self.__class__(self.integer, self.factors.copy())
120
121     def __mod__(self, other):
122         # maybe you want self.is_divisible_by(other)
123         if int(other) in self.factors:
124             return 0
125         return self.integer % int(other)
126
127     def is_divisible_by(self, other):
128         """
129         Return True if other divides self.
130         """
131         if int(other) in self.factors:
132             # other is prime and divides
133             return True
134         return not self.integer % int(other)
135
136     def exact_division(self, other):
137         """
138         Divide by a factor.
139         """
140         divisor = int(other)
141         quotient = self.copy()
142         if divisor in quotient.factors:
143             if quotient.factors[divisor] == 1:
144                 del quotient.factors[divisor]
145             else:
146                 quotient.factors[divisor] -= 1
147         elif not isinstance(other, FactoredInteger):
148             dividing = divisor
149             for p, e in self.factors.iteritems():
150                 while not dividing % p:
151                     dividing //= p
152                     if quotient.factors[p] == 1:
153                         del quotient.factors[p]
154                         assert dividing % p, dividing
155                     else:
156                         quotient.factors[p] -= 1
157                 if dividing == 1:
158                     break
159             assert dividing == 1
160         else:
161             for p, e in other.factors.iteritems():
162                 assert p in quotient.factors and quotient.factors[p] >= e
163                 if quotient.factors[p] == e:
164                     del quotient.factors[p]
165                 else:
166                     quotient.factors[p] -= e
167         quotient.integer //= divisor
168         return quotient
169
170     # maybe this is what you want, isn't it?
171     __floordiv__ = exact_division
172
173     def divisors(self):
174         """
175         Return all divisors.
176         """
177         l = [1]
178         for p, e in self.factors.iteritems():
179             for j in range(1, e + 1):
180                 l += [k*pow(p, j) for k in l if k % p]
181         l.sort()
182         return l
183
184     def proper_divisors(self):
185         """
186         Return the proper divisors (divisors of n excluding 1 and n).
187         """
188         return self.divisors()[1:-1]
189
190     def prime_divisors(self):
191         """
192         Return the list of primes that divides the number.
193         """
194         return self.factors.keys()
195
196     def square_part(self, asfactored=False):
197         """
198         Return the largest integer whose square divides the number.
199
200         If an optional argument asfactored is true, then the result is
201         also a FactoredInteger object. (default is False)
202         """
203         result = FactoredInteger(1, {})
204         for d, e in self.factors.iteritems():
205             if e >= 2:
206                 result *= FactoredInteger(d ** (e >> 1), {d:e>>1})
207         if asfactored:
208             return result
209         else:
210             return result.integer
211
212     def squarefree_part(self, asfactored=False):
213         """
214         Return the largest divisor of the number which is squarefree.
215
216         If an optional argument asfactored is true, then the result is
217         also a FactoredInteger object. (default is False)
218         """
219         result = FactoredInteger(1, {})
220         for d, e in self.factors.iteritems():
221             if e & 1:
222                 result *= FactoredInteger(d, {d:1})
223         if asfactored:
224             return result
225         else:
226             return result.integer
227
228
229 # for backward compatibility
230 allDivisors = lambda n: FactoredInteger(n).divisors()
231 primeDivisors = lambda n: FactoredInteger(n).prime_divisors()
232 squarePart = lambda n: FactoredInteger(n).square_part()
```