12.13 Miscellaneous arithmetic functions

Module: sage.rings.arith

Miscellaneous arithmetic functions

Module-level Functions

CRT( 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

CRT_basis( 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

CRT_list( 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

CRT_vectors( X, moduli)

Input:

X
- list of lists of the same length
moduli
- list of len(X) moduli
Output:
list
- application of CRT componentwise.

GCD( a, [b=0], [integer=False])

The greatest common divisor of a and b.

Input:

a
- number
b
- number (optional)
integer
- (default: False); if True, do an integer GCD or
v
- vector
integer
- (default: False); if True, do an integer GCD
NOTE
- this is *vastly* faster than doing the generic GCD

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

LCM( 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:

a
- number
b
- number (optional)
integer
- (default: False); if True, do an integer LCM or
a
- vector
integer
- (default: False); if True, do an integer LCM
NOTE
- this is *vastly* faster than doing the generic LCM

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

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.

XGCD( a, b)

Returns triple (g,s,t) such that g = s*a+t*b = gcd(a,b).

Input:

a, b
- integers or univariate polynomials (or any type with an xgcd method).
Output:
g, s, t
- such that g = s*a + t*b

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))

algdep( z, n, [known_bits=None], [use_bits=None], [known_digits=None], [use_digits=None])

Returns a polynomial of degree at most $ n$ which is approximately satisfied by the number $ z$ . Note that the returned polynomial need not be irreducible, and indeed usually won't be if $ z$ is a good approximation to an algebraic number of degree less than $ n$ .

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:

z
- real, complex, 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 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 $ p$ -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

algebraic_dependency( z, n, [known_bits=None], [use_bits=None], [known_digits=None], [use_digits=None])

Returns a polynomial of degree at most $ n$ which is approximately satisfied by the number $ z$ . Note that the returned polynomial need not be irreducible, and indeed usually won't be if $ z$ is a good approximation to an algebraic number of degree less than $ n$ .

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:

z
- real, complex, 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 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 $ p$ -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

bernoulli( 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
'magma'
- use MAGMA (optional)
'python'
- use pure Python implementation

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 $ n>50000$ 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

binomial( x, m)

Return the binomial coefficient

$\displaystyle x (x-1) \cdots (x-m+1) / m!
$

which is defined for $ m \in \mathbf{Z}$ and any $ x$ . We extend this definition to include cases when $ x-m$ is an integer but $ m$ is not by

binomial(x,m)= binomial(x,x-m)

If $ m<0$ return 0 .

Input::

x,m
- numbers or symbolic expressions Either m or x-m must be an integer.

Output:: number or symbolic expression (if input is symbolic)

:

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

continuant( v, [n=None])

Function returns the continuant of the sequence $ v$ (list or tuple).

Definition: see Graham, Knuth and Patashnik: Concrete Mathematics: 6.7 Continuants:

$ K_0() = 1$

$ K_1(x_1) = x_1$

$ K_n(x_1, \cdots, x_n) = K_{n-1}(x_n, \cdots x_{n-1})x_n + K_{n-2}(x_1, \cdots, x_{n-2})$

If $ n = None$ or $ n > len(v)$ the default $ n = len(v)$ is used.

Input:

v
- list or tuple of elements of a ring
n
- optional integer

Output: element of ring (integer, polynomial, etcetera).

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

$ K_n(z,z,\cdots,z) = sum_{k=0}^n {n-k} \choose k z^{n-2k}$ :

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)

continued_fraction_list( x, [partial_convergents=False], [bits=None])

Returns the continued fraction of x as a list.


\begin{note}This may be slow since it's implemented in pure
Python for real input. For rational number input the PARI C
library is used. \end{note}

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]

convergent( v, n)

Return the n-th continued fraction convergent of the continued fraction defined by the sequence of integers v. We assume $ n \geq 0$ .

Input:

v
- list of integers
n
- integer
Output: a rational number

If the continued fraction integers are

$\displaystyle v = [a_0, a_1, a_2, \ldots, a_k]
$

then convergent(v,2) is the rational number

$\displaystyle a_0 + 1/a_1
$

and convergent(v,k) is the rational number

$\displaystyle a1 + 1/(a2+1/(...) ... )
$

represented by the continued fraction.

sage: convergent([2, 1, 2, 1, 1, 4, 1, 1], 7)
193/71

convergents( 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]

crt( 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

differences( lis, [n=1])

Returns the $ n$ successive differences of the elements in $ lis$ .

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)

divisors( 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]

eratosthenes( n)

Return a list of the primes $ \leq n$ .

This is extremely slow and is for educational purposes only.

euler_phi( 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:

n
- an integer

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

factor( 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:

n
- an nonzero integer
proof
- bool or None (default: None)
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

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]

factorial( n, [algorithm=gmp])

Compute the factorial of $ n$ , which is the product $ 1\cdot 2\cdot 3 \cdots (n-1) n$ .

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 -- 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.

falling_factorial( x, a)

Returns the falling factorial $ (x)_a$ .

The notation in the literature is a mess: often $ (x)_a$ , but there are many other notations: GKP: Concrete Mathematics uses $ x^{\underline{a}}$ .

Definition: for integer $ a \ge 0$ we have $ x(x-1) \cdots (x-a+1)$ . In all other cases we use the GAMMA-function: $ \frac {\Gamma(x+1)} {\Gamma(x-a+1)}$ .

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.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)

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

gaussian_binomial( n, k, [q=None])

Return the gaussian binomial

$\displaystyle \binom{n}{k}_q = \frac{(1-q^n)(1-q^{n-1})\cdots (1-q^{n-k+1})}
{(1-q)(1-q^2)\cdots (1-q^k)}.
$

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

gcd( a, [b=0], [integer=False])

The greatest common divisor of a and b.

Input:

a
- number
b
- number (optional)
integer
- (default: False); if True, do an integer GCD or
v
- vector
integer
- (default: False); if True, do an integer GCD
NOTE
- this is *vastly* faster than doing the generic GCD

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

hilbert_symbol( a, b, p, [algorithm=pari])

Returns 1 if $ ax^2 + by^2$ $ p$ -adically represents a nonzero square, otherwise returns $ -1$ . 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)

