"Fossies" - the Fresh Open Source Software Archive

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

    1 """
    2 Multiplicative number theoretic functions.
    3 """
    4 
    5 import nzmath.factor.misc as factor_misc
    6 import nzmath.prime as prime
    7 
    8 def euler(n):
    9     """
   10     Euler totient function.
   11     It returns the number of relatively prime numbers to n smaller than n.
   12     """
   13     if n == 1:
   14         return 1
   15     if prime.primeq(n):
   16         return n - 1
   17     t = 1
   18     for p, e in factor_misc.FactoredInteger(n):
   19         if e > 1:
   20             t *= pow(p, e - 1) * (p - 1)
   21         else:
   22             t *= p - 1
   23     return t
   24 
   25 def moebius(n):
   26     """
   27     Moebius function.
   28     It returns:
   29       -1  if n has odd distinct prime factors,
   30        1  if n has even distinct prime factors, or
   31        0  if n has a squared prime factor.
   32     """
   33     if n == 1:
   34         return 1
   35     if prime.primeq(n):
   36         return -1
   37     m = 1
   38     for p, e in factor_misc.FactoredInteger(n):
   39         if e > 1:
   40             return 0
   41         m = -m
   42     return m
   43 
   44 def sigma(m, n):
   45     """
   46     Return the sum of m-th powers of the factors of n.
   47     """
   48     if n == 1:
   49         return 1
   50     if prime.primeq(n):
   51         return 1 + n**m
   52     s = 1
   53     for p, e in factor_misc.FactoredInteger(n):
   54         t = 1
   55         for i in range(1, e + 1):
   56             t += (p**i)**m
   57         s *= t
   58     return s
   59