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)
squarefree.py
Go to the documentation of this file.
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
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
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
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
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
nzmath.bigrange.range
def range(start, stop=None, step=None)
Definition: bigrange.py:19
nzmath.squarefree.SquarefreeDecompositionMethod.issquarefree
def issquarefree(self, n)
Definition: squarefree.py:248
nzmath.squarefree.lenstra_ternary
def lenstra_ternary(n)
Definition: squarefree.py:119
nzmath.squarefree.trivial_test_ternary
def trivial_test_ternary(n)
Definition: squarefree.py:141
nzmath.factor.misc
Definition: misc.py:1
nzmath.squarefree.trial_division
def trial_division(n)
Definition: squarefree.py:50
nzmath.squarefree.SquarefreeDecompositionMethod.generate
def generate(self, target, **options)
Definition: squarefree.py:201
nzmath.rational
Definition: rational.py:1
nzmath.squarefree.viafactor
def viafactor(n)
Definition: squarefree.py:98
nzmath.squarefree.Undetermined
Definition: squarefree.py:24
nzmath.squarefree.SquarefreeDecompositionMethod.primeseq
primeseq
Definition: squarefree.py:199
nzmath.squarefree.trial_division_ternary
def trial_division_ternary(n)
Definition: squarefree.py:159
nzmath.squarefree.trivial_test
def trivial_test(n)
Definition: squarefree.py:81
nzmath.arith1
Definition: arith1.py:1
nzmath.prime
Definition: prime.py:1
nzmath.bigrange
Definition: bigrange.py:1
nzmath.factor.methods
Definition: methods.py:1
nzmath.squarefree.lenstra
def lenstra(n)
Definition: squarefree.py:30
nzmath.squarefree.SquarefreeDecompositionMethod.__init__
def __init__(self)
Definition: squarefree.py:197