2.9 Miscellaneous arithmetic functions

Module: sage.rings.arith

Module-level Functions

CRT( a, [b=1], [m=1], [n=0])

Use the Chinese Remainder Theorem to find some integer x such that x=a (mod m) and x=b (mod n). Note that x is only well-defined modulo m*n.

sage: crt(2, 1, 3, 5)
-4
sage: crt(13,20,100,301)
-2087

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)

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

The greatest commond divisor of a and b.

sage: GCD(97,100)
1
sage: GCD(97*10^15, 19^20*97^2)
97

LCM( a, [b=None])

The least common multiple of a and b.

sage: LCM(97,100)
9700
sage: LCM(0,2)
0
sage: LCM(-3,-5)
15

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 of integers (g,s,t) such that g = s*a+t*b = gcd(a,b).

sage: xgcd(56, 44)
(4, 4, -5)
sage: 4*56 + (-5)*44
4

__GCD_list( v)

__LCM_list( v)

__factor_using_pari( n, [int_=0], [debug_level=False])

__factor_using_trial_division( n)

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

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

algdep( z, n)

Return algebraic dependency of degree $ n$ satisfied by the number $ z$ .

ALGORITHM: Uses the PARI C-library algdep command.

INPUT:
    z -- real or $p$-adic number
    n -- an integer

sage: algdep(1.888888888888888, 1)
9*x - 17                                  
sage: algdep(0.12121212121212,1)
33*x - 4                                  
sage: algdep(sqrt(2),2)
x^2 - 2

This example involves a $ p$ -adic number.

sage: K = pAdicField(3)
sage: a = K(7/19); a
1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 +
2*3^16 + 3^17 + 2*3^19 + O(3^20)
sage: algdep(a, 1)
19*x - 7

algebraic_dependency( z, n)

Return algebraic dependency of degree $ n$ satisfied by the number $ z$ .

ALGORITHM: Uses the PARI C-library algdep command.

INPUT:
    z -- real or $p$-adic number
    n -- an integer

sage: algdep(1.888888888888888, 1)
9*x - 17                                  
sage: algdep(0.12121212121212,1)
33*x - 4                                  
sage: algdep(sqrt(2),2)
x^2 - 2

This example involves a $ p$ -adic number.

sage: K = pAdicField(3)
sage: a = K(7/19); a
1 + 2*3 + 3^2 + 3^3 + 2*3^4 + 2*3^5 + 3^8 + 2*3^9 + 3^11 + 3^12 + 2*3^15 +
2*3^16 + 3^17 + 2*3^19 + O(3^20)
sage: algdep(a, 1)
19*x - 7

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
        'python' -- use pure Python implementation

sage: bernoulli(12)
-691/2730
sage: bernoulli(50)
495057205241079648212477525/66

We illustrate use of some of the alternative algorithms.

sage: bernoulli(12, algorithm='gap')    
-691/2730
sage: bernoulli(12, algorithm='gp')
-691/2730

Note: If $ 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$ . If $ m<0$ return 0 .

INPUT::
    x -- number
    m -- integer
    
OUTPUT::
    number

:

sage: binomial(5,2)
10
sage: binomial(2,0)
1
sage: binomial(3,-1)
0
sage: binomial(20,10)
184756
sage: binomial(RealField()('2.5'), 2)
1.8750000000000000

continued_fraction( x, [partial_convergents=False])

Returns the continued fraction of x.


\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(45/17)
[2, 1, 1, 1, 5]
sage: continued_fraction(sqrt(2))
[1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1]
sage: continued_fraction(RR(pi), partial_convergents=True)
([3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 3],
 [(3, 1),
  (22, 7),
  (333, 106),
  (355, 113),
  (103993, 33102),
  (104348, 33215),
  (208341, 66317),
  (312689, 99532),
  (833719, 265381),
  (1146408, 364913),
  (4272943, 1360120),
  (5419351, 1725033),
  (80143857, 25510582),
  (245850922, 78256779)])
sage: continued_fraction(e)
Traceback (most recent call last):
...
NotImplementedError: computation of continued fraction of e not
implemented; try computing continued fraction of RR(e) instead
sage: continued_fraction(RR(e))
[2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 11]
sage: print continued_fraction(RealField(200)(e))
[2, 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14, 1, 1,
16, 1, 1, 18, 1, 1, 20, 1, 1, 22, 1, 1, 24, 1, 1, 26, 1, 1, 28, 1, 1, 30,
1, 1, 32, 1, 1, 34, 1, 1, 36, 1, 1, 38, 1, 1]

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=1], [m=1], [n=0])

