"Fossies" - the Fresh Open Source Software Archive

Member "NZMATH-1.2.0/nzmath/squarefree.py" (19 Nov 2012, 7604 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 "squarefree.py" see the Fossies "Dox" file reference documentation.

    1 """
    2 Squarefreeness tests.
    3 
    4 Definition:
    5   n: squarefree <=> there is no p whose square divides n.
    6 
    7 Examples:
    8   - 0 is non-squarefree because any square of prime can divide 0.
    9   - 1 is squarefree because there is no prime dividing 1.
   10   - 2, 3, 5, and any other primes are squarefree.
   11   - 4, 8, 9, 12, 16 are non-squarefree composites.
   12   - 6, 10, 14, 15, 21 are squarefree composites.
   13 """
   14 
   15 import math
   16 import nzmath.arith1 as arith1
   17 import nzmath.bigrange as bigrange
   18 import nzmath.prime as prime
   19 import nzmath.rational as rational
   20 import nzmath.factor.methods as factor_methods
   21 import nzmath.factor.misc as factor_misc
   22 
   23 
   24 class Undetermined (Exception):
   25     """
   26     Undetermined state of calculation.
   27     """
   28 
   29 
   30 def lenstra(n):
   31     """
   32     If return value is True, n is squarefree.  Otherwise, the
   33     squarefreeness is still unknown and Undetermined is raised.
   34 
   35     The condition is so strong that it seems n is a prime or a
   36     Carmichael number.
   37 
   38     pre-condition: n & 1
   39     reference: H.W.Lenstra 1973 ---
   40     """
   41     n = int(n) # see sf bug #1826712
   42     predn = n - 1
   43     bound = int(math.log(n)**2 + 1)
   44     for i in range(2, bound):
   45         if pow(i, predn, n) != 1:
   46             raise Undetermined("Lenstra's method can't determine squarefreeness")
   47     return True
   48 
   49 
   50 def trial_division(n):
   51     """
   52     Test whether n is squarefree or not.
   53 
   54     The method is a kind of trial division.
   55     """
   56     try:
   57         return trivial_test(n)
   58     except Undetermined:
   59         pass
   60 
   61     for p in prime.generator():
   62         if not (n % (p*p)):
   63             # found a square factor
   64             return False
   65         elif not (n % p):
   66             # found a non-square factor
   67             n //= p
   68             try:
   69                 return trivial_test(n)
   70             except Undetermined:
   71                 pass
   72         if p*p*p > n:
   73             break
   74     # At the end of the loop:
   75     #   n doesn't have any factor less than its cubic root.
   76     #   n is not a prime nor a perfect square number.
   77     # The factor must be two primes p and q such that p < sqrt(n) < q.
   78     return True
   79 
   80 
   81 def trivial_test(n):
   82     """
   83     Test whether n is squarefree or not.
   84 
   85     This method do anything but factorization.
   86     """
   87     if n == 1 or n == 2:
   88         return True
   89     if arith1.issquare(n):
   90         return False
   91     if n & 1:
   92         return lenstra(n)
   93     elif not (n & 3):
   94         return False
   95     raise Undetermined("trivial test can't determine squarefreeness")
   96 
   97 
   98 def viafactor(n):
   99     """
  100     Test whether n is squarefree or not.
  101 
  102     It is obvious that if one knows the prime factorization of the number,
  103     he/she can tell whether the number is squarefree or not.
  104     """
  105     for p, e in factor_misc.FactoredInteger(n):
  106         if e >= 2:
  107             return False
  108     return True
  109 
  110 
  111 # ternary logic versions
  112 #
  113 # The third logical value means "uncertain" or "proof unknown".
  114 # We designate None to this value.  It lets "unknown" status
  115 # be, at least, not true.
  116 # There are nothing corresponding to boolean logic operators.
  117 # They are out of scope of this module.
  118 
  119 def lenstra_ternary(n):
  120     """
  121     Test the squarefreeness of n.
  122     The return value is one of the ternary logical constants.
  123     If return value is TRUE, n is squarefree.  Otherwise, the
  124     squarefreeness is still unknown and UNKNOWN is returned.
  125 
  126     The condition is so strong that it seems n is a prime or a
  127     Carmichael number.
  128 
  129     pre-condition: n & 1
  130     reference: H.W.Lenstra 1973 ---
  131     """
  132     n = int(n) # see sf bug #1826712
  133     predn = n - 1
  134     bound = int(math.log(n)**2 + 1)
  135     for i in range(2, bound):
  136         if pow(i, predn, n) != 1:
  137             return None
  138     return True
  139 
  140 
  141 def trivial_test_ternary(n):
  142     """
  143     Test the squarefreeness of n.
  144     The return value is one of the ternary logical constants.
  145 
  146     The method uses a series of trivial tests.
  147     """
  148     if n == 1 or n == 2:
  149         return True
  150     if arith1.issquare(n):
  151         return False
  152     if n & 1:
  153         return lenstra_ternary(n)
  154     elif not (n & 3):
  155         return False
  156     return None
  157 
  158 
  159 def trial_division_ternary(n):
  160     """
  161     Test the squarefreeness of n.
  162     The return value is one of the True or False, not None.
  163 
  164     The method is a kind of trial division.
  165     """
  166     result = trivial_test_ternary(n)
  167     if result is not None:
  168         return result
  169 
  170     for p in prime.generator():
  171         if not (n % (p*p)):
  172             # found a square factor
  173             return False
  174         elif not (n % p):
  175             # found a non-square factor
  176             n //= p
  177             result = trivial_test_ternary(n)
  178             if result is not None:
  179                 return result
  180         if p*p*p > n:
  181             break
  182     # At the end of the loop:
  183     #   n doesn't have any factor less than its cubic root.
  184     #   n is not a prime nor a perfect square number.
  185     # The factor must be two primes p and q such that p < sqrt(n) < q.
  186     return True
  187 
  188 
  189 # Just for symmetry, viafactor_ternary is defined as an alias of viafactor.
  190 viafactor_ternary = viafactor
  191 
  192 
  193 class SquarefreeDecompositionMethod (factor_methods.TrialDivision):
  194     """
  195     Decomposition of an integer into square part and squarefree part.
  196     """
  197     def __init__(self):
  198         factor_methods.TrialDivision.__init__(self)
  199         self.primeseq = None # initialized later
  200 
  201     def generate(self, target, **options):
  202         """
  203         Generate squarefree factors of the target number with their
  204         valuations.  The method may terminate with yielding (1, 1)
  205         to indicate the factorization is incomplete.
  206 
  207         If a keyword option 'strict' is False (default to True),
  208         factorization will stop after the first square factor no
  209         matter whether it is squarefree or not.
  210         """
  211         strict = options.get('strict', True)
  212         options['n'] = target
  213         primeseq = self._parse_seq(options)
  214         for p in primeseq:
  215             if not (target % p):
  216                 e, target = arith1.vp(target, p)
  217                 yield p, e
  218                 if target == 1:
  219                     break
  220                 elif e > 1 and not strict:
  221                     yield 1, 1
  222                     break
  223                 elif trivial_test_ternary(target):
  224                     # the factor remained is squarefree.
  225                     yield target, 1
  226                     break
  227                 q, e = factor_misc.primePowerTest(target)
  228                 if e:
  229                     yield q, e
  230                     break
  231                 sqrt = arith1.issquare(target)
  232                 if sqrt:
  233                     if strict:
  234                         for q, e in self.factor(sqrt, iterator=primeseq):
  235                             yield q, 2 * e
  236                     else:
  237                         yield sqrt, 2
  238                     break
  239             if p ** 3 > target:
  240                 # there are no more square factors of target,
  241                 # thus target is squarefree
  242                 yield target, 1
  243                 break
  244         else:
  245             # primeseq is exhausted but target has not been proven prime
  246             yield 1, 1
  247 
  248     def issquarefree(self, n):
  249         """
  250         Return True if n is squarefree, False otherwise.
  251 
  252         The method uses partial factorization into squarefree parts,
  253         if such partial factorization is possible.  In other cases,
  254         It completely factor n by trial division.
  255         """
  256         if trivial_test_ternary(n):
  257             return True
  258         for s, e in self.generate(n, strict=False):
  259             if e > 1:
  260                 return False
  261         return True
  262 
  263 
  264 viadecomposition = SquarefreeDecompositionMethod().issquarefree