"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()