Use the Chinese Remainder Theorem to find some integer x such that x=a (mod m) and x=b (mod n). Note that x is only well-defined modulo m*n.

sage: crt(2, 1, 3, 5)
-4
sage: crt(13,20,100,301)
-2087

discrete_log_generic( b, a, [ord=None])

Return an integer $ n$ such that $ b^n = a$ , assuming that ord is a multiple of the multiplicative order of $ a$ . If ord is not specified an attempt is made to compute it.

The elements a and b must support exponentiation to a negative power.

If no such $ x$ exits, this function raises a ValueError exception.

ALGORITHM: Baby step giant step.

sage: b = Mod(2,37);  a = b^20
sage: discrete_log_generic(b, a)
20
sage: b = Mod(2,997);  a = b^20
sage: discrete_log_generic(b, a)
20

sage: K = GF(3^6)
sage: b = K.gen()
sage: a = b^210
sage: discrete_log_generic(b, a, K.order()-1)
210

sage: b = Mod(1,37);  a = Mod(2,37)
sage: discrete_log_generic(b, a)
Traceback (most recent call last):
...
ValueError: Log of 2 to the base 1 does not exist.
sage: b = Mod(1,997);  a = Mod(2,997)
sage: discrete_log_generic(b, a)
Traceback (most recent call last):
...
ValueError: Log of 2 to the base 1 does not exist.

Author: William Stein and David Joyner (2005-01-05)

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. Use prime_list(..., leave_pari=True) for an extremely efficient implementation.

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.

sage: euler_phi(1)
1
sage: euler_phi(2)
1
sage: euler_phi(3)
2
sage: euler_phi(12)
4
sage: euler_phi(37)
36

Notice that euler_phi is defined to be 0 on negative numbers and 0.

sage: euler_phi(-1)  
0
sage: euler_phi(0)
0

We verify directly that the phi function is correct for 21.

sage: euler_phi(21)
12
sage: [i for i in range(21) if gcd(21,i) == 1]
[1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]

The length of the list of integers 'i' in range(n) such that the gcd(i,n) == 1 equals euler_phi(n).

sage: len([i for i in range(21) if gcd(21,i) == 1]) == euler_phi(21)
True

Author Log:

factor( n, [proof=0], [int_=pari], [algorithm=False], [verbose=True])

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

INPUT:
    n -- an nonzero integer
    proof -- bool (default: True)
    int_ -- bool (default: False) whether to return answers as Python ints
    algorithm -- string
             * 'pari' -- (default)  use the PARI c library
             * 'kash' -- use KASH computer algebra system (requires
                         the optional kash package be installed)
    verbose -- integer (default 0); pari's debug variable is set to this;
               e.g., set to 4 or 8 to see lots of output during
factorization.
OUTPUT:
    factorization of n

sage: factor(500)
2^2 * 5^3
sage: factor(-20)
-1 * 2^2 * 5

sage: factor(500, algorithm='kash')     # requires optional kash package
2^2 * 5^3

sage: factor(0)
Traceback (most recent call last):
...
ArithmeticError: Prime factorization of 0 not defined.
sage: factor(1)
1
sage: factor(-1)
-1
sage: factor(2004)
2^2 * 3 * 167

sage: factor(2^197 + 1)       # takes a long time
3 * 197002597249 * 1348959352853811313 * 251951573867253012259144010843

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 -- n = (-32) must be nonnegative

PERFORMANCE: This discussion is valid as of April 2006. All timings below are on a Pentium Core Duo 2Ghz MacBook Pro running Linux with a 2.6.16.1 kernel.

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

sage: falling_factorial(10, RR('3.3'))
1310.1163339660077

sage: falling_factorial(10, 10)
3628800
sage: factorial(10)
3628800

sage: falling_factorial(1+i, i)
0.65296549642016677 + 0.34306583981654537*I

sage: falling_factorial(1+i, 4)
2.0000000000000000 + 4.0000000000000000*I

sage: falling_factorial(i, 4)
-10.000000000000000

sage: M = MatrixSpace(ZZ, 4, 4)
sage: A = M([1,0,1,0,1,0,1,0,1,0,10,10,1,0,1,1])
sage: falling_factorial(A, 2) # A(A - I)
[  1   0  10  10]
[  1   0  10  10]
[ 20   0 101 100]
[  2   0  11  10]

sage: x = ZZ['x'].0
sage: falling_factorial(x, 4)
x^4 - 6*x^3 + 11*x^2 - 6*x

Author: Jaap Spies (2006-03-05)

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)

Return the gaussian binomial

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

sage: gaussian_binomial(5,1,2)
31

Author: David Joyner and William Stein

