Home       Trees       Indices       Help   
Package sage :: Package rings :: Module arith
[hide private]
[frames] | no frames]

Module arith

source code


Miscellaneous arithmetic functions


Classes [hide private]
  Moebius
Returns the value of the Moebius function of abs(n), where n is an integer.
Functions [hide private]
 
algdep(z, n, known_bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., known_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Returns a polynomial of degree at most $n$ which is approximately satisfied by the number $z$.		 source code
 
algebraic_dependency(z, n, known_bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., known_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Returns a polynomial of degree at most $n$ which is approximately satisfied by the number $z$.		 source code
 
bernoulli(n, algorithm='pari')
Return the n-th Bernoulli number, as a rational number.		 source code
 
factorial(n, algorithm='gmp')
Compute the factorial of $n$, which is the product $1\cdot 2\cdot 3 \cdots (n-1) n$.		 source code
 
is_prime(n, flag=0)
Returns True if $x$ is prime, and False otherwise.		 source code
 
is_pseudoprime(n, flag=0)
Returns True if $x$ is a pseudo-prime, and False otherwise.		 source code
 
is_prime_power(n, flag=0)
Returns True if $x$ is a prime power, and False otherwise.		 source code
 
valuation(m, p)
The exact power of p that divides m.		 source code
 
prime_range(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., leave_pari=False)
List of all primes between start and stop-1, inclusive.		 source code
 
prime_powers(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
List of all positive primes powers between start and stop-1, inclusive.		 source code
 
primes_first_n(n, leave_pari=False)
Return the first $n$ primes.		 source code
 
eratosthenes(n)
Return a list of the primes $\leq n$.		 source code
 
prange(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., leave_pari=False)
List of all primes between start and stop-1, inclusive.		 source code
 
primes(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Returns an iterator over all primes between start and stop-1, inclusive.		 source code
 
next_prime_power(n)
The next prime power greater than the integer n.		 source code
 
next_probable_prime(n)
Returns the next probable prime after self, as determined by PARI.		 source code
 
next_prime(n, proof=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
The next prime greater than the integer n.		 source code
 
previous_prime(n)
The largest prime < n.		 source code
 
previous_prime_power(n)
The largest prime power $< n$.		 source code
 
random_prime(n, proof=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Returns a random prime p between 2 and n (i.e.		 source code
 
divisors(n)
Returns a list of all positive integer divisors of the nonzero integer n.		 source code
 
sigma(n, k=1)
Return the sum of the k-th powers of the divisors of n.		 source code
 
gcd(a, b=0, integer=False, **kwargs)
The greatest common divisor of a and b.		 source code
 
GCD(a, b=0, integer=False, **kwargs)
The greatest common divisor of a and b.		 source code
 
lcm(a, b=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., 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.		 source code
 
LCM(a, b=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., 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.		 source code
 
__LCM_list(v)
EXAMPLES:...		 source code
 
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.		 source code
 
__GCD_list(v)
EXAMPLES:...		 source code
 
xgcd(a, b)
Returns triple (g,s,t) such that g = s*a+t*b = gcd(a,b).		 source code
 
XGCD(a, b)
Returns triple (g,s,t) such that g = s*a+t*b = gcd(a,b).		 source code
 
inverse_mod(a, m)
The inverse of the ring element a modulo m.		 source code
 
power_mod(a, n, m)
The n-th power of a modulo the integer m.		 source code
 
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).		 source code
 
_rational_reconstruction_python(a, m) source code
 
mqrr_rational_reconstruction(u, m, T)
Maximal Quotient Rational Reconstruction.		 source code
 
trial_division(n, bound=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Return the smallest prime divisor <= bound of the positive integer n, or n if there is no such prime.		 source code
 
__factor_using_trial_division(n)
Returns the factorization of the integer n as a sorted list of tuples (p,e).		 source code
 
__factor_using_pari(n, int_=False, debug_level=0, proof=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...) source code
 
factor(n, proof=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., int_=False, algorithm='pari', verbose=0, **kwds)
Returns the factorization of the integer n as a sorted list of tuples (p,e).		 source code
 
prime_divisors(n)
The prime divisors of the integer n, sorted in increasing order.		 source code
 
prime_factors(n)
The prime divisors of the integer n, sorted in increasing order.		 source code
 
odd_part(n)
The odd part of the integer $n$.		 source code
 
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.		 source code
 
is_square(n, root=False)
Returns whether or not n is square, and if n is a square also returns the square root.		 source code
 
is_squarefree(n)
Returns True if and only if n is not divisible by the square of an integer > 1.		 source code
 
euler_phi(n)
Return the value of the Euler phi function on the integer n.		 source code
 
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).		 source code
 
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).		 source code
 
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.		 source code
 
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 + ...		 source code
 
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.		 source code
 
binomial(x, m)
Return the binomial coefficient $$ x (x-1) \cdots (x-m+1) / m! $$ which is defined for $m \in \ZZ$ and any $x$.		 source code
 
multinomial(*ks)
Return the multinomial coefficient...		 source code
 
gaussian_binomial(n, k, q=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Return the gaussian binomial $$ \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)}.		 source code
 
kronecker_symbol(x, y)
The Kronecker symbol (x|y).		 source code
 
kronecker(x, y)
Synonym for \code{kronecker_symbol}.		 source code
 
legendre_symbol(x, p)
The Legendre symbol (x|p), for $p$ prime.		 source code
 
primitive_root(n)
Return a generator for the multiplicative group of integers modulo $n$, if one exists.		 source code
 
nth_prime(n)
EXAMPLES: sage: nth_prime(0) Traceback (most recent call last): ...		 source code
 
quadratic_residues(n)
Return a sorted list of all squares modulo the integer $n$ in the range $0\leq x < |n|$.		 source code
 
Max(x)
The maximum of a list of objects, on which a binary max operation is defined.		 source code
 
Min(x)
The minimum of a list of objects, on which a binary min operation is defined.		 source code
 
farey(v, lim)
Return the Farey sequence associated to the floating point number v.		 source code
 
continued_fraction_list(x, partial_convergents=False, bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Returns the continued fraction of x as a list.		 source code
 
convergent(v, n)
Return the n-th continued fraction convergent of the continued fraction defined by the sequence of integers v.		 source code
 
convergents(v)
Return all the partial convergents of a continued fraction defined by the sequence of integers v.		 source code
 
continuant(v, n=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)
Function returns the continuant of the sequence $v$ (list or tuple).		 source code
 
number_of_divisors(n)
Return the number of divisors of the integer n.		 source code
 
hilbert_symbol(a, b, p, algorithm='pari')
Returns 1 if $ax^2 + by^2$ $p$-adically represents a nonzero square, otherwise returns $-1$.		 source code
 
falling_factorial(x, a)
Returns the falling factorial $(x)_a$.		 source code
 
rising_factorial(x, a)
Returns the rising factorial $(x)^a$.		 source code
 
integer_ceil(x)
Return the ceiling of x.		 source code
 
integer_floor(x)
Return the largest integer $\leq x$.		 source code
 
two_squares(n, algorithm='gap')
Write the integer n as a sum of two integer squares if possible; otherwise raise a ValueError.		 source code
 
subfactorial(n)
Subfactorial or rencontres numbers, or derangements: number of permutations of $n$ elements with no fixed points.		 source code
 
is_power_of_two(n)
This function returns True if and only if $n$ is a power of 2...		 source code
 
differences(lis, n=1)
Returns the $n$ successive differences of the elements in $lis$.		 source code
Variables [hide private]
  moebius = The Moebius function
Function Details [hide private]

algdep(z, n, known_bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., known_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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

EXAMPLES:
    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=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., known_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., use_digits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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

EXAMPLES:
    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')

source code  

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

EXAMPLES:
    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

factorial(n, algorithm='gmp')

source code  

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

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

\begin{itemize}
   \item It takes less than a minute to compute the factorial of
      $10^7$ using the GMP algorithm, and the factorial of $10^6$
      takes less than 4 seconds.

   \item The GMP algorithm is faster and more memory efficient
      than the PARI algorithm.  E.g., PARI computes $10^7$
      factorial in 100 seconds on the core duo 2Ghz.

   \item For comparison, computation in Magma $\leq$ 2.12-10 of
         $n!$ is best done using \code{&*[1..n]}.  
         It takes 113 seconds to compute the factorial of $10^7$
         and 6 seconds to compute the factorial of $10^6$.
         Mathematica V5.2 compute the factorial of $10^7$ in
         136 seconds and the factorial of $10^6$ in 7 seconds.
         (Mathematica is notably very efficient at memory usage
         when doing factorial calculations.)
\end{itemize}

is_prime(n, flag=0)

source code  

Returns True if $x$ is prime, and False otherwise.  The result
is proven correct -- \emph{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.}

EXAMPLES::
    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_pseudoprime(n, flag=0)

source code  

Returns True if $x$ is a pseudo-prime, and False otherwise.  The result
is \emph{NOT} proven correct -- \emph{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.}

EXAMPLES::
    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_prime_power(n, flag=0)

source code  

Returns True if $x$ is a prime power, and False otherwise.
The result is proven correct -- \emph{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.


EXAMPLES::
    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

valuation(m, p)

source code  

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.

EXAMPLES:
    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

prime_range(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., leave_pari=False)

source code  

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 \code{prime_range(bound)} to
get all primes up to bound.

EXAMPLES:
    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_powers(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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.

EXAMPLES:
    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'>

primes_first_n(n, leave_pari=False)

source code  

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. 

EXAMPLES:
    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

eratosthenes(n)

source code  

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

This is extremely slow and is for educational purposes only.

prange(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., leave_pari=False)

source code  

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 \code{prime_range(bound)} to
get all primes up to bound.

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

primes(start, stop=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

Returns an iterator over all primes between start and stop-1,
inclusive.  This is much slower than \code{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 \code{next_prime} function
repeatedly, and \code{next_prime} is slow, partly because it
proves correctness.

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

next_prime_power(n)

source code  

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.

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

source code  

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

INPUT:
    n -- an integer

EXAMPLES:
    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)
    1552518092300708935148979488462502555256886017116696611139052038026050952686376886330878408828646477950487730697131073206171580044114814391444287275041181139204454976020849905550265285631598444825262999193716468750892846853816058039

next_prime(n, proof=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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)

EXAMPLES:
    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

previous_prime(n)

source code  

The largest prime < n.  The result is provably
correct.   If n <= 2, this function raises a ValueError.

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

source code  

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.

EXAMPLES:
    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

random_prime(n, proof=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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)

EXAMPLES:
    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:
    -- Jon Hanke: 2006-08-08  (with standard Stein cleanup)
    -- Jonathan Bober: 2007-03-17

divisors(n)

source code  

Returns a list of all positive integer divisors 
of the nonzero integer n.

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

sigma(n, k=1)

source code  

Return the sum of the k-th powers of the divisors of n.

INPUT:
    n -- integer
    k -- integer (default: 1)

OUTPUT:
    integer

EXAMPLES:
    sage: sigma(5)
    6
    sage: sigma(5,2)
    26

AUTHORS:
    -- William Stein: original implementation
    -- Craig Citro (2007-06-01): rewrote for huge speedup

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

gcd(a, b=0, integer=False, **kwargs)

source code  

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.

EXAMPLES:
    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

GCD(a, b=0, integer=False, **kwargs)

source code  

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.

EXAMPLES:
    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=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., integer=False)

source code  

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

EXAMPLES:
    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

LCM(a, b=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., integer=False)

source code  

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

EXAMPLES:
    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

__LCM_list(v)

source code  

EXAMPLES:
    sage: l = ()
    sage: lcm(l)
    1

    This is because lcm(0,x)=0 for all x (by convention)
    sage: lcm(range(100))
    0

    So for the lcm of all integers up to 10 you must do this:
    sage: lcm(range(1,100))
    69720375229712477164533808935312303556800

    Note that the following example does not work in QQ[] as of 2.11:
    sage: R.<X>=ZZ[]
    sage: lcm((2*X+4,2*X^2,2))
    2*X^3 + 4*X^2

xlcm(m, n)

source code  

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.

EXAMPLES:
    sage: xlcm(120,36)
    (360, 40, 9)

__GCD_list(v)

source code  

EXAMPLES:
    sage: l = ()
    sage: gcd(l)
    0
    sage: gcd(range(10))
    1
    sage: X=polygen(QQ)
    sage: gcd((2*X+4,2*X^2,2))
    1
    sage: X=polygen(ZZ)
    sage: gcd((2*X+4,2*X^2,2))
    2

xgcd(a, b)

source code  

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.

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

XGCD(a, b)

source code  

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.

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

inverse_mod(a, m)

source code  

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

power_mod(a, n, m)

source code  
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

rational_reconstruction(a, m, algorithm='fast')

source code  

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.


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

mqrr_rational_reconstruction(u, m, T)

source code  

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.

trial_division(n, bound=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

Return the smallest prime divisor <= bound of the positive integer
n, or n if there is no such prime.  If the optional argument bound
is omitted, then bound=n.

INPUT:
    n -- a positive integer
    bound - (optional) a positive integer

OUTPUT:
    int -- a prime p<=bound that divides n, or n if
           there is no such prime.

EXAMPLES:
    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

__factor_using_trial_division(n)

source code  

Returns the factorization of the integer n as 
a sorted list of tuples (p,e).

INPUT:
    n -- an integer
OUTPUT:
    list -- factorization of n

factor(n, proof=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a..., int_=False, algorithm='pari', verbose=0, **kwds)

source code  

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

prime_divisors(n)

source code  

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.

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

source code  

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.

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

odd_part(n)

source code  

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

prime_to_m_part(n, m)

source code  

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

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

is_square(n, root=False)

source code  

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.

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

euler_phi(n)

source code  

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 \code{euler_phi(n)} is
defined and equals 0.

INPUT:
    n -- an integer

EXAMPLES:

    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

AUTHORS:
    - William Stein
    - Alex Clemesha (2006-01-10): some examples

crt(a, b, m, n)

source code  

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. 

EXAMPLES:
    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(a, b, m, n)

source code  

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. 

EXAMPLES:
    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_list(v, moduli)

source code  

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.

EXAMPLES:
    sage: CRT_list([2,3,2], [3,5,7])
    23

CRT_basis(moduli)

source code  

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

binomial(x, m)

source code  

Return the binomial coefficient
$$
   x (x-1) \cdots (x-m+1) / m!
$$
which is defined for $m \in \ZZ$ 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)
    
EXAMPLES::
    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

multinomial(*ks)

source code  

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

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

AUTHOR: Gabriel Ebner

gaussian_binomial(n, k, q=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

Return the gaussian binomial
$$
   \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)}.
$$ 

EXAMPLES:
    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

kronecker_symbol(x, y)

source code  

The Kronecker symbol (x|y).

INPUT:
    x -- integer
    y -- integer

EXAMPLES:
    sage: kronecker(3,5)
    -1
    sage: kronecker(3,15)
    0
    sage: kronecker(2,15)
    1
    sage: kronecker(-2,15)
    -1

IMPLEMENTATION: Using GMP.

legendre_symbol(x, p)

source code  

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

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

INPUT:
    x -- integer
    p -- an odd prime number

EXAMPLES:
    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

primitive_root(n)

source code  

Return a generator for the multiplicative group of integers
modulo $n$, if one exists.

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

nth_prime(n)

source code  

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

quadratic_residues(n)

source code  

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

EXAMPLES:
    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

farey(v, lim)

source code  

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

continued_fraction_list(x, partial_convergents=False, bits=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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}

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

source code  

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
$$
        v = [a_0, a_1, a_2, \ldots, a_k]
$$
then \code{convergent(v,2)} is the rational number
$$
          a_0 + 1/a_1
$$
and \code{convergent(v,k)} is the rational number 
$$    
        a1 + 1/(a2+1/(...) ... )
$$
represented by the continued fraction.

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

convergents(v)

source code  

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
    
EXAMPLES:
    sage: convergents([2, 1, 2, 1, 1, 4, 1, 1])
    [2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71]

continuant(v, n=['4ti2-20061025', 'R-2.6.0', 'atlas-3.7.37', 'atlas-3.8.1', 'a...)

source code  

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

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

hilbert_symbol(a, b, p, algorithm='pari')

source code  

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)

EXAMPLES:
    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

AUTHORS:
   -- William Stein and David Kohel (2006-01-05)

falling_factorial(x, a)

source code  

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

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

rising_factorial(x, a)

source code  

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

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

integer_ceil(x)

source code  

Return the ceiling of x.

EXAMPLES:
    sage: integer_ceil(5.4)
    6

integer_floor(x)

source code  

Return the largest integer $\leq x$.

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

OUTPUT:
    an Integer

EXAMPLES:
    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

two_squares(n, algorithm='gap')

source code  

Write the integer n as a sum of two integer squares if
possible; otherwise raise a ValueError.

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

subfactorial(n)

source code  

 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

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

 AUTHOR:
     -- Jaap Spies (2007-01-23)

is_power_of_two(n)

source code  

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

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

differences(lis, n=1)

source code  

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

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

   Home       Trees       Indices       Help   
Generated by Epydoc 3.0beta1 on Thu Jul 17 04:23:28 2008 http://epydoc.sourceforge.net