Module: sage.rings.arith
Miscellaneous arithmetic functions
Module-level Functions
a, b, m, n) |
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) 11 sage: crt(13,20,100,301) -2087
You can also use upper case:
sage: c = CRT(2,3, 3, 5); c -7 sage: c % 3 == 2 True sage: c % 5 == 3 True
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:
v, moduli) |
Given a list v of integers and a list of corresponding moduli, find a single integer that reduces to each element of v modulo the corresponding moduli.
sage: CRT_list([2,3,2], [3,5,7]) 23
X, moduli) |
Input:
a, [b=0], [integer=False]) |
The greatest common divisor of a and b.
Input:
Additional keyword arguments are passed to the respectively called methods.
sage: GCD(97,100) 1 sage: GCD(97*10^15, 19^20*97^2) 97 sage: GCD(2/3, 4/3) 2/3 sage: GCD([2,4,6,8]) 2 sage: GCD(srange(0,10000,10)) # fast !! 10
a, [b=None], [integer=False]) |
The least common multiple of a and b, or if a is a list and b is omitted the least common multiple of all elements of a.
NOTE: Use integer=True to make this vastly faster if you are working with lists of integers.
Input:
sage: LCM(97,100) 9700 sage: LCM(0,2) 0 sage: LCM(-3,-5) 15 sage: LCM([1,2,3,4,5]) 60 sage: v = LCM(range(1,10000),integer=True) # *very* fast! sage: len(str(v)) 4349
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 (g,s,t) such that g = s*a+t*b = gcd(a,b).
Input:
NOTE: There is no guarantee that the returned cofactors (s and t) are minimal. In the integer case, see Integer._xgcd() for minimal cofactors.
sage: xgcd(56, 44) (4, 4, -5) sage: 4*56 + (-5)*44 4 sage: g, a, b = xgcd(5/1, 7/1); g, a, b (1, -4, 3) sage: a*(5/1) + b*(7/1) == g True sage: x = polygen(QQ) sage: xgcd(x^3 - 1, x^2 - 1) (x - 1, 1, -x) sage: K.<g> = NumberField(x^2-3) sage: R.<a,b> = K[] sage: S.<y> = R.fraction_field()[] sage: xgcd(y^2, a*y+b) (b^2/a^2, 1, ((-1)/a)*y + b/a^2) sage: xgcd((b+g)*y^2, (a+g)*y+b) ((b^3 + g*b^2)/(a^2 + 2*g*a + 3), 1, ((-b - g)/(a + g))*y + (b^2 + g*b)/(a^2 + 2*g*a + 3))
z, n, [known_bits=None], [use_bits=None], [known_digits=None], [use_digits=None]) |
Returns a polynomial of degree at most
which is approximately
satisfied by the number
. Note that the returned polynomial
need not be irreducible, and indeed usually won't be if
is a good
approximation to an algebraic number of degree less than
.
You can specify the number of known bits or digits with known_bits=k or known_digits=k; Pari is then told to compute the result using .8*k of these bits/digits. (The Pari documentation recommends using a factor between .6 and .9, but internally defaults to .8.) Or, you can specify the precision to use directly with use_bits=k or use_digits=k. If none of these are specified, then the precision is taken from the input value.
ALGORITHM: Uses the PARI C-library algdep command.
Input:
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 complex number.
sage: z = (1/2)*(1 + RDF(sqrt(3)) *CC.0); z 0.500000000000000 + 0.866025403784439*I sage: p = algdep(z, 6); p x^5 + x^2 sage: p.factor() (x + 1) * x^2 * (x^2 - x + 1) sage: z^2 - z + 1 1.11022302462516e-16
This example involves a
-adic number.
sage: K = Qp(3, print_mode = 'series') 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
These examples show the importance of proper precision control. We compute a 200-bit approximation to sqrt(2) which is wrong in the 33'rd bit.
sage: z = sqrt(RealField(200)(2)) + (1/2)^33 sage: p = algdep(z, 4); p 177858662573*x^4 + 59566570004*x^3 - 221308611561*x^2 - 84791308378*x - 317384111411 sage: factor(p) 177858662573*x^4 + 59566570004*x^3 - 221308611561*x^2 - 84791308378*x - 317384111411 sage: algdep(z, 4, known_bits=32) x^2 - 2 sage: algdep(z, 4, known_digits=10) x^2 - 2 sage: algdep(z, 4, use_bits=25) x^2 - 2 sage: algdep(z, 4, use_digits=8) x^2 - 2
z, n, [known_bits=None], [use_bits=None], [known_digits=None], [use_digits=None]) |
Returns a polynomial of degree at most
which is approximately
satisfied by the number
. Note that the returned polynomial
need not be irreducible, and indeed usually won't be if
is a good
approximation to an algebraic number of degree less than
.
You can specify the number of known bits or digits with known_bits=k or known_digits=k; Pari is then told to compute the result using .8*k of these bits/digits. (The Pari documentation recommends using a factor between .6 and .9, but internally defaults to .8.) Or, you can specify the precision to use directly with use_bits=k or use_digits=k. If none of these are specified, then the precision is taken from the input value.
ALGORITHM: Uses the PARI C-library algdep command.
Input:
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 complex number.
sage: z = (1/2)*(1 + RDF(sqrt(3)) *CC.0); z 0.500000000000000 + 0.866025403784439*I sage: p = algdep(z, 6); p x^5 + x^2 sage: p.factor() (x + 1) * x^2 * (x^2 - x + 1) sage: z^2 - z + 1 1.11022302462516e-16
This example involves a
-adic number.
sage: K = Qp(3, print_mode = 'series') 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
These examples show the importance of proper precision control. We compute a 200-bit approximation to sqrt(2) which is wrong in the 33'rd bit.
sage: z = sqrt(RealField(200)(2)) + (1/2)^33 sage: p = algdep(z, 4); p 177858662573*x^4 + 59566570004*x^3 - 221308611561*x^2 - 84791308378*x - 317384111411 sage: factor(p) 177858662573*x^4 + 59566570004*x^3 - 221308611561*x^2 - 84791308378*x - 317384111411 sage: algdep(z, 4, known_bits=32) x^2 - 2 sage: algdep(z, 4, known_digits=10) x^2 - 2 sage: algdep(z, 4, use_bits=25) x^2 - 2 sage: algdep(z, 4, use_digits=8) x^2 - 2
n, [algorithm=pari]) |
Return the n-th Bernoulli number, as a rational number.
Input:
sage: bernoulli(12) -691/2730 sage: bernoulli(50) 495057205241079648212477525/66
We use of each of the alternative algorithms:
sage: bernoulli(12, algorithm='gap') -691/2730 sage: bernoulli(12, algorithm='gp') -691/2730 sage: bernoulli(12, algorithm='magma') # optional -691/2730 sage: bernoulli(12, algorithm='pari') -691/2730 sage: bernoulli(12, algorithm='python') -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
binomial(x,m)= binomial(x,x-m)
If
return 0
.
Input::
:
sage: binomial(5,2) 10 sage: binomial(2,0) 1 sage: binomial(1/2, 0) 1 sage: binomial(3,-1) 0 sage: binomial(20,10) 184756 sage: binomial(RealField()('2.5'), 2) 1.87500000000000 sage: n=var('n'); binomial(n,2) (n - 1)*n/2 sage: n=var('n'); binomial(n,n) 1 sage: n=var('n'); binomial(n,n-1) n
v, [n=None]) |
Function returns the continuant of the sequence
(list or tuple).
Definition: see Graham, Knuth and Patashnik: Concrete Mathematics: 6.7 Continuants:
If
or
the default
is used.
Input:
sage: continuant([1,2,3]) 10 sage: p = continuant([2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10]) sage: q = continuant([1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10]) sage: p/q 517656/190435 sage: convergent([2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10],14) 517656/190435 sage: x = PolynomialRing(RationalField(),'x',5).gens() sage: continuant(x) x0*x1*x2*x3*x4 + x0*x1*x2 + x0*x1*x4 + x0*x3*x4 + x2*x3*x4 + x0 + x2 + x4 sage: continuant(x, 3) x0*x1*x2 + x0 + x2 sage: continuant(x,2) x0*x1 + 1
:
sage: z = QQ['z'].0 sage: continuant((z,z,z,z,z,z,z,z,z,z,z,z,z,z,z),6) z^6 + 5*z^4 + 6*z^2 + 1 sage: continuant(9) Traceback (most recent call last): ... TypeError: object of type 'sage.rings.integer.Integer' has no len()
Author: Jaap Spies (2007-02-06)
x, [partial_convergents=False], [bits=None]) |
Returns the continued fraction of x as a list.
sage: continued_fraction_list(45/17) [2, 1, 1, 1, 5] sage: continued_fraction_list(e, bits=20) [2, 1, 2, 1, 1, 4, 1, 1, 6] sage: continued_fraction_list(e, bits=30) [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1] sage: continued_fraction_list(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_list(sqrt(4/19)) [0, 2, 5, 1, 1, 2, 1, 16, 1, 2, 1, 1, 5, 4, 5, 1, 1, 2, 1, 15, 2] sage: continued_fraction_list(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_list(e) [2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 11] sage: continued_fraction_list(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_list(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:
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:
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, m, n) |
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) 11 sage: crt(13,20,100,301) -2087
You can also use upper case:
sage: c = CRT(2,3, 3, 5); c -7 sage: c % 3 == 2 True sage: c % 5 == 3 True
lis, [n=1]) |
Returns the
successive differences of the elements in
.
sage: differences(prime_range(50)) [1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4] sage: differences([i^2 for i in range(1,11)]) [3, 5, 7, 9, 11, 13, 15, 17, 19] sage: differences([i^3 + 3*i for i in range(1,21)]) [10, 22, 40, 64, 94, 130, 172, 220, 274, 334, 400, 472, 550, 634, 724, 820, 922, 1030, 1144] sage: differences([i^3 - i^2 for i in range(1,21)], 2) [10, 16, 22, 28, 34, 40, 46, 52, 58, 64, 70, 76, 82, 88, 94, 100, 106, 112] sage: differences([p - i^2 for i, p in enumerate(prime_range(50))], 3) [-1, 2, -4, 4, -4, 4, 0, -6, 8, -6, 0, 4]
Author: Timothy Clemans (2008-03-09)
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.
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.
Input:
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 sage: type(euler_phi(0)) <type 'sage.rings.integer.Integer'>
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: - William Stein - Alex Clemesha (2006-01-10): some examples
n, [proof=None], [int_=False], [algorithm=pari], [verbose=0]) |
Returns the factorization of the integer n as a sorted list of tuples (p,e).
Input:
NOTES: The qsieve and ecm commands give access to highly optimized implementations of algorithms for doing certain integer factorization problems. These implementations are not used by the generic factor command, which currently just calls PARI (note that PARI also implements sieve and ecm algorithms, but they aren't as optimized). Thus you might consider using them instead for certain numbers.
The factorization prints in user-friendly format but the (p,e) pairs can easily be accessed - see examples
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 calls PARI's factor, which has proof False by default. SAGE has a global proof flag, set to True by default (see sage.structure.proof, or proof.[tab]). To override the default, call this function with proof=False.
sage: factor(3^89-1, proof=False) 2 * 179 * 1611479891519807 * 5042939439565996049162197
sage: factor(2^197 + 1) # takes a long time (e.g., 3 seconds!) 3 * 197002597249 * 1348959352853811313 * 251951573867253012259144010843
To access the data in a factorization:
sage: factor(420) 2^2 * 3 * 5 * 7 sage: [x for x in factor(420)] [(2, 2), (3, 1), (5, 1), (7, 1)] sage: [p for p,e in factor(420)] [2, 3, 5, 7] sage: [e for p,e in factor(420)] [2, 1, 1, 1] sage: [p^e for p,e in factor(420)] [4, 3, 5, 7]
n, [algorithm=gmp]) |
Compute the factorial of
, which is the product
.
Input:
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 -- 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:
sage: falling_factorial(10, 3) 720 sage: falling_factorial(10, RR('3.0')) 720.000000000000 sage: falling_factorial(10, RR('3.3')) 1310.11633396601 sage: falling_factorial(10, 10) 3628800 sage: factorial(10) 3628800 sage: falling_factorial(1+I, I) 0.652965496420167 + 0.343065839816545*I sage: falling_factorial(1+I, 4) (I - 2)*(I - 1)*I*(I + 1) sage: expand(falling_factorial(1+I, 4)) 4*I + 2 sage: falling_factorial(I, 4) (I - 3)*(I - 2)*(I - 1)*I
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:
Author: Scott David Daniels, Python Cookbook, 2nd Ed., Recipe 18.13
n, k, [q=None]) |
Return the gaussian binomial
sage: gaussian_binomial(5,1) q^4 + q^3 + q^2 + q + 1 sage: gaussian_binomial(5,1).subs(q=2) 31 sage: gaussian_binomial(5,1,2) 31
Author: David Joyner and William Stein
a, [b=0], [integer=False]) |
The greatest common divisor of a and b.
Input:
Additional keyword arguments are passed to the respectively called methods.
sage: GCD(97,100) 1 sage: GCD(97*10^15, 19^20*97^2) 97 sage: GCD(2/3, 4/3) 2/3 sage: GCD([2,4,6,8]) 2 sage: GCD(srange(0,10000,10)) # fast !! 10
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:
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)
x) |
Return the ceiling of x.
sage: integer_ceil(5.4) 6
x) |
Return the largest integer
.
Input:
sage: integer_floor(5.4) 5 sage: integer_floor(float(5.4)) 5 sage: integer_floor(-5/2) -3 sage: integer_floor(RDF(-5/2)) -3
a, m) |
The inverse of the ring element a modulo m.
If no special inverse_mod is defined for the elements, it tries to coerce them into integers and perform the inversion there
sage: inverse_mod(7,1) 0 sage: inverse_mod(5,14) 3 sage: inverse_mod(3,-5) 2
n) |
This function returns True if and only if
is a power of 2
Input:
sage: is_power_of_two(1024) True
sage: is_power_of_two(1) True
sage: is_power_of_two(24) False
sage: is_power_of_two(0) False
sage: is_power_of_two(-4) False
Author: Jaap Spies (2006-12-09)
n, [flag=0]) |
Returns True if
is prime, and False otherwise. The result
is proven correct - this is NOT a pseudo-primality test!.
Input:
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=0]) |
Returns True if
is a prime power, and False otherwise.
The result is proven correct - this is NOT a
pseudo-primality test!.
Input:
:
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
n, [flag=0]) |
Returns True if
is a pseudo-prime, and False otherwise. The result
is NOT proven correct - this is a pseudo-primality test!.
Input:
Note: We do not consider negatives of prime numbers as prime.
:
sage: is_pseudoprime(389) True sage: is_pseudoprime(2000) False sage: is_pseudoprime(2) True sage: is_pseudoprime(-1) False sage: factor(-6) -1 * 2 * 3 sage: is_pseudoprime(1) False sage: is_pseudoprime(-2) False
IMPLEMENTATION: Calls the PARI ispseudoprime function.
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:
sage: is_square(2) False sage: is_square(4) True sage: is_square(2.2) True sage: is_square(-2.2) False sage: is_square(CDF(-2.2)) True sage: is_square((x-1)^2) True
sage: is_square(4, True) (True, 2)
n) |
Returns True if and only if n is not divisible by the square of an integer > 1.
x, y) |
Synonym for kronecker_symbol
.
x, y) |
The Kronecker symbol (x|y).
Input:
sage: kronecker(3,5) -1 sage: kronecker(3,15) 0 sage: kronecker(2,15) 1 sage: kronecker(-2,15) -1
IMPLEMENTATION: Using GMP.
a, [b=None], [integer=False]) |
The least common multiple of a and b, or if a is a list and b is omitted the least common multiple of all elements of a.
NOTE: Use integer=True to make this vastly faster if you are working with lists of integers.
Input:
sage: LCM(97,100) 9700 sage: LCM(0,2) 0 sage: LCM(-3,-5) 15 sage: LCM([1,2,3,4,5]) 60 sage: v = LCM(range(1,10000),integer=True) # *very* fast! sage: len(str(v)) 4349
x, p) |
The Legendre symbol (x|p), for
prime.
NOTE: The kronecker_symbol
command extends the
Legendre symbol to composite moduli and
.
Input:
sage: legendre_symbol(2,3) -1 sage: legendre_symbol(1,3) 1 sage: legendre_symbol(1,2) Traceback (most recent call last): ... ValueError: p must be odd sage: legendre_symbol(2,15) Traceback (most recent call last): ... ValueError: p must be a prime sage: kronecker_symbol(2,15) 1
u, m, T) |
Maximal Quotient Rational Reconstruction.
FOR research purposes only - this is pure Python, so slow.
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.
) |
Return the multinomial coefficient
sage: multinomial(0, 0, 2, 1, 0, 0) 3 sage: multinomial(3, 2) 10 sage: multinomial(2^30, 2, 1) 618970023101454657175683075
Author: Gabriel Ebner
n, [proof=None]) |
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, this function only returns a pseudo-prime, as defined by the PARI nextprime function. If it is None, uses the global default (see sage.structure.proof)
Input:
sage: next_prime(-100) 2 sage: next_prime(1) 2 sage: next_prime(2) 3 sage: next_prime(3) 5 sage: next_prime(4) 5
Notice that the next_prime(5) is not 5 but 7.
sage: next_prime(5) 7 sage: next_prime(2004) 2011
n) |
The next prime power greater than the integer n. If n is a prime power, then this function does not return n, but the next prime power after n.
sage: next_prime_power(-10) 1 sage: is_prime_power(1) True sage: next_prime_power(0) 1 sage: next_prime_power(1) 2 sage: next_prime_power(2) 3 sage: next_prime_power(10) 11 sage: next_prime_power(7) 8 sage: next_prime_power(99) 101
n) |
Returns the next probable prime after self, as determined by PARI.
Input:
sage: next_probable_prime(-100) 2 sage: next_probable_prime(19) 23 sage: next_probable_prime(int(999999999)) 1000000007 sage: next_probable_prime(2^768) 155251809230070893514897948846250255525688601711669661113905203802605095268 637688633087840882864647795048773069713107320617158004411481439144428727504 118113920445497602084990555026528563159844482526299919371646875089284685381 6058039
n) |
sage: nth_prime(0) Traceback (most recent call last): ... ValueError sage: nth_prime(3) 5 sage: nth_prime(10) 29
n) |
Return the number of divisors of the integer n.
n) |
The odd part of the integer
. This is
,
where
valuation(n,2)
.
a, n, m) |
sage: power_mod(0,0,5) Traceback (most recent call last): ... ArithmeticError: 0^0 is undefined. sage: power_mod(2,390,391) 285 sage: power_mod(2,-1,7) 4
start, [stop=None], [leave_pari=False]) |
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:
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 raises a ValueError.
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) Traceback (most recent call last): ... ValueError: no previous prime sage: previous_prime(1) Traceback (most recent call last): ... ValueError: no previous prime sage: previous_prime(-20) Traceback (most recent call last): ... ValueError: no previous prime
n) |
The largest prime power
. The result is provably
correct. If
, this function returns
,
where
is prime power and
and no larger negative
of a prime power has this property.
sage: previous_prime_power(2) 1 sage: previous_prime_power(10) 9 sage: previous_prime_power(7) 5 sage: previous_prime_power(127) 125
sage: previous_prime_power(0) Traceback (most recent call last): ... ValueError: no previous prime power sage: previous_prime_power(1) Traceback (most recent call last): ... ValueError: no previous prime power
sage: n = previous_prime_power(2^16 - 1) sage: while is_prime(n): ... n = previous_prime_power(n) sage: factor(n) 251^2
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]
start, [stop=None]) |
List of all positive primes powers between start and stop-1, inclusive. If the second argument is omitted, returns the primes up to the first argument.
sage: prime_powers(20) [1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19] sage: len(prime_powers(1000)) 194 sage: len(prime_range(1000)) 168 sage: a = [z for z in range(95,1234) if is_prime_power(z)] sage: b = prime_powers(95,1234) sage: len(b) 194 sage: len(a) 194 sage: a[:10] [97, 101, 103, 107, 109, 113, 121, 125, 127, 128] sage: b[:10] [97, 101, 103, 107, 109, 113, 121, 125, 127, 128] sage: a == b True
TESTS:
sage: v = prime_powers(10) sage: type(v[0]) # trac #922 <type 'sage.rings.integer.Integer'>
start, [stop=None], [leave_pari=False]) |
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:
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:
sage: z = 43434 sage: z.prime_to_m_part(20) 21717
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(11)) [2, 3, 5, 7] sage: list(primes(10000000000, 10000000100)) [10000000019, 10000000033, 10000000061, 10000000069, 10000000097]
n, [leave_pari=False]) |
Return the first
primes.
Input:
sage: primes_first_n(10) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] sage: len(primes_first_n(1000)) 1000
This is very fast, because we leave the output as a PARI object:
sage: v = primes_first_n(10^6, leave_pari=True) sage: len(v) 1000000
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
n, [proof=None]) |
Returns a random prime p between 2 and n (i.e. 2 <= p <= n). The returned prime is chosen uniformly at random from the set of prime numbers less than or equal to n.
Input:
sage: random_prime(100000) 88237 sage: random_prime(2) 2
TESTS:
sage: type(random_prime(2)) <type 'sage.rings.integer.Integer'> sage: type(random_prime(100)) <type 'sage.rings.integer.Integer'>
Author Log:
a, m, [algorithm=fast]) |
This function tries to compute x/y, where x/y is 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 x/y exists, that pair is unique and this function returns it. If no such pair exists, this function raises ZeroDivisionError.
An 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.
Input: a - an integer m - a modulus algorithm - (default: 'fast') fast - a fast compiled implementation python - a slow pure python implementation
Output: Numerator and denominator n, d of the unique rational number r=n/d, if it exists, with |n| and |d| <= sqrt(N/2). Return (0,0) if no such number exists.
The algorithm for rational reconstruction is described (with a complete nontrivial proof) on pages 656-657 of Knuth, Vol 2, 3rd ed. as the solution to exercise 51 on page 379. See in particular the conclusion paragraph right in the middle of page 657, which describes the algorithm thus:
This discussion proves that the problem can be solved efficiently by applying Algorithm 4.5.2X with u=m and v=a, but with the following replacement for step X2: If v3<=sqrt(m/2), the algorithm terminates. The pair (x,y)=(|v2|,v3*sign(v2)) is then the unique solution, provided that x and y are coprime and x<=sqrt(m/2); otherwise there is no solution. (Alg 4.5.2X is the extended Euclidean algorithm.)
Knuth remarks that this algorithm is due to Wang, Kornerup, and Gregory from around 1983.
:
sage: m = 100000 sage: (119*inverse_mod(53,m))%m 11323 sage: rational_reconstruction(11323,m) 119/53
sage: rational_reconstruction(400,1000) Traceback (most recent call last): ... ValueError: Rational reconstruction of 400 (mod 1000) does not exist.
sage: rational_reconstruction(3,292393, algorithm='python') 3 sage: a = Integers(292393)(45/97); a 204977 sage: rational_reconstruction(a,292393, algorithm='python') 45/97 sage: a = Integers(292393)(45/97); a 204977 sage: rational_reconstruction(a,292393, algorithm='fast') 45/97 sage: rational_reconstruction(293048,292393, algorithm='fast') Traceback (most recent call last): ... ValueError: Rational reconstruction of 655 (mod 292393) does not exist. sage: rational_reconstruction(293048,292393, algorithm='python') Traceback (most recent call last): ... ValueError: Rational reconstruction of 655 (mod 292393) does not exist.
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:
sage: rising_factorial(10,3) 1320
sage: rising_factorial(10,RR('3.0')) 1320.00000000000
sage: rising_factorial(10,RR('3.3')) 2826.38895824964
sage: rising_factorial(1+I, I) 0.266816390637832 + 0.122783354006372*I
sage: a = rising_factorial(I, 4); a I*(I + 1)*(I + 2)*(I + 3) sage: expand(a) -10
See falling_factorial(I, 4).
sage: x = polygen(ZZ) 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:
sage: sigma(5) 6 sage: sigma(5,2) 26
Author Log:
TESTS:
sage: sigma(100,4) 106811523 sage: sigma(factorial(100),3).mod(144169) 3672 sage: sigma(factorial(150),12).mod(691) 176 sage: RR(sigma(factorial(133),20)) 2.80414775675747e4523 sage: sigma(factorial(100),0) 39001250856960000 sage: sigma(factorial(41),1) 229199532273029988767733858700732906511758707916800
n) |
Subfactorial or rencontres numbers, or derangements: number of permutations of
elements with no fixed points.
Input:
sage: subfactorial(0) 1 sage: subfactorial(1) 0 sage: subfactorial(8) 14833
Author: Jaap Spies (2007-01-23)
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:
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
n, [algorithm=gap]) |
Write the integer n as a sum of two integer squares if possible; otherwise raise a ValueError.
sage: two_squares(389) (10, 17) sage: two_squares(7) Traceback (most recent call last): ... ValueError: 7 is not a sum of two squares sage: a,b = two_squares(2009); a,b (28, 35) sage: a^2 + b^2 2009
TODO: Create an implementation using PARI's continued fraction implementation.
m, p) |
The exact power of p that divides m.
m should be an integer or rational (but maybe other types work too.)
This actually just calls the m.valuation() method.
If m is 0, this function returns rings.infinity.
sage: valuation(512,2) 9 sage: valuation(1,2) 0 sage: valuation(5/9, 3) -2
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: You can only compute the valuation with respect to a integer larger than 1.
Here are some other examples:
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 (g,s,t) such that g = s*a+t*b = gcd(a,b).
Input:
NOTE: There is no guarantee that the returned cofactors (s and t) are minimal. In the integer case, see Integer._xgcd() for minimal cofactors.
sage: xgcd(56, 44) (4, 4, -5) sage: 4*56 + (-5)*44 4 sage: g, a, b = xgcd(5/1, 7/1); g, a, b (1, -4, 3) sage: a*(5/1) + b*(7/1) == g True sage: x = polygen(QQ) sage: xgcd(x^3 - 1, x^2 - 1) (x - 1, 1, -x) sage: K.<g> = NumberField(x^2-3) sage: R.<a,b> = K[] sage: S.<y> = R.fraction_field()[] sage: xgcd(y^2, a*y+b) (b^2/a^2, 1, ((-1)/a)*y + b/a^2) sage: xgcd((b+g)*y^2, (a+g)*y+b) ((b^3 + g*b^2)/(a^2 + 2*g*a + 3), 1, ((-b - g)/(a + g))*y + (b^2 + g*b)/(a^2 + 2*g*a + 3))
m, n) |
Extended lcm function: given two positive integers m,n, returns a triple (l,m1,n1) such that l=lcm(m,n)=m1*n1 where m1|m, n1|n and gcd(m1,n1)=1. All with no factorization.
Used to construct an element of order l from elements of orders m,n in any group: see sage/groups/generic.py for examples.
sage: xlcm(120,36) (360, 40, 9)
Class: Moebius
DEFINITION:
is 0 if
is not square free, and otherwise equals
,
where
has
distinct prime factors.
For simplicity, if
we define
.
IMPLEMENTATION: Factors or - for integers - uses the PARI C library.
Input:
sage: moebius(-5) -1 sage: moebius(9) 0 sage: moebius(12) 0 sage: moebius(-35) 1 sage: moebius(-1) 1 sage: moebius(7) -1
sage: moebius(0) # potentially nonstandard! 0
The moebius function even makes sense for non-integer inputs.
sage: x = GF(7)['x'].0 sage: moebius(x+2) -1
Functions: plot,
range
self, [xmin=0], [xmax=50], [pointsize=30], [rgbcolor=(0, 0, 1)], [join=True]) |
Plot the Moebius function.
Input:
self, start, [stop=None], [step=None]) |
Return the Moebius function evaluated at the given range of values, i.e., the image of the list range(start, stop, step) under the Mobius function.
This is much faster than directly computing all these values with a list comprehension.
sage: v = moebius.range(-10,10); v [1, 0, 0, -1, 1, -1, 0, -1, -1, 1, 0, 1, -1, -1, 0, -1, 1, -1, 0, 0] sage: v == [moebius(n) for n in range(-10,10)] True sage: v = moebius.range(-1000, 2000, 4) sage: v == [moebius(n) for n in range(-1000,2000, 4)] True
Special Functions: __call__,
__repr__
See About this document... for information on suggesting changes.