gcd( a, [b=0])

The greatest commond divisor of a and b.

sage: GCD(97,100)
1
sage: GCD(97*10^15, 19^20*97^2)
97

generic_power( a, m, [one=1])

The m-th power of a, where m is a non-negative integer and a is a Python object on which multiplication is defined. The exponentiation is done using the standard binary powering algorithm.

sage: generic_power(2,5)
32
sage: generic_power(RealField()('2.5'),4)
39.062500000000000
sage: generic_power(0,0)
1
sage: generic_power(2,-3)
Traceback (most recent call last):
...
ArithmeticError: 2 cannot be raised to the negative power -3

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)

inverse_mod( a, m)

The inverse of the integer a modulo the integer m.

sage: inverse_mod(7,1)
0
sage: inverse_mod(5,14)
3
sage: inverse_mod(3,-5)
2

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=False], [use_pari=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.
    use_pari -- (default False); whether to use PARI to determine
            if the integer is a power.  this is vastly faster,
            but there is a serious bug in PARI version 2.2.12-beta,
            so using this is not recommended.   Try pari(2).ispower?
            for more details about the bug.

OUTPUT:
    bool -- True or False

IMPLEMENTATION: Calls the PARI isprime and factor (or ispower) functions.

:

sage: is_prime_power(389)
True
sage: is_prime_power(2000)
False
sage: is_prime_power(2)
True
sage: is_prime_power(1024)
True
sage: is_prime_power(-1)   
False
sage: is_prime_power(1)
True
sage: is_prime_power(997^100)
True
sage: is_prime_power(997^100, use_pari=True)
True

is_square( n, [root=False])

Returns whether or not n is square, and if n is a square also returns the square root. If n is not square, also returns None.

INPUT:
    n -- an integer
    root -- whether or not to also return a square root (default: False)
OUTPUT:
    bool -- whether or not a square
    object --

is_squarefree( n)

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

kronecker( a, b)

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

lcm( a, [b=None])

The least common multiple of a and b.

sage: LCM(97,100)
9700
sage: LCM(0,2)
0
sage: LCM(-3,-5)
15

moebius( n)

Returns the value of the Moebius function of abs(n), where n is an integer.

DEFINITION: $ \mu(n)$ is 0 if $ n$ is not square free, and otherwise equals $ (-1)^r$ , where $ n$ has $ r$ distinct prime factors.

INPUT:
    n -- an integer
OUTPUT:
    0, 1, or -1

sage: moebius(-5)
-1
sage: moebius(9)
0
sage: moebius(12)
0
sage: moebius(-35)
1
sage: moebius(-1)
1
sage: moebius(7)
-1

mqrr_rational_reconstruction( u, m, T)

Maximal Quotient Rational Reconstruction.

Input: u, m, and T are integers and m > u>=0, T>0. Output: Either integer n,d such that d>0, gcd(n,d)=1, n/d=u (mod m), and T*abs(n)*d < m, or None.

Reference: Monagan, Maximal Quotient Rational Reconstruction: An Almost Optimal Algorithm for Rational Reconstruction (page 11) This algorithm is probabilistic.

next_prime( n, [proof=True])

The next prime greater than the integer n. If n is prime, then this function does not return n, but the next prime after n. If the optional argument proof is false (the default), this function only returns a pseudo-prime, as defined by the PARI nextprime function.

INPUT:
    n -- integer
    proof -- bool (default: True)

sage: next_prime(-100)
2

Notice that the next_prime(5) is not 5 but 7.

sage: next_prime(5)
7
sage: next_prime(2004)
2011

number_of_divisors( n)

Return the number of divisors of the integer n.

number_of_primes( x)

Return the number of primes $ \leq x$ .

sage: prime_pi(7)
4
sage: prime_pi(100)
25
sage: prime_pi(1000)
168
sage: prime_pi(100000)
9592

odd_part( n)

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

partitions( n)

Generate the partitions of an integer.

INPUT:
    n -- int

» partitions(3) <generator object at 0xab3b3eac>

sage: list(partitions(3))
[(1, 1, 1), (1, 2), (3,)]

Author: David Eppstein, Jan Van lent, George Yoshida; Python Cookbook 2, Recipe 19.16.

power_mod( a, m, n)
The m-th power of a modulo the integer n.
sage: power_mod(0,0,5)
1
sage: power_mod(2,390,391)
285
sage: power_mod(2,-1,7)
4

prange( start, [stop=False], [leave_pari=None])

List of all primes between start and stop-1, inclusive. If the second argument is omitted, returns the primes up to the first argument.

Use this function when both start and stop are not too large, since in all cases this function makes a table of primes up to stop. If both are large, use the primes iterator function instead.

INPUT:
    start -- lower bound
    stop -- upper bound
    leave_pari -- bool (default: False) if True the returned list
                is a PARI list; this is *vastly* faster since the
                time of prime_range is dominated by conversion
                from PARI to SAGE integers.   However, PARI integers
                are much different than SAGE integers.
                If you use this option the lower bound must be 2.

You can also call this function with prime_range(bound) to get all primes up to bound.

sage: prime_range(10)
[2, 3, 5, 7]
sage: prime_range(7)
[2, 3, 5]
sage: prime_range(2000,2020)
[2003, 2011, 2017]
sage: prime_range(2,2)
[]
sage: prime_range(2,3)
[2]
sage: prime_range(10)
[2, 3, 5, 7]

previous_prime( n)

The largest prime < n. The result is provably correct. If n <= 2, this function returns -p, where p is prime and -p < n and no larger negative of a prime has this property.

sage: previous_prime(10)
7
sage: previous_prime(7)
5
sage: previous_prime(8)
7
sage: previous_prime(7)
5
sage: previous_prime(5)
3
sage: previous_prime(3)
2
sage: previous_prime(2)
-2
sage: previous_prime(1)
-2
sage: previous_prime(-20)
-23

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_pi( x)

Return the number of primes $ \leq x$ .

sage: prime_pi(7)
4
sage: prime_pi(100)
25
sage: prime_pi(1000)
168
sage: prime_pi(100000)
9592

prime_range( start, [stop=False], [leave_pari=None])

List of all primes between start and stop-1, inclusive. If the second argument is omitted, returns the primes up to the first argument.

Use this function when both start and stop are not too large, since in all cases this function makes a table of primes up to stop. If both are large, use the primes iterator function instead.

INPUT:
    start -- lower bound
    stop -- upper bound
    leave_pari -- bool (default: False) if True the returned list
                is a PARI list; this is *vastly* faster since the
                time of prime_range is dominated by conversion
                from PARI to SAGE integers.   However, PARI integers
                are much different than SAGE integers.
                If you use this option the lower bound must be 2.

You can also call this function with prime_range(bound) to get all primes up to bound.

sage: prime_range(10)
[2, 3, 5, 7]
sage: prime_range(7)
[2, 3, 5]
sage: prime_range(2000,2020)
[2003, 2011, 2017]
sage: prime_range(2,2)
[]
sage: prime_range(2,3)
[2]
sage: prime_range(10)
[2, 3, 5, 7]

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

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(10000000000, 10000000100))
[10000000019, 10000000033, 10000000061, 10000000069, 10000000097]

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