integer_ceil( x)

Return the ceiling of x.

sage: integer_ceil(5.4)
6

integer_floor( x)

Return the largest integer $ \leq x$ .

Input:

x
- an object that has a floor method or is coercible to int

Output: an Integer

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

inverse_mod( 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

is_power_of_two( n)

This function returns True if and only if $ n$ is a power of 2

Input:

n
- integer

Output:
True
- if n is a power of 2
False
- if not

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)

is_prime( n, [flag=0])

Returns True if $ x$ 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.

is_prime_power( n, [flag=0])

Returns True if $ x$ 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.

:

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

is_pseudoprime( n, [flag=0])

Returns True if $ x$ is a pseudo-prime, and False otherwise. The result is NOT proven correct - this is a pseudo-primality test!.

Input:

flag
- int 0 (default): checks whether x is a Baillie-Pomerance- Selfridge-Wagstaff pseudo prime (strong Rabin-Miller pseudo prime for base 2, followed by strong Lucas test for the sequence (P,-1), P smallest positive integer such that $ P^2 - 4$ is not a square mod x). > 0: checks whether x is a strong Miller-Rabin pseudo prime for flag randomly chosen bases (with end-matching to catch square roots of -1).

Output:
bool
- True or False

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.

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
- (optional) an actual square if found, and None otherwise.

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)

is_squarefree( n)

Returns True if and only if n is not divisible by the square of an integer > 1.

kronecker( x, y)

Synonym for kronecker_symbol.

