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