Spaces:
Sleeping
Sleeping
| from itertools import chain, combinations | |
| from sympy.external.gmpy import gcd | |
| from sympy.ntheory.factor_ import factorint | |
| from sympy.utilities.misc import as_int | |
| def _is_nilpotent_number(factors: dict) -> bool: | |
| """ Check whether `n` is a nilpotent number. | |
| Note that ``factors`` is a prime factorization of `n`. | |
| This is a low-level helper for ``is_nilpotent_number``, for internal use. | |
| """ | |
| for p in factors.keys(): | |
| for q, e in factors.items(): | |
| # We want to calculate | |
| # any(pow(q, k, p) == 1 for k in range(1, e + 1)) | |
| m = 1 | |
| for _ in range(e): | |
| m = m*q % p | |
| if m == 1: | |
| return False | |
| return True | |
| def is_nilpotent_number(n) -> bool: | |
| """ | |
| Check whether `n` is a nilpotent number. A number `n` is said to be | |
| nilpotent if and only if every finite group of order `n` is nilpotent. | |
| For more information see [1]_. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.group_numbers import is_nilpotent_number | |
| >>> from sympy import randprime | |
| >>> is_nilpotent_number(21) | |
| False | |
| >>> is_nilpotent_number(randprime(1, 30)**12) | |
| True | |
| References | |
| ========== | |
| .. [1] Pakianathan, J., Shankar, K., Nilpotent Numbers, | |
| The American Mathematical Monthly, 107(7), 631-634. | |
| .. [2] https://oeis.org/A056867 | |
| """ | |
| n = as_int(n) | |
| if n <= 0: | |
| raise ValueError("n must be a positive integer, not %i" % n) | |
| return _is_nilpotent_number(factorint(n)) | |
| def is_abelian_number(n) -> bool: | |
| """ | |
| Check whether `n` is an abelian number. A number `n` is said to be abelian | |
| if and only if every finite group of order `n` is abelian. For more | |
| information see [1]_. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.group_numbers import is_abelian_number | |
| >>> from sympy import randprime | |
| >>> is_abelian_number(4) | |
| True | |
| >>> is_abelian_number(randprime(1, 2000)**2) | |
| True | |
| >>> is_abelian_number(60) | |
| False | |
| References | |
| ========== | |
| .. [1] Pakianathan, J., Shankar, K., Nilpotent Numbers, | |
| The American Mathematical Monthly, 107(7), 631-634. | |
| .. [2] https://oeis.org/A051532 | |
| """ | |
| n = as_int(n) | |
| if n <= 0: | |
| raise ValueError("n must be a positive integer, not %i" % n) | |
| factors = factorint(n) | |
| return all(e < 3 for e in factors.values()) and _is_nilpotent_number(factors) | |
| def is_cyclic_number(n) -> bool: | |
| """ | |
| Check whether `n` is a cyclic number. A number `n` is said to be cyclic | |
| if and only if every finite group of order `n` is cyclic. For more | |
| information see [1]_. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.group_numbers import is_cyclic_number | |
| >>> from sympy import randprime | |
| >>> is_cyclic_number(15) | |
| True | |
| >>> is_cyclic_number(randprime(1, 2000)**2) | |
| False | |
| >>> is_cyclic_number(4) | |
| False | |
| References | |
| ========== | |
| .. [1] Pakianathan, J., Shankar, K., Nilpotent Numbers, | |
| The American Mathematical Monthly, 107(7), 631-634. | |
| .. [2] https://oeis.org/A003277 | |
| """ | |
| n = as_int(n) | |
| if n <= 0: | |
| raise ValueError("n must be a positive integer, not %i" % n) | |
| factors = factorint(n) | |
| return all(e == 1 for e in factors.values()) and _is_nilpotent_number(factors) | |
| def _holder_formula(prime_factors): | |
| r""" Number of groups of order `n`. | |
| where `n` is squarefree and its prime factors are ``prime_factors``. | |
| i.e., ``n == math.prod(prime_factors)`` | |
| Explanation | |
| =========== | |
| When `n` is squarefree, the number of groups of order `n` is expressed by | |
| .. math :: | |
| \sum_{d \mid n} \prod_p \frac{p^{c(p, d)} - 1}{p - 1} | |
| where `n=de`, `p` is the prime factor of `e`, | |
| and `c(p, d)` is the number of prime factors `q` of `d` such that `q \equiv 1 \pmod{p}` [2]_. | |
| The formula is elegant, but can be improved when implemented as an algorithm. | |
| Since `n` is assumed to be squarefree, the divisor `d` of `n` can be identified with the power set of prime factors. | |
| We let `N` be the set of prime factors of `n`. | |
| `F = \{p \in N : \forall q \in N, q \not\equiv 1 \pmod{p} \}, M = N \setminus F`, we have the following. | |
| .. math :: | |
| \sum_{d \in 2^{M}} \prod_{p \in M \setminus d} \frac{p^{c(p, F \cup d)} - 1}{p - 1} | |
| Practically, many prime factors are expected to be members of `F`, thus reducing computation time. | |
| Parameters | |
| ========== | |
| prime_factors : set | |
| The set of prime factors of ``n``. where `n` is squarefree. | |
| Returns | |
| ======= | |
| int : Number of groups of order ``n`` | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.group_numbers import _holder_formula | |
| >>> _holder_formula({2}) # n = 2 | |
| 1 | |
| >>> _holder_formula({2, 3}) # n = 2*3 = 6 | |
| 2 | |
| See Also | |
| ======== | |
| groups_count | |
| References | |
| ========== | |
| .. [1] Otto Holder, Die Gruppen der Ordnungen p^3, pq^2, pqr, p^4, | |
| Math. Ann. 43 pp. 301-412 (1893). | |
| http://dx.doi.org/10.1007/BF01443651 | |
| .. [2] John H. Conway, Heiko Dietrich and E.A. O'Brien, | |
| Counting groups: gnus, moas and other exotica | |
| The Mathematical Intelligencer 30, 6-15 (2008) | |
| https://doi.org/10.1007/BF02985731 | |
| """ | |
| F = {p for p in prime_factors if all(q % p != 1 for q in prime_factors)} | |
| M = prime_factors - F | |
| s = 0 | |
| powerset = chain.from_iterable(combinations(M, r) for r in range(len(M)+1)) | |
| for ps in powerset: | |
| ps = set(ps) | |
| prod = 1 | |
| for p in M - ps: | |
| c = len([q for q in F | ps if q % p == 1]) | |
| prod *= (p**c - 1) // (p - 1) | |
| if not prod: | |
| break | |
| s += prod | |
| return s | |
| def groups_count(n): | |
| r""" Number of groups of order `n`. | |
| In [1]_, ``gnu(n)`` is given, so we follow this notation here as well. | |
| Parameters | |
| ========== | |
| n : Integer | |
| ``n`` is a positive integer | |
| Returns | |
| ======= | |
| int : ``gnu(n)`` | |
| Raises | |
| ====== | |
| ValueError | |
| Number of groups of order ``n`` is unknown or not implemented. | |
| For example, gnu(`2^{11}`) is not yet known. | |
| On the other hand, gnu(12) is known to be 5, | |
| but this has not yet been implemented in this function. | |
| Examples | |
| ======== | |
| >>> from sympy.combinatorics.group_numbers import groups_count | |
| >>> groups_count(3) # There is only one cyclic group of order 3 | |
| 1 | |
| >>> # There are two groups of order 10: the cyclic group and the dihedral group | |
| >>> groups_count(10) | |
| 2 | |
| See Also | |
| ======== | |
| is_cyclic_number | |
| `n` is cyclic iff gnu(n) = 1 | |
| References | |
| ========== | |
| .. [1] John H. Conway, Heiko Dietrich and E.A. O'Brien, | |
| Counting groups: gnus, moas and other exotica | |
| The Mathematical Intelligencer 30, 6-15 (2008) | |
| https://doi.org/10.1007/BF02985731 | |
| .. [2] https://oeis.org/A000001 | |
| """ | |
| n = as_int(n) | |
| if n <= 0: | |
| raise ValueError("n must be a positive integer, not %i" % n) | |
| factors = factorint(n) | |
| if len(factors) == 1: | |
| (p, e) = list(factors.items())[0] | |
| if p == 2: | |
| A000679 = [1, 1, 2, 5, 14, 51, 267, 2328, 56092, 10494213, 49487367289] | |
| if e < len(A000679): | |
| return A000679[e] | |
| if p == 3: | |
| A090091 = [1, 1, 2, 5, 15, 67, 504, 9310, 1396077, 5937876645] | |
| if e < len(A090091): | |
| return A090091[e] | |
| if e <= 2: # gnu(p) = 1, gnu(p**2) = 2 | |
| return e | |
| if e == 3: # gnu(p**3) = 5 | |
| return 5 | |
| if e == 4: # if p is an odd prime, gnu(p**4) = 15 | |
| return 15 | |
| if e == 5: # if p >= 5, gnu(p**5) is expressed by the following equation | |
| return 61 + 2*p + 2*gcd(p-1, 3) + gcd(p-1, 4) | |
| if e == 6: # if p >= 6, gnu(p**6) is expressed by the following equation | |
| return 3*p**2 + 39*p + 344 +\ | |
| 24*gcd(p-1, 3) + 11*gcd(p-1, 4) + 2*gcd(p-1, 5) | |
| if e == 7: # if p >= 7, gnu(p**7) is expressed by the following equation | |
| if p == 5: | |
| return 34297 | |
| return 3*p**5 + 12*p**4 + 44*p**3 + 170*p**2 + 707*p + 2455 +\ | |
| (4*p**2 + 44*p + 291)*gcd(p-1, 3) + (p**2 + 19*p + 135)*gcd(p-1, 4) + \ | |
| (3*p + 31)*gcd(p-1, 5) + 4*gcd(p-1, 7) + 5*gcd(p-1, 8) + gcd(p-1, 9) | |
| if any(e > 1 for e in factors.values()): # n is not squarefree | |
| # some known values for small n that have more than 1 factor and are not square free (https://oeis.org/A000001) | |
| small = {12: 5, 18: 5, 20: 5, 24: 15, 28: 4, 36: 14, 40: 14, 44: 4, 45: 2, 48: 52, | |
| 50: 5, 52: 5, 54: 15, 56: 13, 60: 13, 63: 4, 68: 5, 72: 50, 75: 3, 76: 4, | |
| 80: 52, 84: 15, 88: 12, 90: 10, 92: 4} | |
| if n in small: | |
| return small[n] | |
| raise ValueError("Number of groups of order n is unknown or not implemented") | |
| if len(factors) == 2: # n is squarefree semiprime | |
| p, q = list(factors.keys()) | |
| if p > q: | |
| p, q = q, p | |
| return 2 if q % p == 1 else 1 | |
| return _holder_formula(set(factors.keys())) | |