Home | Trees | Index | Help |
|
---|
Package sage :: Package rings :: Module arith |
|
Function Summary | |
---|---|
The binomial coefficient 'n choose m', where m and n are integers. | |
Use the Chinese Remainder Theorem to find some integer x such that x=a (mod m) and x=b (mod n). | |
CRT_list(v,
moduli)
| |
Returns a list of all positive integer divisors of the nonzero integer n. | |
Return a list of the primes <= n. | |
Euler phi function of the integer n. | |
Returns the factorization of the integer n as a sorted list of tuples (p,e). | |
int |
Compute the factorial of n. |
Return the Farey sequence associated to the floating point number v. | |
The greatest commond divisor of a and b. | |
The greatest commond divisor of a and b. | |
This function should behave exactly the same as GCD, but is implemented in pure python. | |
The m-th power of a, where m is a non-negative integer and a is a Python object on which multiplication is defined. | |
The inverse of the integer a modulo the integer m. | |
Returns True if x is a PROVEN prime number, and False otherwise. | |
Returns whether or not n is square, and if n is a square also returns the square root. | |
Returns True if and only if n is not divisible by the square of an integer > 1. | |
kronecker(a,
b)
| |
The least common multiple of a and b. | |
The least common multiple of a and b. | |
The maximum of a list of objects, on which a binary max operation is defined. | |
The minimum of a list of objects, on which a binary min operation is defined. | |
Returns the value of the Moebius function of abs(n), where n is an integer. | |
Maximal Quotient Rational Reconstruction. | |
The next prime greater than the integer n. | |
The odd part of the integer n. | |
Generate the partitions of an integer. | |
The m-th power of a modulo the integer n. | |
List of all primes between start and stop-1, inclusive. | |
The largest prime < n. | |
The prime divisors of the integer n, sorted in increasing order. | |
List of all primes between start and stop-1, inclusive. | |
Returns the prime-to-m part of n, i.e., the largest divisor of n that is coprime to m. | |
Returns an iterator over all primes between start and stop-1, inclusive. | |
This function tries to compute a pair (x,y), where x/y is a rational number is lowest terms such that reduction of x/y modulo m is equal to a and the absolute values of x and y are both <= sqrt(m/2). | |
Return the sum of the k-th powers of the divisors of n. | |
Returns the square root of x compute to precision prec. | |
Returns the result of dividing n by the largest square of an integer that divides n. | |
Return the smallest prime divisor <= bound of the positive integer n, or n if there is no such prime. | |
The exact power of p>0 that divides the integer m. | |
Returns triple of integers (g,s,t) such that g = s*a+t*b = GCD(a,b). | |
Returns triple (g,p,q) such that g = p*a+b*q = GCD(a,b). |
Function Details |
---|
binom(n, m)The binomial coefficient 'n choose m', where m and n are integers. If m<0 then this function returns 0. INPUT:n -- int m -- intOUTPUT: intEXAMPLES: >>> binom(5,2) 10 >>> binom(2,0) 1 >>> binom(3,-1) 0 >>> binom(20,10) 184756 |
CRT(a, b=0, m=1, n=1)Use the Chinese Remainder Theorem to find some integer x such that x=a (mod m) and x=b (mod n). Note that x is only well-defined modulo m*n.>>> CRT(2, 1, 3, 5) -4 >>> CRT(13,20,100,301) -2087 |
divisors(n)Returns a list of all positive integer divisors of the nonzero integer n. EXAMPLES:>>> divisors(-3) [1, 3] >>> divisors(6) [1, 2, 3, 6] >>> divisors(28) [1, 2, 4, 7, 14, 28] >>> divisors(2**5) [1, 2, 4, 8, 16, 32] >>> divisors(100) [1, 2, 4, 5, 10, 20, 25, 50, 100] >>> divisors(1) [1] >>> divisors(0) Traceback (most recent call last): ... ValueError: n must be nonzero >>> divisors(2**3*3**2*17) [1, 2, 3, 4, 6, 8, 9, 12, 17, 18, 24, 34, 36, 51, 68, 72, 102, 136, 153, 204, 306, 408, 612, 1224] |
eratosthenes(n)Return a list of the primes <= n. |
eulerphi(n)Euler phi function of the integer n. We defined this to be the number of positive integers <= n that are relatively prime to n. Thus if n<=0 then eulerphi(n) is defined and equals 0.>>> eulerphi(1) 1 >>> eulerphi(2) 1 >>> eulerphi(3) 2 >>> eulerphi(12) 4 >>> eulerphi(37) 36Notice that eulerphi is defined to be 0 on negative numbers and 0. >>> eulerphi(-1) 0 >>> eulerphi(0) 0 |
factor(n, proof=True, int_=False)Returns the factorization of the integer n as a sorted list of tuples (p,e). INPUT: n -- an integer OUTPUT: list -- factorization of n EXAMPLES: >>> factor(500) [(2, 2), (5, 3)] >>> factor(-20) [(2, 2), (5, 1)] >>> factor(0) [] >>> factor(1) [] >>> factor(-1) [] >>> factor(2004) [(2, 2), (3, 1), (167, 1)] |
factorial(n)Compute the factorial of n.>>> factorial(0) 1 >>> factorial(4) 24 >>> factorial(10) 3628800
|
farey(v, lim)Return the Farey sequence associated to the floating point number v. INPUT: v -- float (automatically converted to a float) lim -- maximum denominator. OUTPUT: Results are (numerator, denominator); (1, 0) is"infinity". AUTHOR: Scott David Daniels, Python Cookbook, 2nd Ed., Recipe 18.13 |
gcd(a, b=0)The greatest commond divisor of a and b.>>> GCD(97,100) 1 >>> GCD(97 * 10**15, 19**20 * 97**2) 97 |
GCD(a, b=0)The greatest commond divisor of a and b.>>> GCD(97,100) 1 >>> GCD(97 * 10**15, 19**20 * 97**2) 97 |
GCD_python(a, b=0)This function should behave exactly the same as GCD, but is implemented in pure python. |
generic_power(a, m)The m-th power of a, where m is a non-negative integer and a is a Python object on which multiplication is defined. The exponentiation is done using the standard binary powering algorithm. EXAMPLES:>>> generic_power(2,5) 32 >>> generic_power(2.5,4) 39.0625 >>> generic_power(0,0) 1 >>> generic_power(2,-3) Traceback (most recent call last): ... ArithmeticError: 2 cannot be raised to the negative power -3 |
inverse_mod(a, m)The inverse of the integer a modulo the integer m. >>> inverse_mod(7,1) 0 >>> inverse_mod(5,14) 3 >>> inverse_mod(3,-5) 2 |
is_prime(n, flag=0)Returns True if x is a PROVEN prime number, and False otherwise. INPUT: flag -- int 0 (default): use a combination of algorithms. 1: certify primality using the Pocklington-Lehmer Test. 2: certify primality using the APRCL test. OUTPUT: bool -- True or False EXAMPLES:: >>> is_prime(389) True >>> is_prime(2000) False >>> is_prime(2) True >>> is_prime(-1) False >>> factor(-6) [(2, 1), (3, 1)] >>> is_prime(1) False >>> is_prime(-2) False IMPLEMENTATION: Calls the PARI isprime function. |
is_square(n, root=False)Returns whether or not n is square, and if n is a square also returns the square root. If n is not square, also returns None. INPUT: n -- an integer root -- whether or not to also return a square root (default: False) OUTPUT: bool -- whether or not a square object -- |
is_squarefree(n)Returns True if and only if n is not divisible by the square of an integer > 1. |
lcm(a, b=None)The least common multiple of a and b.>>> LCM(97,100) 9700 >>> LCM(0,2) 0 >>> LCM(-3,-5) 15 |
LCM(a, b=None)The least common multiple of a and b.>>> LCM(97,100) 9700 >>> LCM(0,2) 0 >>> LCM(-3,-5) 15 |
Max(x)The maximum of a list of objects, on which a binary max operation is defined. |
Min(x)The minimum of a list of objects, on which a binary min operation is defined. |
moebius(n)Returns the value of the Moebius function of abs(n), where n is an integer. DEFINITION: mu(n) is 0 if n is not square free, and otherwise equals (-1)^r, where n has r distinct prime factors. INPUT: n -- an integer OUTPUT: 0, 1, or -1 EXAMPLES: >>> moebius(-5) -1 >>> moebius(9) 0 >>> moebius(12) 0 >>> moebius(-35) 1 >>> moebius(-1) 1 >>> moebius(7) -1 |
mqrr_rational_reconstruction(u, m, T)Maximal Quotient Rational Reconstruction. Input: u, m, and T are integers and m > u>=0, T>0. Output: Either integer n,d such that d>0, gcd(n,d)=1, n/d=u (mod m), and T*abs(n)*d < m, or None. Reference: Monagan, Maximal Quotient Rational Reconstruction: An Almost Optimal Algorithm for Rational Reconstruction (page 11) This algorithm is probabilistic. |
next_prime(n, proof=True)The next prime greater than the integer n. If n is prime, then this function does not return n, but the next prime after n. If the optional argument proof is false (the default), this function only returns a pseudo-prime, as defined by the PARI nextprime function. INPUT: n -- integer proof -- bool (default: True) EXAMPLES: >>> next_prime(-100) 2 Notice that the next_prime(5) is not 5 but 7. >>> next_prime(5) 7 >>> next_prime(2004) 2011 |
odd_part(n)The odd part of the integer n. This is n / 2^v, where v = valuation(n,2). |
partitions(n)Generate the partitions of an integer. INPUT: n -- int EXAMPLES: >> partitions(3) <generator object at 0xab3b3eac> >>> list(partitions(3)) [(1, 1, 1), (1, 2), (3,)] AUTHOR: David Eppstein, Jan Van lent, George Yoshida; Python Cookbook 2, Recipe 19.16. |
power_mod(a, m, n)The m-th power of a modulo the integer n. >>> power_mod(0,0,5) 1 >>> power_mod(2,390,391) 285 >>> power_mod(2,-1,7) 4 |
prange(start, stop=None)List of all primes between start and stop-1, inclusive. If the second argument is omitted, returns the primes up to the first argument. Use this function when both start and stop are not too large, since in all cases this function makes a table of primes up to stop. If both are large, use the primes iterator function instead. EXAMPLES:>>> prime_range(0,10) [2, 3, 5, 7] >>> prime_range(2000,2020) [2003, 2011, 2017] >>> prime_range(2,2) [] >>> prime_range(2,3) [2] >>> prime_range(10) [2, 3, 5, 7] |
prev_prime(n)The largest prime < n. The result is provably correct. If n <= 2, this function returns -p, where p is prime and -p < n and no larger negative of a prime has this property. EXAMPLES:>>> prev_prime(10) 7 >>> prev_prime(7) 5 >>> prev_prime(8) 7 >>> prev_prime(7) 5 >>> prev_prime(5) 3 >>> prev_prime(3) 2 >>> prev_prime(2) -2 >>> prev_prime(1) -2 >>> prev_prime(-20) -23 |
prime_divisors(n)The prime divisors of the integer n, sorted in increasing order. If n is negative, we do *not* include -1 among the prime divisors, since -1 is not a prime number.>>> prime_divisors(1) [] >>> prime_divisors(100) [2, 5] >>> prime_divisors(-100) [2, 5] >>> prime_divisors(2004) [2, 3, 167] |
prime_range(start, stop=None)List of all primes between start and stop-1, inclusive. If the second argument is omitted, returns the primes up to the first argument. Use this function when both start and stop are not too large, since in all cases this function makes a table of primes up to stop. If both are large, use the primes iterator function instead. EXAMPLES:>>> prime_range(0,10) [2, 3, 5, 7] >>> prime_range(2000,2020) [2003, 2011, 2017] >>> prime_range(2,2) [] >>> prime_range(2,3) [2] >>> prime_range(10) [2, 3, 5, 7] |
prime_to_m_part(n, m)Returns the prime-to-m part of n, i.e., the largest divisor of n that is coprime to m. INPUT: n -- int (nonzero) m -- int OUTPUT: int |
primes(start, stop=None)Returns an iterator over all primes between start and stop-1, inclusive. This is much slower than prime_range, but potentially uses less memory. This command is like the xrange command, except it only iterates over primes. In some cases it is better to use primes than prime_range, because primes does not build a list of all primes in the range in memory all at once. However it is much slower since it simply calls the next_prime function repeatedly. EXAMPLES:>>> from arith import * >>> for p in primes(10): ... print p ... 2 3 5 7 >>> for p in primes(5,10): ... print p ... 5 7 >>> list(primes(10000000000, 10000000100)) [10000000019L, 10000000033L, 10000000061L, 10000000069L, 10000000097L] |
rational_reconstruction(a, m)This function tries to compute a pair (x,y), where x/y is a rational number is lowest terms such that reduction of x/y modulo m is equal to a and the absolute values of x and y are both <= sqrt(m/2). If such a pair exists, that pair is unique and this function returns it. If no such pair exists, this function return the pair (0,0). The efficient algorithm for computing rational reconstruction is very similar to the extended Euclidean algorithm. For more details, see Knuth, Vol 2, 3rd ed, pages 656-657. EXAMPLES:>>> m = 100000 >>> (119*inverse_mod(53,m))%m 11323 >>> rational_reconstruction(11323,m) (119, 53) |
sigma(k, n)Return the sum of the k-th powers of the divisors of n. |
sqrt(x, prec=0)Returns the square root of x compute to precision prec. The precision is the real precision of the PARI system. EXAMPLES: |
squarefree_part(n)Returns the result of dividing n by the largest square of an integer that divides n.>>> squarefree_part(17*37*37) 17 >>> squarefree_part(-17*32) -34 >>> squarefree_part(1) 1 >>> squarefree_part(-2) -2 >>> squarefree_part(-4) -1 >>> |
trial_division(n, bound=None)Return the smallest prime divisor <= bound of the positive integer n, or n if there is no such prime. If the optional argument bound is omitted, then bound=n. Input: n -- a positive integer bound - (optional) a positive integer Output: int -- a prime p<=bound that divides n, or n if there is no such prime. Examples: >>> trial_division(15) 3 >>> trial_division(91) 7 >>> trial_division(11) 11 >>> trial_division(387833, 300) 387833 >>> # 300 is not big enough to split off a >>> # factor, but 400 is. >>> trial_division(387833, 400) 389 |
valuation(m, p)The exact power of p>0 that divides the integer m. We do not require that p be prime, and if m is 0, then this function returns rings.infinity. EXAMPLES:>>> valuation(512,2) 9 >>> valuation(1,2) 0Valuation of 0 is defined, but valuation with respect to 0 is not: >>> valuation(0,7) Infinity >>> valuation(3,0) Traceback (most recent call last): ... ValueError: valuation at 0 not definedHere are some other example: >>> valuation(100,10) 2 >>> valuation(200,10) 2 >>> valuation(243,3) 5 >>> valuation(243*10007,3) 5 >>> valuation(243*10007,10007) 1 |
XGCD(a, b)Returns triple of integers (g,s,t) such that g = s*a+t*b = GCD(a,b).>>> XGCD(56, 44) (4, 4, -5) >>> 4*56 + (-5)*44 4 |
XGCD_python(a, b)Returns triple (g,p,q) such that g = p*a+b*q = GCD(a,b). This function should behave exactly the same as XGCD, but is implemented in pure python. |
Home | Trees | Index | Help |
|
---|
Generated by Epydoc 2.1 on Mon Jun 20 15:43:22 2005 | http://epydoc.sf.net |