Module: sage.rings.arith
Module-level Functions
a, [b=1], [m=1], [n=0]) |
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.
sage: crt(2, 1, 3, 5) -4 sage: crt(13,20,100,301) -2087
moduli) |
Return a list of integers a[i] such that CRT to the given moduli of numbers x[0],...,x[n-1] is a[0]*x0 + ... + a[n-1]*x[n-1].
INPUT: list -- list of integers
v, moduli) |
X, moduli) |
INPUT: X -- list of lists of the same length moduli -- list of len(X) moduli OUTPUT: list -- application of CRT componentwise.
a, [b=0]) |
The greatest commond divisor of a and b.
sage: GCD(97,100) 1 sage: GCD(97*10^15, 19^20*97^2) 97
a, [b=None]) |
The least common multiple of a and b.
sage: LCM(97,100) 9700 sage: LCM(0,2) 0 sage: LCM(-3,-5) 15
x) |
The maximum of a list of objects, on which a binary max operation is defined.
x) |
The minimum of a list of objects, on which a binary min operation is defined.
a, b) |
Returns triple of integers (g,s,t) such that g = s*a+t*b = gcd(a,b).
sage: xgcd(56, 44) (4, 4, -5) sage: 4*56 + (-5)*44 4
v) |
v) |
n, [int_=0], [debug_level=False]) |
n) |
Returns the factorization of the integer n as a sorted list of tuples (p,e).
INPUT: n -- an integer OUTPUT: list -- factorization of n
z, n) |
Return algebraic dependency of degree
satisfied by the
number
.
ALGORITHM: Uses the PARI C-library algdep command.
INPUT: z -- real or $p$-adic number n -- an integer
sage: algdep(1.888888888888888, 1) 9*x - 17 sage: algdep(0.12121212121212,1) 33*x - 4 sage: algdep(sqrt(2),2) x^2 - 2
This example involves a
-adic number.
sage: K = pAdicField(3) sage: a = K(7/19); a 1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 + 2*3^16 + 3^17 + 2*3^19 + O(3^20) sage: algdep(a, 1) 19*x - 7
z, n) |
Return algebraic dependency of degree
satisfied by the
number
.
ALGORITHM: Uses the PARI C-library algdep command.
INPUT: z -- real or $p$-adic number n -- an integer
sage: algdep(1.888888888888888, 1) 9*x - 17 sage: algdep(0.12121212121212,1) 33*x - 4 sage: algdep(sqrt(2),2) x^2 - 2
This example involves a
-adic number.
sage: K = pAdicField(3) sage: a = K(7/19); a 1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 + 2*3^16 + 3^17 + 2*3^19 + O(3^20) sage: algdep(a, 1) 19*x - 7
n, [algorithm=pari]) |
Return the n-th Bernoulli number, as a rational number.
INPUT: n -- an integer algorithm: 'pari' -- (default) use the PARI C library, which is by *far* the fastest. 'gap' -- use GAP 'gp' -- use PARI/GP interpreter 'python' -- use pure Python implementation
sage: bernoulli(12) -691/2730 sage: bernoulli(50) 495057205241079648212477525/66
We illustrate use of some of the alternative algorithms.
sage: bernoulli(12, algorithm='gap') -691/2730 sage: bernoulli(12, algorithm='gp') -691/2730
Note:
If
then algorithm = 'gp' is used instead of
algorithm = 'pari', since the C-library interface to PARI
is limited in memory for individual operations.
Author: David Joyner and William Stein
x, m) |
Return the binomial coefficient
which is defined for
INPUT:: x -- number m -- integer OUTPUT:: number
:
sage: binomial(5,2) 10 sage: binomial(2,0) 1 sage: binomial(3,-1) 0 sage: binomial(20,10) 184756 sage: binomial(RealField()('2.5'), 2) 1.8750000000000000
x, [partial_convergents=False]) |
Returns the continued fraction of x.
sage: continued_fraction(45/17) [2, 1, 1, 1, 5] sage: continued_fraction(sqrt(2)) [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1] sage: continued_fraction(RR(pi), partial_convergents=True) ([3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3], [(3, 1), (22, 7), (333, 106), (355, 113), (103993, 33102), (104348, 33215), (208341, 66317), (312689, 99532), (833719, 265381), (1146408, 364913), (4272943, 1360120), (5419351, 1725033), (80143857, 25510582), (245850922, 78256779)]) sage: continued_fraction(e) Traceback (most recent call last): ... NotImplementedError: computation of continued fraction of e not implemented; try computing continued fraction of RR(e) instead sage: continued_fraction(RR(e)) [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 11] sage: print continued_fraction(RealField(200)(e)) [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1, 16, 1, 1, 18, 1, 1, 20, 1, 1, 22, 1, 1, 24, 1, 1, 26, 1, 1, 28, 1, 1, 30, 1, 1, 32, 1, 1, 34, 1, 1, 36, 1, 1, 38, 1, 1]
v, n) |
Return the n-th continued fraction convergent of the continued
fraction defined by the sequence of integers v. We assume
.
INPUT: v -- list of integers n -- integer OUTPUT: a rational number
If the continued fraction integers are
then
convergent(v,2)
is the rational number
and
convergent(v,k)
is the rational number
represented by the continued fraction.
sage: convergent([2, 1, 2, 1, 1, 4, 1, 1], 7) 193/71
v) |
Return all the partial convergents of a continued fraction defined by the sequence of integers v.
If v is not a list, compute the continued fraction of v and return its convergents (this is potentially much faster than calling continued_fraction first, since continued fractions are implemented using PARI and there is overhead moving the answer back from PARI).
INPUT: v -- list of integers or a rational number OUTPUT: list -- of partial convergents, as rational numbers
sage: convergents([2, 1, 2, 1, 1, 4, 1, 1]) [2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71]
a, [b=1], [m=1], [n=0]) |
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.
sage: crt(2, 1, 3, 5) -4 sage: crt(13,20,100,301) -2087
b, a, [ord=None]) |
Return an integer
such that
, assuming that ord is a
multiple of the multiplicative order of
. If ord is not
specified an attempt is made to compute it.
The elements a and b must support exponentiation to a negative power.
If no such
exits, this function raises a ValueError exception.
ALGORITHM: Baby step giant step.
sage: b = Mod(2,37); a = b^20 sage: discrete_log_generic(b, a) 20 sage: b = Mod(2,997); a = b^20 sage: discrete_log_generic(b, a) 20
sage: K = GF(3^6) sage: b = K.gen() sage: a = b^210 sage: discrete_log_generic(b, a, K.order()-1) 210
sage: b = Mod(1,37); a = Mod(2,37) sage: discrete_log_generic(b, a) Traceback (most recent call last): ... ValueError: Log of 2 to the base 1 does not exist. sage: b = Mod(1,997); a = Mod(2,997) sage: discrete_log_generic(b, a) Traceback (most recent call last): ... ValueError: Log of 2 to the base 1 does not exist.
Author: William Stein and David Joyner (2005-01-05)
n) |
Returns a list of all positive integer divisors of the nonzero integer n.
sage: divisors(-3) [1, 3] sage: divisors(6) [1, 2, 3, 6] sage: divisors(28) [1, 2, 4, 7, 14, 28] sage: divisors(2^5) [1, 2, 4, 8, 16, 32] sage: divisors(100) [1, 2, 4, 5, 10, 20, 25, 50, 100] sage: divisors(1) [1] sage: divisors(0) Traceback (most recent call last): ... ValueError: n must be nonzero sage: 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]
n) |
Return a list of the primes
.
This is extremely slow and is for educational purposes only. Use
prime_list(..., leave_pari=True)
for an extremely efficient
implementation.
n) |
Return the value of the Euler phi function on 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 euler_phi(n)
is
defined and equals 0.
sage: euler_phi(1) 1 sage: euler_phi(2) 1 sage: euler_phi(3) 2 sage: euler_phi(12) 4 sage: euler_phi(37) 36
Notice that euler_phi is defined to be 0 on negative numbers and 0.
sage: euler_phi(-1) 0 sage: euler_phi(0) 0
We verify directly that the phi function is correct for 21.
sage: euler_phi(21) 12 sage: [i for i in range(21) if gcd(21,i) == 1] [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]
The length of the list of integers 'i' in range(n) such that the gcd(i,n) == 1 equals euler_phi(n).
sage: len([i for i in range(21) if gcd(21,i) == 1]) == euler_phi(21) True
Author Log:
n, [proof=0], [int_=pari], [algorithm=False], [verbose=True]) |
Returns the factorization of the integer n as a sorted list of tuples (p,e).
INPUT: n -- an nonzero integer proof -- bool (default: True) int_ -- bool (default: False) whether to return answers as Python ints algorithm -- string * 'pari' -- (default) use the PARI c library * 'kash' -- use KASH computer algebra system (requires the optional kash package be installed) verbose -- integer (default 0); pari's debug variable is set to this; e.g., set to 4 or 8 to see lots of output during factorization. OUTPUT: factorization of n
sage: factor(500) 2^2 * 5^3 sage: factor(-20) -1 * 2^2 * 5
sage: factor(500, algorithm='kash') # requires optional kash package 2^2 * 5^3
sage: factor(0) Traceback (most recent call last): ... ArithmeticError: Prime factorization of 0 not defined. sage: factor(1) 1 sage: factor(-1) -1 sage: factor(2004) 2^2 * 3 * 167
sage: factor(2^197 + 1) # takes a long time 3 * 197002597249 * 1348959352853811313 * 251951573867253012259144010843
n, [algorithm=gmp]) |
Compute the factorial of
, which is the product
.
INPUT: n -- an integer algorithm -- string (default: 'gmp') 'gmp' -- use the GMP C-library factorial function 'pari' -- use PARI's factorial function OUTPUT: an integer
sage: factorial(0) 1 sage: factorial(4) 24 sage: factorial(10) 3628800 sage: factorial(1) == factorial(0) True sage: factorial(6) == 6*5*4*3*2 True sage: factorial(1) == factorial(0) True sage: factorial(71) == 71* factorial(70) True sage: factorial(-32) Traceback (most recent call last): ... ValueError: factorial -- n = (-32) must be nonnegative
PERFORMANCE: This discussion is valid as of April 2006. All timings below are on a Pentium Core Duo 2Ghz MacBook Pro running Linux with a 2.6.16.1 kernel.
&*[1..n]
.
It takes 113 seconds to compute the factorial of
x, a) |
Returns the falling factorial
.
The notation in the literature is a mess: often
, but there
are many other notations: GKP: Concrete Mathematics uses
.
Definition: for integer
we have
.
In all other cases we use the GAMMA-function:
.
INPUT: x -- element of a ring a -- a non-negative integer or x and a -- any numbers OUTPUT: the falling factorial
sage: falling_factorial(10, 3) 720
sage: falling_factorial(10, RR('3.0')) 720.00000000000000
sage: falling_factorial(10, RR('3.3')) 1310.1163339660077
sage: falling_factorial(10, 10) 3628800 sage: factorial(10) 3628800
sage: falling_factorial(1+i, i) 0.65296549642016677 + 0.34306583981654537*I
sage: falling_factorial(1+i, 4) 2.0000000000000000 + 4.0000000000000000*I
sage: falling_factorial(i, 4) -10.000000000000000
sage: M = MatrixSpace(ZZ, 4, 4) sage: A = M([1,0,1,0,1,0,1,0,1,0,10,10,1,0,1,1]) sage: falling_factorial(A, 2) # A(A - I) [ 1 0 10 10] [ 1 0 10 10] [ 20 0 101 100] [ 2 0 11 10]
sage: x = ZZ['x'].0 sage: falling_factorial(x, 4) x^4 - 6*x^3 + 11*x^2 - 6*x
Author: Jaap Spies (2006-03-05)
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
n, k, q) |
Return the gaussian binomial
sage: gaussian_binomial(5,1,2) 31
Author: David Joyner and William Stein
a, [b=0]) |
The greatest commond divisor of a and b.
sage: GCD(97,100) 1 sage: GCD(97*10^15, 19^20*97^2) 97
a, m, [one=1]) |
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.
sage: generic_power(2,5) 32 sage: generic_power(RealField()('2.5'),4) 39.062500000000000 sage: generic_power(0,0) 1 sage: generic_power(2,-3) Traceback (most recent call last): ... ArithmeticError: 2 cannot be raised to the negative power -3
a, b, p, [algorithm=pari]) |
Returns 1 if
-adically represents a nonzero
square, otherwise returns
. If either a or b is 0, returns 0.
INPUT: a, b -- integers p -- integer; either prime or -1 (which represents the archimedean place) algorithm -- string 'pari' -- (default) use the PARI C library 'direct' -- use a Python implementation 'all' -- use both PARI and direct and check that the results agree, then return the common answer OUTPUT: integer (0, -1, or 1)
sage: hilbert_symbol (-1, -1, -1, algorithm='all') -1 sage: hilbert_symbol (2,3, 5, algorithm='all') 1 sage: hilbert_symbol (4, 3, 5, algorithm='all') 1 sage: hilbert_symbol (0, 3, 5, algorithm='all') 0 sage: hilbert_symbol (-1, -1, 2, algorithm='all') -1 sage: hilbert_symbol (1, -1, 2, algorithm='all') 1 sage: hilbert_symbol (3, -1, 2, algorithm='all') -1
Author: William Stein and David Kohel (2006-01-05)
a, m) |
The inverse of the integer a modulo the integer m.
sage: inverse_mod(7,1) 0 sage: inverse_mod(5,14) 3 sage: inverse_mod(3,-5) 2
n, [flag=0]) |
Returns True if
is prime, and False otherwise. The result
is proven correct - this is NOT a pseudo-primality test!.
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
Note: We do not consider negatives of prime numbers as prime.
:
sage: is_prime(389) True sage: is_prime(2000) False sage: is_prime(2) True sage: is_prime(-1) False sage: factor(-6) -1 * 2 * 3 sage: is_prime(1) False sage: is_prime(-2) False
IMPLEMENTATION: Calls the PARI isprime function.
n, [flag=False], [use_pari=0]) |
Returns True if
is a prime power, and False otherwise. The result
is proven correct - this is NOT a pseudo-primality test!.
INPUT: n -- an integer flag (for primality testing) -- int 0 (default): use a combination of algorithms. 1: certify primality using the Pocklington-Lehmer Test. 2: certify primality using the APRCL test. use_pari -- (default False); whether to use PARI to determine if the integer is a power. this is vastly faster, but there is a serious bug in PARI version 2.2.12-beta, so using this is not recommended. Try pari(2).ispower? for more details about the bug. OUTPUT: bool -- True or False
IMPLEMENTATION: Calls the PARI isprime and factor (or ispower) functions.
:
sage: is_prime_power(389) True sage: is_prime_power(2000) False sage: is_prime_power(2) True sage: is_prime_power(1024) True sage: is_prime_power(-1) False sage: is_prime_power(1) True sage: is_prime_power(997^100) True sage: is_prime_power(997^100, use_pari=True) True
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 --
n) |
Returns True if and only if n is not divisible by the square of an integer > 1.
a, b) |
x, y) |
The Kronecker symbol (x|y).
INPUT: x -- integer y -- integer
sage: kronecker(3,5) -1 sage: kronecker(3,15) 0 sage: kronecker(2,15) 1 sage: kronecker(-2,15) -1
IMPLEMENTATION: Using Pari.
a, [b=None]) |
The least common multiple of a and b.
sage: LCM(97,100) 9700 sage: LCM(0,2) 0 sage: LCM(-3,-5) 15
n) |
Returns the value of the Moebius function of abs(n), where n is an integer.
DEFINITION:
is 0 if
is not square free, and otherwise equals
,
where
has
distinct prime factors.
INPUT: n -- an integer OUTPUT: 0, 1, or -1
sage: moebius(-5) -1 sage: moebius(9) 0 sage: moebius(12) 0 sage: moebius(-35) 1 sage: moebius(-1) 1 sage: moebius(7) -1
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.
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)
sage: next_prime(-100) 2
Notice that the next_prime(5) is not 5 but 7.
sage: next_prime(5) 7 sage: next_prime(2004) 2011
n) |
Return the number of divisors of the integer n.
x) |
Return the number of primes
.
sage: prime_pi(7) 4 sage: prime_pi(100) 25 sage: prime_pi(1000) 168 sage: prime_pi(100000) 9592
n) |
The odd part of the integer
. This is
,
where
valuation(n,2)
.
n) |
Generate the partitions of an integer.
INPUT: n -- int
» partitions(3) <generator object at 0xab3b3eac>
sage: list(partitions(3)) [(1, 1, 1), (1, 2), (3,)]
Author: David Eppstein, Jan Van lent, George Yoshida; Python Cookbook 2, Recipe 19.16.
a, m, n) |
sage: power_mod(0,0,5) 1 sage: power_mod(2,390,391) 285 sage: power_mod(2,-1,7) 4
start, [stop=False], [leave_pari=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.
INPUT: start -- lower bound stop -- upper bound leave_pari -- bool (default: False) if True the returned list is a PARI list; this is *vastly* faster since the time of prime_range is dominated by conversion from PARI to SAGE integers. However, PARI integers are much different than SAGE integers. If you use this option the lower bound must be 2.
You can also call this function with prime_range(bound) to get all primes up to bound.
sage: prime_range(10) [2, 3, 5, 7] sage: prime_range(7) [2, 3, 5] sage: prime_range(2000,2020) [2003, 2011, 2017] sage: prime_range(2,2) [] sage: prime_range(2,3) [2] sage: prime_range(10) [2, 3, 5, 7]
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.
sage: previous_prime(10) 7 sage: previous_prime(7) 5 sage: previous_prime(8) 7 sage: previous_prime(7) 5 sage: previous_prime(5) 3 sage: previous_prime(3) 2 sage: previous_prime(2) -2 sage: previous_prime(1) -2 sage: previous_prime(-20) -23
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.
sage: prime_divisors(1) [] sage: prime_divisors(100) [2, 5] sage: prime_divisors(-100) [2, 5] sage: prime_divisors(2004) [2, 3, 167]
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.
sage: prime_divisors(1) [] sage: prime_divisors(100) [2, 5] sage: prime_divisors(-100) [2, 5] sage: prime_divisors(2004) [2, 3, 167]
x) |
Return the number of primes
.
sage: prime_pi(7) 4 sage: prime_pi(100) 25 sage: prime_pi(1000) 168 sage: prime_pi(100000) 9592
start, [stop=False], [leave_pari=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.
INPUT: start -- lower bound stop -- upper bound leave_pari -- bool (default: False) if True the returned list is a PARI list; this is *vastly* faster since the time of prime_range is dominated by conversion from PARI to SAGE integers. However, PARI integers are much different than SAGE integers. If you use this option the lower bound must be 2.
You can also call this function with prime_range(bound) to get all primes up to bound.
sage: prime_range(10) [2, 3, 5, 7] sage: prime_range(7) [2, 3, 5] sage: prime_range(2000,2020) [2003, 2011, 2017] sage: prime_range(2,2) [] sage: prime_range(2,3) [2] sage: prime_range(10) [2, 3, 5, 7]
n, m) |
Returns the prime-to-m part of n, i.e., the largest divisor of n that is coprime to m.
INPUT: n -- Integer (nonzero) m -- Integer OUTPUT: Integer
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 potentially much
slower since it simply calls the next_prime
function
repeatedly, and next_prime
is slow, partly because it
proves correctness.
sage: for p in primes(5,10): ... print p ... 5 7 sage: list(primes(10000000000, 10000000100)) [10000000019, 10000000033, 10000000061, 10000000069, 10000000097]
n) |
Return a generator for the multiplicative group of integers
modulo
, if one exists.
sage: primitive_root(23) 5 sage: print [primitive_root(p) for p in primes(100)] [1, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5]
n) |
Return a sorted list of all squares modulo the integer
in the
range
.
sage: quadratic_residues(11) [0, 1, 3, 4, 5, 9] sage: quadratic_residues(1) [0] sage: quadratic_residues(2) [0, 1] sage: quadratic_residues(8) [0, 1, 4] sage: quadratic_residues(-10) [0, 1, 4, 5, 6, 9] sage: v = quadratic_residues(1000); len(v); 159
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.
:
sage: m = 100000 sage: (119*inverse_mod(53,m))%m 11323 sage: rational_reconstruction(11323,m) (119, 53)
x, a) |
Returns the rising factorial
.
The notation in the literature is a mess: often
, but there
are many other notations: GKP: Concrete Mathematics uses
.
The rising factorial is also known as the Pochhammer symbol, see Maple and Mathematica.
Definition: for integer
we have
.
In all other cases we use the GAMMA-function:
.
INPUT: x -- element of a ring a -- a non-negative integer or x and a -- any numbers OUTPUT: the rising factorial
sage: rising_factorial(10,3) 1320
sage: rising_factorial(10,RR('3.0')) 1320.0000000000000
sage: rising_factorial(10,RR('3.3')) 2826.3889582496449
sage: rising_factorial(1+i, i) 0.26681639063783236 + 0.12278335400637194*I
sage: rising_factorial(i, 4) -10.000000000000000
See falling_factorial(i, 4)!
sage: x = PolynomialRing(IntegerRing(),'x').gen() sage: rising_factorial(x, 4) x^4 + 6*x^3 + 11*x^2 + 6*x
Author: Jaap Spies (2006-03-05)
n, [k=1]) |
Return the sum of the k-th powers of the divisors of n.
INPUT: n -- integer k -- integer (default: 1) OUTPUT: integer
sage: sigma(5) 6 sage: sigma(5,2) 26
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.
sage: trial_division(15) 3 sage: trial_division(91) 7 sage: trial_division(11) 11 sage: trial_division(387833, 300) 387833 sage: # 300 is not big enough to split off a sage: # factor, but 400 is. sage: trial_division(387833, 400) 389
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.
:
sage: valuation(512,2) 9 sage: valuation(1,2) 0
Valuation of 0 is defined, but valuation with respect to 0 is not::
sage: valuation(0,7) Infinity sage: valuation(3,0) Traceback (most recent call last): ... ValueError: valuation at 0 not defined
Here are some other example::
sage: valuation(100,10) 2 sage: valuation(200,10) 2 sage: valuation(243,3) 5 sage: valuation(243*10007,3) 5 sage: valuation(243*10007,10007) 1
a, b) |
Returns triple of integers (g,s,t) such that g = s*a+t*b = gcd(a,b).
sage: xgcd(56, 44) (4, 4, -5) sage: 4*56 + (-5)*44 4
See About this document... for information on suggesting changes.