kronecker_symbol( 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 GMP.

lcm( 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:

a
- number
b
- number (optional)
integer
- (default: False); if True, do an integer LCM or
a
- vector
integer
- (default: False); if True, do an integer LCM
NOTE
- this is *vastly* faster than doing the generic LCM

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

legendre_symbol( x, p)

The Legendre symbol (x|p), for $ p$ prime.

NOTE: The kronecker_symbol command extends the Legendre symbol to composite moduli and $ p=2$ .

Input:

x
- integer
p
- an odd prime number

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

mqrr_rational_reconstruction( 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.

multinomial( )

Return the multinomial coefficient

$\displaystyle \binom{k_1 + \cdots + k_n}{k_1, \cdots, k_n}
= \frac{\left(\sum_{...
...k_i\right)!}{\prod_{i=1}^n k_i!}
= \prod_{i=1}^n \binom{\sum_{j=1}^i k_j}{k_i}
$

sage: multinomial(0, 0, 2, 1, 0, 0)
3
sage: multinomial(3, 2)
10
sage: multinomial(2^30, 2, 1)
618970023101454657175683075

Author: Gabriel Ebner

next_prime( 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:

n
- integer
proof
- bool or None (default: None)

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

next_prime_power( 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

next_probable_prime( n)

Returns the next probable prime after self, as determined by PARI.

Input:

n
- an integer

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

nth_prime( n)

sage: nth_prime(0)
Traceback (most recent call last):
...
ValueError
sage: nth_prime(3)
5
sage: nth_prime(10)
29

number_of_divisors( n)

Return the number of divisors of the integer n.

odd_part( n)

The odd part of the integer $ n$ . This is $ n / 2^v$ , where $ v =$ valuation(n,2).

power_mod( a, n, m)
The n-th power of a modulo the integer 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

prange( 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:

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]

previous_prime( 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

previous_prime_power( n)

The largest prime power $ < n$ . The result is provably correct. If $ n \leq 2$ , this function returns $ -x$ , where $ x$ is prime power and $ -x < n$ 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

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.

sage: prime_divisors(1)
[]
sage: prime_divisors(100)
[2, 5]
sage: prime_divisors(-100)
[2, 5]
sage: prime_divisors(2004)
[2, 3, 167]

prime_factors( 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]

prime_powers( 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'>

prime_range( 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:

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]

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
- Integer (nonzero)
m
- Integer
Output: Integer

sage: z = 43434
sage: z.prime_to_m_part(20)
21717

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 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]

primes_first_n( n, [leave_pari=False])

Return the first $ n$ primes.

Input:

leave_pari
- bool (default: False) if True the returned list is a PARI list; this is *vastly* (10 times!) 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.
Output: a list of the first $ n$ prime numbers.

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

primitive_root( n)

Return a generator for the multiplicative group of integers modulo $ n$ , 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]

quadratic_residues( n)

Return a sorted list of all squares modulo the integer $ n$ in the range $ 0\leq x < \vert n\vert$ .

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

random_prime( 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:

n
- an integer >= 2.
proof
- bool or None (default: None) If False, the function uses a pseudo-primality test, which is much faster for really big numbers but does not provide a proof of primality. If None, uses the global default (see sage.structure.proof)

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:

rational_reconstruction( 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.

rising_factorial( x, a)

Returns the rising factorial $ (x)^a$ .

The notation in the literature is a mess: often $ (x)^a$ , but there are many other notations: GKP: Concrete Mathematics uses $ x^{\overline{a}}$ .

The rising factorial is also known as the Pochhammer symbol, see Maple and Mathematica.

Definition: for integer $ a \ge 0$ we have $ x(x+1) \cdots (x+a-1)$ . In all other cases we use the GAMMA-function: $ \frac {\Gamma(x+a)} {\Gamma(x)}$ .

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.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)

sigma( 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

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

subfactorial( n)

Subfactorial or rencontres numbers, or derangements: number of permutations of $ n$ elements with no fixed points.

Input:

n
- non negative integer

Output:
integer
- function value

sage: subfactorial(0)
1
sage: subfactorial(1)
0
sage: subfactorial(8)
14833

Author: Jaap Spies (2007-01-23)

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.

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

two_squares( 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.

valuation( 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

xgcd( a, b)

Returns triple (g,s,t) such that g = s*a+t*b = gcd(a,b).

Input:

a, b
- integers or univariate polynomials (or any type with an xgcd method).
Output:
g, s, t
- such that g = s*a + t*b

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))

xlcm( 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

class Moebius
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.

For simplicity, if $ n = 0$ we define $ \mu(n) = 0$ .

IMPLEMENTATION: Factors or - for integers - uses the PARI C library.

Input:

n
- anything that can be factored.

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

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

plot( self, [xmin=0], [xmax=50], [pointsize=30], [rgbcolor=(0, 0, 1)], [join=True])

Plot the Moebius function.

Input:

xmin
- default: 0
xmax
- default: 50
pointsize
- default: 30
rgbcolor
- default: (0,0,1)
join
- default: True; whether to join the points (very helpful in seeing their order).
**kwds
- passed on

range( 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.