NZMATH  1.2.0 About: NZMATH is a Python based number theory oriented calculation system.   Fossies Dox: NZMATH-1.2.0.tar.gz  ("inofficial" and yet experimental doxygen-generated source code documentation)
misc.py
Go to the documentation of this file.
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
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()
nzmath.factor.misc.FactoredInteger.divisors
def divisors(self)
Definition: misc.py:173
nzmath.bigrange.range
def range(start, stop=None, step=None)
Definition: bigrange.py:19
nzmath.factor.misc.FactoredInteger.__eq__
def __eq__(self, other)
Definition: misc.py:104
nzmath.factor.misc.FactoredInteger.from_partial_factorization
def from_partial_factorization(cls, integer, partial)
Definition: misc.py:61
nzmath.factor.misc.FactoredInteger.__str__
def __str__(self)
Definition: misc.py:101
nzmath.factor.misc.FactoredInteger.__pos__
def __pos__(self)
Definition: misc.py:98
nzmath.factor.misc.FactoredInteger.exact_division
def exact_division(self, other)
Definition: misc.py:136
nzmath.gcd
Definition: gcd.py:1
nzmath.factor.misc.primePowerTest
def primePowerTest(n)
Definition: misc.py:11
nzmath.factor.misc.FactoredInteger.integer
integer
Definition: misc.py:54
nzmath.factor.misc.FactoredInteger.__init__
def __init__(self, integer, factors=None)
Definition: misc.py:46
nzmath.factor.misc.FactoredInteger.__mod__
def __mod__(self, other)
Definition: misc.py:121
nzmath.factor.misc.FactoredInteger.__long__
def __long__(self)
Definition: misc.py:113
nzmath.factor.misc.FactoredInteger.factors
factors
Definition: misc.py:56
nzmath.factor.misc.FactoredInteger.__iter__
def __iter__(self)
Definition: misc.py:73
nzmath.factor.misc.FactoredInteger
Definition: misc.py:42
nzmath.factor.misc.FactoredInteger.__hash__
def __hash__(self)
Definition: misc.py:107
nzmath.factor.misc.FactoredInteger.proper_divisors
def proper_divisors(self)
Definition: misc.py:184
nzmath.factor.misc.FactoredInteger.__ne__
def __ne__(self, other)
Definition: misc.py:110
nzmath.arith1
Definition: arith1.py:1
nzmath.prime
Definition: prime.py:1
nzmath.factor.misc.FactoredInteger.square_part
def square_part(self, asfactored=False)
Definition: misc.py:196
nzmath.factor.misc.FactoredInteger.is_divisible_by
def is_divisible_by(self, other)
Definition: misc.py:127
nzmath.factor.misc.FactoredInteger.__mul__
def __mul__(self, other)
Definition: misc.py:79
nzmath.factor.misc.FactoredInteger.__pow__
def __pow__(self, other)
Definition: misc.py:91
nzmath.factor.methods
Definition: methods.py:1
nzmath.factor.misc.FactoredInteger.squarefree_part
def squarefree_part(self, asfactored=False)
Definition: misc.py:212
nzmath.factor.misc.FactoredInteger.copy
def copy(self)
Definition: misc.py:118
nzmath.factor.misc.FactoredInteger.prime_divisors
def prime_divisors(self)
Definition: misc.py:190