## "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