rational_reconstruction( a, m)

This function tries to compute a pair (x,y), where x/y is a rational number is lowest terms such that reduction of x/y modulo m is equal to a and the absolute values of x and y are both <= sqrt(m/2). If such a pair exists, that pair is unique and this function returns it. If no such pair exists, this function return the pair (0,0).

The efficient algorithm for computing rational reconstruction is very similar to the extended Euclidean algorithm. For more details, see Knuth, Vol 2, 3rd ed, pages 656-657.

:

sage: m = 100000
sage: (119*inverse_mod(53,m))%m
11323
sage: rational_reconstruction(11323,m)
(119, 53)

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

sage: rising_factorial(10,RR('3.3'))
2826.3889582496449

sage: rising_factorial(1+i, i)
0.26681639063783236 + 0.12278335400637194*I

sage: rising_factorial(i, 4)
-10.000000000000000

See falling_factorial(i, 4)!

sage: x = PolynomialRing(IntegerRing(),'x').gen()
sage: rising_factorial(x, 4)
x^4 + 6*x^3 + 11*x^2 + 6*x

Author: Jaap Spies (2006-03-05)

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

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

valuation( m, p)

The exact power of p>0 that divides the integer m. We do not require that p be prime, and if m is 0, then this function returns rings.infinity.

:

sage: valuation(512,2)
9
sage: valuation(1,2)
0

Valuation of 0 is defined, but valuation with respect to 0 is not::

sage: valuation(0,7)
Infinity
sage: valuation(3,0)
Traceback (most recent call last):
...
ValueError: valuation at 0 not defined

Here are some other example::

sage: valuation(100,10)
2
sage: valuation(200,10)
2
sage: valuation(243,3)
5
sage: valuation(243*10007,3)
5
sage: valuation(243*10007,10007)
1

xgcd( a, b)

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

sage: xgcd(56, 44)
(4, 4, -5)
sage: 4*56 + (-5)*44
4

See About this document... for information on suggesting changes.