Module: sage.rings.integer
Elements of the ring
of integers
Author: William Stein (2005): initial version
- Gonzalo Tornaria (2006-03-02): vastly improved python/GMP conversion; hashing - Didier Deshommes <dfdeshom@gmail.com> (2006-03-06): numerous examples and docstrings - William Stein (2006-03-31): changes to reflect GMP bug fixes - William Stein (2006-04-14): added GMP factorial method (since it's now very fast). - David Harvey (2006-09-15): added nth_root, exact_log - David Harvey (2006-09-16): attempt to optimise Integer constructor - Rishikesh (2007-02-25): changed quo_rem so that the rem is positive - David Harvey, Martin Albrecht, Robert Bradshaw (2007-03-01): optimized Integer constructor and pool - Pablo De Napoli (2007-04-01): multiplicative_order should return +infinity for non zero numbers - Robert Bradshaw (2007-04-12): is_perfect_power, Jacobi symbol (with Kronecker extension). Convert some methods to use GMP directly rather than pari, Integer() -> PY_NEW(Integer) - David Roe (2007-03-21): sped up valuation and is_square, added val_unit, is_power, is_power_of and divide_knowing_divisible_by - Robert Bradshaw (2008-03-26): gamma function, multifactorials
Add 2 integers:
sage: a = Integer(3) ; b = Integer(4) sage: a + b == 7 True
Add an integer and a real number:
sage: a + 4.0 7.00000000000000
Add an integer and a rational number:
sage: a + Rational(2)/5 17/5
Add an integer and a complex number:
sage: b = ComplexField().0 + 1.5 sage: loads((a+b).dumps()) == a+b True
sage: z = 32 sage: -z -32 sage: z = 0; -z 0 sage: z = -0; -z 0 sage: z = -1; -z 1
Multiplication:
sage: a = Integer(3) ; b = Integer(4) sage: a * b == 12 True sage: loads((a * 4.0).dumps()) == a*b True sage: a * Rational(2)/5 6/5
sage: list([2,3]) * 4 [2, 3, 2, 3, 2, 3, 2, 3]
sage: 'sage'*Integer(3) 'sagesagesage'
COERCIONS: Returns version of this integer in the multi-precision floating real field R.
sage: n = 9390823 sage: RR = RealField(200) sage: RR(n) 9.3908230000000000000000000000000000000000000000000000000000e6
Module-level Functions
) |
Return the GCD of a list v of integers. Element of v is converted to a SAGE integer if it isn't one already.
This function is used, e.g., by rings/arith.py
Input:
sage: from sage.rings.integer import GCD_list sage: w = GCD_list([3,9,30]); w 3 sage: type(w) <type 'sage.rings.integer.Integer'>
The inputs are converted to SAGE integers.
sage: w = GCD_list([int(3), int(9), '30']); w 3 sage: type(w) <type 'sage.rings.integer.Integer'>
) |
Return the LCM of a list v of integers. Element of v is converted to a SAGE integer if it isn't one already.
This function is used, e.g., by rings/arith.py
Input:
sage: from sage.rings.integer import LCM_list sage: w = LCM_list([3,9,30]); w 90 sage: type(w) <type 'sage.rings.integer.Integer'>
The inputs are converted to SAGE integers.
sage: w = LCM_list([int(3), int(9), '30']); w 90 sage: type(w) <type 'sage.rings.integer.Integer'>
) |
) |
) |
) |
) |
Return true if x is of the SAGE integer type.
sage: is_Integer(2) True sage: is_Integer(2/1) False sage: is_Integer(int(2)) False sage: is_Integer(long(2)) False sage: is_Integer('5') False
) |
Create a SAGE integer from the base-32 Python *string* s. This is used in unpickling integers.
sage: from sage.rings.integer import make_integer sage: make_integer('-29') -73 sage: make_integer(29) Traceback (most recent call last): ... TypeError: expected string or Unicode object, sage.rings.integer.Integer found
) |
Class: int_to_Z
Special Functions: __init__,
_repr_type
) |
Class: Integer
Integer() interprets numbers and strings that begin with 0 as octal numbers, and numbers and strings that begin with 0x as hexadecimal numbers.
mpz_t
integer type.
sage: Integer(010) 8 sage: Integer(0x10) 16 sage: Integer(10) 10 sage: Integer('0x12') 18 sage: Integer('012') 10
) |
You can create an integer from an int, long, string literal, or integer modulo N.
sage: Integer(495) 495 sage: Integer('495949209809328523') 495949209809328523 sage: Integer(Mod(3,7)) 3 sage: 2^3 8
Functions: additive_order,
binary,
bits,
ceil,
coprime_integers,
crt,
denominator,
digits,
divide_knowing_divisible_by,
divides,
divisors,
exact_log,
factor,
factorial,
floor,
gamma,
gcd,
inverse_mod,
inverse_of_unit,
is_integral,
is_irreducible,
is_one,
is_perfect_power,
is_power,
is_power_of,
is_prime,
is_prime_power,
is_pseudoprime,
is_square,
is_squarefree,
is_unit,
isqrt,
jacobi,
kronecker,
list,
multifactorial,
multiplicative_order,
ndigits,
next_prime,
next_probable_prime,
nth_root,
numerator,
ord,
powermod,
powermodm_ui,
prime_divisors,
prime_factors,
prime_to_m_part,
quo_rem,
radical,
rational_reconstruction,
sqrt,
sqrt_approx,
squarefree_part,
str,
val_unit,
valuation
) |
Return the additive order of self.
sage: ZZ(0).additive_order() 1 sage: ZZ(1).additive_order() +Infinity
) |
Return the binary digits of self as a string.
sage: print Integer(15).binary() 1111 sage: print Integer(16).binary() 10000 sage: print Integer(16938402384092843092843098243).binary() 110110101110110001111000111001001010011101000110101000111111100010100000000 0101111000010000011
) |
Return the number of bits in self.
sage: 500.bits() 9 sage: 5.bits() 3 sage: 12345.bits() == len(12345.binary()) True
) |
Return the ceiling of self, which is self since self is an integer.
sage: n = 6 sage: n.ceil() 6
) |
Return the positive integers
that are coprime to self.
sage: n = 8 sage: n.coprime_integers(8) [1, 3, 5, 7] sage: n.coprime_integers(11) [1, 3, 5, 7, 9] sage: n = 5; n.coprime_integers(10) [1, 2, 3, 4, 6, 7, 8, 9] sage: n.coprime_integers(5) [1, 2, 3, 4] sage: n = 99; n.coprime_integers(99) [1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 43, 46, 47, 49, 50, 52, 53, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 73, 74, 76, 79, 80, 82, 83, 85, 86, 89, 91, 92, 94, 95, 97, 98]
Author: Naqi Jaffery (2006-01-24): examples
ALGORITHM: Naive - compute lots of GCD's. If this isn't good enough for you, please code something better and submit a patch.
) |
Return the unique integer between 0
and
that is
congruent to the integer modulo
and to
modulo
. We
assume that
and
are coprime.
sage: n = 17 sage: m = n.crt(5, 23, 11); m 247 sage: m%23 17 sage: m%11 5
) |
Return the denominator of this integer.
sage: x = 5 sage: x.denominator() 1 sage: x = 0 sage: x.denominator() 1
) |
Return a list of digits for self in the given base in little endian order.
The return is unspecified if self is a negative number and the digits are given.
Input:
sage: 5.digits() [1, 0, 1] sage: 5.digits(digits=["zero","one"]) ['one', 'zero', 'one'] sage: 5.digits(3) [2, 1] sage: 0.digits(base=10) # 0 has 0 digits [] sage: 0.digits(base=2) # 0 has 0 digits [] sage: 10.digits(16,'0123456789abcdef') ['a'] sage: 0.digits(16,'0123456789abcdef') [] sage: 0.digits(16,'0123456789abcdef',padto=1) ['0'] sage: 123.digits(base=10,padto=5) [3, 2, 1, 0, 0] sage: 123.digits(base=2,padto=3) # padto is the minimal length [1, 1, 0, 1, 1, 1, 1] sage: 123.digits(base=2,padto=10,digits=(1,-1)) [-1, -1, 1, -1, -1, -1, -1, 1, 1, 1] sage: a=9939082340; a.digits(10) [0, 4, 3, 2, 8, 0, 9, 3, 9, 9] sage: a.digits(512) [100, 302, 26, 74] sage: (-12).digits(10) [-2, -1] sage: (-12).digits(2) [0, 0, -1, -1]
We support large bases
sage: n=2^6000 sage: n.digits(2^3000) [0, 0, 1]
sage: base=3; n=25 sage: l=n.digits(base) sage: # the next relationship should hold for all n,base sage: sum(base^i*l[i] for i in range(len(l)))==n True sage: base=3; n=-30; l=n.digits(base); sum(base^i*l[i] for i in range(len(l)))==n True
Note: In some cases it is faster to give a digits collection. This would be particularly true for computing the digits of a series of small numbers. In these cases, the code is careful to allocate as few python objects as reasonably possible.
sage: digits = range(15) sage: l=[ZZ(i).digits(15,digits) for i in range(100)] sage: l[16] [1, 1]
This function is comparable to str
for speed.
sage: n=3^100000 sage: n.digits(base=10)[-1] # slightly slower than str 1 sage: n=10^10000 sage: n.digits(base=10)[-1] # slightly faster than str 1
Author: Joel B. Mohler significantly rewrote this entire function (2008-03-02)
) |
Returns the integer self / right when self is divisible by right.
If self is not divisible by right, the return value is undefined, and may not even be close to self/right for multi-word integers.
sage: a = 8; b = 4 sage: a.divide_knowing_divisible_by(b) 2 sage: (100000).divide_knowing_divisible_by(25) 4000 sage: (100000).divide_knowing_divisible_by(26) # close (random) 3846
However, often it's way off.
sage: a = 2^70; a 1180591620717411303424 sage: a // 11 # floor divide 107326510974310118493 sage: a.divide_knowing_divisible_by(11) # way off and possibly random 43215361478743422388970455040
) |
Return True if self divides n.
sage: Z = IntegerRing() sage: Z(5).divides(Z(10)) True sage: Z(0).divides(Z(5)) False sage: Z(10).divides(Z(5)) False
) |
Returns a list of all positive integer divisors of the integer self.
sage: a = -3; a.divisors() [1, 3] sage: a = 6; a.divisors() [1, 2, 3, 6] sage: a = 28; a.divisors() [1, 2, 4, 7, 14, 28] sage: a = 2^5; a.divisors() [1, 2, 4, 8, 16, 32] sage: a = 100; a.divisors() [1, 2, 4, 5, 10, 20, 25, 50, 100] sage: a = 1; a.divisors() [1] sage: a = 0; a.divisors() Traceback (most recent call last): ... ValueError: n must be nonzero sage: a = 2^3 * 3^2 * 17; a.divisors() [1, 2, 3, 4, 6, 8, 9, 12, 17, 18, 24, 34, 36, 51, 68, 72, 102, 136, 153, 204, 306, 408, 612, 1224]
) |
Returns the largest integer
such that
self
, i.e.,
the floor of
self
.
This is guaranteed to return the correct answer even when the usual log function doesn't have sufficient precision.
Input:
Author: David Harvey (2006-09-15)
TODO: - Currently this is extremely stupid code (although it should always work). Someone needs to think about doing this properly by estimating errors in the log function etc.
sage: Integer(125).exact_log(5) 3 sage: Integer(124).exact_log(5) 2 sage: Integer(126).exact_log(5) 3 sage: Integer(3).exact_log(5) 0 sage: Integer(1).exact_log(5) 0
sage: x = 3^100000 sage: RR(log(RR(x), 3)) 100000.000000000 sage: RR(log(RR(x + 100000), 3)) 100000.000000000
sage: x.exact_log(3) 100000 sage: (x+1).exact_log(3) 100000 sage: (x-1).exact_log(3) 99999
sage: x.exact_log(2.5) Traceback (most recent call last): ... TypeError: Attempt to coerce non-integral RealNumber to Integer
) |
Return the prime factorization of the integer as a list of
pairs
, where
is prime and
is a positive integer.
Input:
sage: n = 2^100 - 1; n.factor() 3 * 5^3 * 11 * 31 * 41 * 101 * 251 * 601 * 1801 * 4051 * 8101 * 268501
We using proof=False, which doesn't prove correctness of the primes that appear in the factorization:
sage: n = 920384092842390423848290348203948092384082349082 sage: n.factor(proof=False) 2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173 sage: n.factor(proof=True) 2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173
We factor using trial division only:
sage: n.factor(limit=1000) 2 * 11 * 41835640583745019265831379463815822381094652231
) |
Return the factorial
.
Self must fit in an
unsigned long int
.
sage: for n in srange(7): ... print n, n.factorial() 0 1 1 1 2 2 3 6 4 24 5 120 6 720
) |
Return the floor of self, which is just self since self is an integer.
sage: n = 6 sage: n.floor() 6
) |
The gamma function on integers is the factorial function (shifted by
one) on positive integers, and
on non-positive integers.
sage: gamma(5) 24 sage: gamma(0) -Infinity sage: gamma(-1) +Infinity sage: gamma(-2^150) -Infinity
) |
Return the greatest common divisor of self and
.
sage: gcd(-1,1) 1 sage: gcd(0,1) 1 sage: gcd(0,0) 0 sage: gcd(2,2^6) 2 sage: gcd(21,2^6) 1
) |
Returns the inverse of self modulo
, if this inverse exists.
Otherwise, raises a ZeroDivisionError exception.
Input:
sage: a = Integer(189) sage: a.inverse_mod(10000) 4709 sage: a.inverse_mod(-10000) 4709 sage: a.inverse_mod(1890) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist. sage: a = Integer(19)**100000 sage: b = a*a sage: c = a.inverse_mod(b) Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
) |
Return inverse of self if self is a unit in the integers, i.e., self is -1 or 1. Otherwise, raise a ZeroDivisionError.
sage: (1).inverse_of_unit() 1 sage: (-1).inverse_of_unit() -1 sage: 5.inverse_of_unit() Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist. sage: 0.inverse_of_unit() Traceback (most recent call last): ... ZeroDivisionError: Inverse does not exist.
) |
Return True
since integers are integral, i.e., satisfy
a monic polynomial with integer coefficients.
sage: Integer(3).is_integral() True
) |
Returns True
if self is irreducible, i.e. +/- prime
sage: z = 2^31 - 1 sage: z.is_irreducible() True sage: z = 2^31 sage: z.is_irreducible() False sage: z = 7 sage: z.is_irreducible() True sage: z = -7 sage: z.is_irreducible() True
) |
Returns True
if the integers is
, otherwise
False
.
sage: Integer(1).is_one() True sage: Integer(0).is_one() False
) |
Returns True
if self is a perfect power.
sage: z = 8 sage: z.is_perfect_power() True sage: z = 144 sage: z.is_perfect_power() True sage: z = 10 sage: z.is_perfect_power() False
) |
Returns True
if self is a perfect power, ie if there
exist integers a and b,
with
.
sage: Integer(-27).is_power() True sage: Integer(12).is_power() False
) |
Returns True
if there is an integer b with
.
sage: Integer(64).is_power_of(4) True sage: Integer(64).is_power_of(16) False
TESTS:
sage: Integer(-64).is_power_of(-4) True sage: Integer(-32).is_power_of(-2) True sage: Integer(1).is_power_of(1) True sage: Integer(-1).is_power_of(-1) True sage: Integer(0).is_power_of(1) False sage: Integer(0).is_power_of(0) True sage: Integer(1).is_power_of(0) True sage: Integer(1).is_power_of(8) True sage: Integer(-8).is_power_of(2) False
NOTES:
For large integers self, is_power_of() is faster than is_power(). The following examples gives some indication of how much faster.
sage: b = lcm(range(1,10000)) sage: b.exact_log(2) 14446 sage: t=cputime() sage: for a in range(2, 1000): k = b.is_power() sage: cputime(t) # random 0.53203299999999976 sage: t=cputime() sage: for a in range(2, 1000): k = b.is_power_of(2) sage: cputime(t) # random 0.0 sage: t=cputime() sage: for a in range(2, 1000): k = b.is_power_of(3) sage: cputime(t) # random 0.032002000000000308
sage: b = lcm(range(1, 1000)) sage: b.exact_log(2) 1437 sage: t=cputime() sage: for a in range(2, 10000): k = b.is_power() # note that we change the range from the example above sage: cputime(t) # random 0.17201100000000036 sage: t=cputime(); TWO=int(2) sage: for a in range(2, 10000): k = b.is_power_of(TWO) sage: cputime(t) # random 0.0040000000000000036 sage: t=cputime() sage: for a in range(2, 10000): k = b.is_power_of(3) sage: cputime(t) # random 0.040003000000000011 sage: t=cputime() sage: for a in range(2, 10000): k = b.is_power_of(a) sage: cputime(t) # random 0.02800199999999986
) |
Returns True
if self is prime.
NOTE: Integer primes are by definition positive!
This is different than Magma, but the same as in Pari.
See also the is_irreducible()
method.
sage: z = 2^31 - 1 sage: z.is_prime() True sage: z = 2^31 sage: z.is_prime() False sage: z = 7 sage: z.is_prime() True sage: z = -7 sage: z.is_prime() False sage: z.is_irreducible() True
) |
Returns True if
is a prime power, and False otherwise.
Input:
sage: (-10).is_prime_power() False sage: (10).is_prime_power() False sage: (64).is_prime_power() True sage: (3^10000).is_prime_power() True sage: (10000).is_prime_power(flag=1) False
) |
Returns True
if self is a pseudoprime
sage: z = 2^31 - 1 sage: z.is_pseudoprime() True sage: z = 2^31 sage: z.is_pseudoprime() False
) |
Returns True
if self is a perfect square
sage: Integer(4).is_square() True sage: Integer(41).is_square() False
) |
Returns True if this integer is not divisible by the square of any prime and False otherwise.
sage: Integer(100).is_squarefree() False sage: Integer(102).is_squarefree() True
) |
Returns true
if this integer is a unit, i.e., 1 or
.
sage: for n in srange(-2,3): ... print n, n.is_unit() -2 False -1 True 0 False 1 True 2 False
) |
Returns the integer floor of the square root of self, or raises an ValueError if self is negative.
sage: a = Integer(5) sage: a.isqrt() 2
sage: Integer(-102).isqrt() Traceback (most recent call last): ... ValueError: square root of negative integer not defined.
) |
Calculate the Jacobi symbol
.
sage: z = -1 sage: z.jacobi(17) 1 sage: z.jacobi(19) -1 sage: z.jacobi(17*19) -1 sage: (2).jacobi(17) 1 sage: (3).jacobi(19) -1 sage: (6).jacobi(17*19) -1 sage: (6).jacobi(33) 0 sage: a = 3; b = 7 sage: a.jacobi(b) == -b.jacobi(a) True
) |
Calculate the Kronecker symbol
with the Kronecker extension
when self odd, or
when
even.
sage: z = 5 sage: z.kronecker(41) 1 sage: z.kronecker(43) -1 sage: z.kronecker(8) -1 sage: z.kronecker(15) 0 sage: a = 2; b = 5 sage: a.kronecker(b) == b.kronecker(a) True
) |
Return a list with this integer in it, to be compatible with the method for number fields.
sage: m = 5 sage: m.list() [5]
) |
Computes the k-th factorial
of self. For k=1 this is the
standard factorial, and for k greater than one it is the product of
every k-th terms down from self to k. The recursive definition is used
to extend this function to the negative integers.
sage: 5.multifactorial(1) 120 sage: 5.multifactorial(2) 15 sage: 23.multifactorial(2) 316234143225 sage: prod([1..23, step=2]) 316234143225 sage: (-29).multifactorial(7) 1/2640
) |
Return the multiplicative order of self.
sage: ZZ(1).multiplicative_order() 1 sage: ZZ(-1).multiplicative_order() 2 sage: ZZ(0).multiplicative_order() +Infinity sage: ZZ(2).multiplicative_order() +Infinity
) |
Return the number of digits of self expressed in the given base.
Input:
sage: n = 52 sage: n.ndigits() 2 sage: n = -10003 sage: n.ndigits() 5 sage: n = 15 sage: n.ndigits(2) 4 sage: n=1000**1000000+1 sage: n.ndigits() 3000001 sage: n=1000**1000000-1 sage: n.ndigits() 3000000 sage: n=10**10000000-10**9999990 sage: n.ndigits() 10000000
) |
Returns the next prime after self.
Input:
sage: Integer(100).next_prime() 101
Use Proof = False, which is way faster:
sage: b = (2^1024).next_prime(proof=False)
sage: Integer(0).next_prime() 2 sage: Integer(1001).next_prime() 1009
) |
Returns the next probable prime after self, as determined by PARI.
sage: (-37).next_probable_prime() 2 sage: (100).next_probable_prime() 101 sage: (2^512).next_probable_prime() 134078079299425970995740249982058461274793658205923933777235614437217640300 735469768018742981669034276900318581864860508537538828119465699464336490060 84171 sage: 0.next_probable_prime() 2 sage: 126.next_probable_prime() 127 sage: 144168.next_probable_prime() 144169
) |
Returns the truncated nth root of self.
Input:
If report_exact is 1, then returns the nth root and a boolean indicating whether the root extraction was exact.
Author: David Harvey (2006-09-15)
sage: Integer(125).nth_root(3) 5 sage: Integer(124).nth_root(3) 4 sage: Integer(126).nth_root(3) 5
sage: Integer(-125).nth_root(3) -5 sage: Integer(-124).nth_root(3) -4 sage: Integer(-126).nth_root(3) -5
sage: Integer(125).nth_root(2, True) (11, False) sage: Integer(125).nth_root(3, True) (5, True)
sage: Integer(125).nth_root(-5) Traceback (most recent call last): ... ValueError: n (=-5) must be positive
sage: Integer(-25).nth_root(2) Traceback (most recent call last): ... ValueError: cannot take even root of negative number
) |
Return the numerator of this integer.
sage: x = 5 sage: x.numerator() 5
sage: x = 0 sage: x.numerator() 0
) |
sage: n=12 sage: n.ord(3) 1
) |
Compute self**exp modulo mod.
sage: z = 2 sage: z.powermod(31,31) 2 sage: z.powermod(0,31) 1 sage: z.powermod(-31,31) == 2^-31 % 31 True
As expected, the following is invalid:
sage: z.powermod(31,0) Traceback (most recent call last): ... ZeroDivisionError: cannot raise to a power modulo 0
) |
Computes self**exp modulo mod, where exp is an unsigned long integer.
sage: z = 32 sage: z.powermodm_ui(2, 4) 0 sage: z.powermodm_ui(2, 14) 2 sage: z.powermodm_ui(2^32-2, 14) 2 sage: z.powermodm_ui(2^32-1, 14) Traceback (most recent call last): # 32-bit ... # 32-bit OverflowError: exp (=4294967295) must be <= 4294967294 # 32-bit 8 # 64-bit sage: z.powermodm_ui(2^65, 14) Traceback (most recent call last): ... OverflowError: exp (=36893488147419103232) must be <= 4294967294 # 32-bit OverflowError: exp (=36893488147419103232) must be <= 18446744073709551614 # 64-bit
) |
The prime divisors of self, 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: a = 1; a.prime_divisors() [] sage: a = 100; a.prime_divisors() [2, 5] sage: a = -100; a.prime_divisors() [2, 5] sage: a = 2004; a.prime_divisors() [2, 3, 167]
) |
The prime divisors of self, 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: a = 1; a.prime_divisors() [] sage: a = 100; a.prime_divisors() [2, 5] sage: a = -100; a.prime_divisors() [2, 5] sage: a = 2004; a.prime_divisors() [2, 3, 167]
) |
Returns the prime-to-m part of self, i.e., the largest divisor of self that is coprime to m.
Input:
sage: z = 43434 sage: z.prime_to_m_part(20) 21717
) |
Returns the quotient and the remainder of self divided by other. Note that the remainder returned is always either zero or of the same sign as other.
Input:
sage: z = Integer(231) sage: z.quo_rem(2) (115, 1) sage: z.quo_rem(-2) (-116, -1) sage: z.quo_rem(0) Traceback (most recent call last): ... ZeroDivisionError: other (=0) must be nonzero
) |
Return the product of the prime divisors of self.
If self is 0, returns 1.
sage: Integer(10).radical() 10 sage: Integer(20).radical() 10 sage: Integer(-20).radical() -10 sage: Integer(0).radical() 1 sage: Integer(36).radical() 6
) |
Return the rational reconstruction of this integer modulo m, i.e., the unique (if it exists) rational number that reduces to self modulo m and whose numerator and denominator is bounded by sqrt(m/2).
sage: (3/7)%100 29 sage: (29).rational_reconstruction(100) 3/7
) |
The square root function.
Input:
sage: Integer(144).sqrt() 12 sage: Integer(102).sqrt() sqrt(102)
sage: n = 2 sage: n.sqrt(all=True) [sqrt(2), -sqrt(2)] sage: n.sqrt(prec=10) 1.4 sage: n.sqrt(prec=100) 1.4142135623730950488016887242 sage: n.sqrt(prec=100,all=True) [1.4142135623730950488016887242, -1.4142135623730950488016887242] sage: n.sqrt(extend=False) Traceback (most recent call last): ... ValueError: square root of 2 not an integer sage: Integer(144).sqrt(all=True) [12, -12] sage: Integer(0).sqrt(all=True) [0]
) |
sage: 5.sqrt_approx(prec=200) 2.2360679774997896964091736687312762354406183596115257242709 sage: 5.sqrt_approx() 2.23606797749979 sage: 4.sqrt_approx() 2
) |
Return the square free part of
(=self), i.e., the unique
integer
that
, with
a perfect square and
square-free.
Use self.radical()
for the product of the primes that
divide self.
If self is 0, just returns 0.
sage: squarefree_part(100) 1 sage: squarefree_part(12) 3 sage: squarefree_part(17*37*37) 17 sage: squarefree_part(-17*32) -34 sage: squarefree_part(1) 1 sage: squarefree_part(-1) -1 sage: squarefree_part(-2) -2 sage: squarefree_part(-4) -1
) |
Return the string representation of self
in the given
base.
sage: Integer(2^10).str(2) '10000000000' sage: Integer(2^10).str(17) '394'
sage: two=Integer(2) sage: two.str(1) Traceback (most recent call last): ... ValueError: base (=1) must be between 2 and 36
sage: two.str(37) Traceback (most recent call last): ... ValueError: base (=37) must be between 2 and 36
sage: big = 10^5000000 sage: s = big.str() # long time (> 20 seconds) sage: len(s) # long time (depends on above defn of s) 5000001 sage: s[:10] # long time (depends on above defn of s) '1000000000'
) |
Returns a pair: the p-adic valuation of self, and the p-adic unit of self.
Input:
self
self
/
sage: n = 60 sage: n.val_unit(2) (2, 15) sage: n.val_unit(3) (1, 20) sage: n.val_unit(7) (0, 60) sage: (2^11).val_unit(4) (5, 2) sage: 0.val_unit(2) (+Infinity, 1)
) |
Return the p-adic valuation of self.
Input:
sage: n = 60 sage: n.valuation(2) 2 sage: n.valuation(3) 1 sage: n.valuation(7) 0 sage: n.valuation(1) Traceback (most recent call last): ... ValueError: You can only compute the valuation with respect to a integer larger than 1.
We do not require that p is a prime:
sage: (2^11).valuation(4) 5
Special Functions: __abs__,
__and__,
__copy__,
__eq__,
__float__,
__floordiv__,
__ge__,
__gt__,
__hex__,
__index__,
__init__,
__int__,
__invert__,
__le__,
__long__,
__lshift__,
__lt__,
__mod__,
__ne__,
__oct__,
__or__,
__pos__,
__pow__,
__rand__,
__reduce__,
__repr__,
__rfloordiv__,
__rlshift__,
__rmod__,
__ror__,
__rpow__,
__rrshift__,
__rshift__,
_factor_trial_division,
_im_gens_,
_interface_init_,
_l_action,
_latex_,
_lcm,
_mathml_,
_pari_,
_r_action,
_rpy_,
_xgcd
) |
Computes
sage: z = -1 sage: abs(z) 1 sage: abs(z) == abs(1) True
) |
Return the bitwise and two integers.
sage: n = Integer(6); m = Integer(2) sage: n \& m 2 sage: n.__and__(m) 2
) |
Return a copy of the integer.
sage: n = 2 sage: copy(n) 2 sage: copy(n) is n False
) |
Return double precision floating point representation of this integer.
sage: n = Integer(17); float(n) 17.0 sage: n = Integer(902834098234908209348209834092834098); float(n) 9.0283409823490813e+35 sage: n = Integer(-57); float(n) -57.0 sage: n.__float__() -57.0 sage: type(n.__float__()) <type 'float'>
) |
Computes the whole part of
.
sage: a = Integer(321) ; b = Integer(10) sage: a // b 32 sage: z = Integer(-231) sage: z // 2 -116 sage: z = Integer(231) sage: z // 2 115 sage: z // -2 -116 sage: z // 0 Traceback (most recent call last): ... ZeroDivisionError: other must be nonzero
) |
Return the hexadecimal digits of self in lower case.
Note: '0x' is not prepended to the result like is done by the corresponding Python function on int or long. This is for efficiency sake--adding and stripping the string wastes time; since this function is used for conversions from integers to other C-library structures, it is important that it be fast.
sage: print hex(Integer(15)) f sage: print hex(Integer(16)) 10 sage: print hex(Integer(16938402384092843092843098243)) 36bb1e3929d1a8fe2802f083 sage: print hex(long(16938402384092843092843098243)) 0x36bb1e3929d1a8fe2802f083L
) |
Needed so integers can be used as list indices.
sage: v = [1,2,3,4,5] sage: v[Integer(3)] 4 sage: v[Integer(2):Integer(4)] [3, 4]
) |
Return the Python int (or long) corresponding to this SAGE integer.
sage: n = 920938; n 920938 sage: int(n) 920938 sage: type(n.__int__()) <type 'int'> sage: n = 99028390823409823904823098490238409823490820938; n 99028390823409823904823098490238409823490820938 sage: type(n.__int__()) <type 'long'>
) |
Return the multiplicative interse of self, as a rational number.
sage: n = 10 sage: 1/n 1/10 sage: n.__invert__() 1/10
) |
Return long integer corresponding to this SAGE integer.
sage: n = 9023408290348092849023849820934820938490234290; n 9023408290348092849023849820934820938490234290 sage: long(n) 9023408290348092849023849820934820938490234290L sage: n = 920938; n 920938 sage: long(n) 920938L sage: n.__long__() 920938L
) |
Shift x y bits to the left.
sage: 32 << 2 128 sage: 32 << int(2) 128 sage: int(32) << 2 128 sage: 1 << 2.5 Traceback (most recent call last): ... TypeError: unsupported operands for <<
) |
Returns self modulo the modulus.
sage: z = 43 sage: z % 2 1 sage: z % 0 Traceback (most recent call last): ... ZeroDivisionError: Integer modulo by zero sage: -5 % 7 2 sage: -5 % -7 -5 sage: 5 % -7 -2
) |
Return the digits of self in base 8.
Note: '0' is not prepended to the result like is done by the corresponding Python function on int or long. This is for efficiency sake--adding and stripping the string wastes time; since this function is used for conversions from integers to other C-library structures, it is important that it be fast.
sage: print oct(Integer(800)) 1440 sage: print oct(Integer(8)) 10 sage: print oct(Integer(-50)) -62 sage: print oct(Integer(-899)) -1603 sage: print oct(Integer(16938402384092843092843098243)) 15535436162247215217705000570203
Behavior of Sage integers vs. Python integers:
sage: oct(Integer(10)) '12' sage: oct(int(10)) '012' sage: oct(Integer(-23)) '-27' sage: oct(int(-23)) '-027'
) |
Return the bitwise or of the integers x and y.
sage: n = 8; m = 4 sage: n.__or__(m) 12
) |
sage: z=43434 sage: z.__pos__() 43434
) |
This is used when pickling integers.
sage: n = 5 sage: t = n.__reduce__(); t (<built-in function make_integer>, ('5',)) sage: t[0](*t[1]) 5 sage: loads(dumps(n)) == n True
) |
Return string representation of this integer.
sage: n = -5; n.__repr__() '-5'
) |
sage: 32 >> 2 8 sage: 32 >> int(2) 8 sage: int(32) >> 2 8 sage: 1 >> 2.5 Traceback (most recent call last): ... TypeError: unsupported operands for >>
) |
Return partial factorization of self obtained using trial division for all primes up to limit, where limit must fit in a signed int.
Input:
ALGORITHM: Uses Pari.
sage: n = 920384092842390423848290348203948092384082349082 sage: n._factor_trial_division(1000) 2 * 11 * 41835640583745019265831379463815822381094652231 sage: n._factor_trial_division(2^30) 2 * 11 * 1531 * 27325696005058797691594630609938486205809701
) |
Return the image of self under the map that sends the generators of the parent to im_gens. Since ZZ maps canonically in the category of rings, this is just the natural coercion.
sage: n = -10 sage: R = GF(17) sage: n._im_gens_(R, [R(1)]) 7
) |
Return canonical string to coerce this integer to any other math software, i.e., just the string representation of this integer in base 10.
sage: n = 9390823 sage: n._interface_init_() '9390823'
) |
sage: [0] * 8 #indirect doctest [0, 0, 0, 0, 0, 0, 0, 0] sage: 'hi' * 8 'hihihihihihihihi'
) |
Return latex representation of this integer. This is just the underlying string representation and nothing more. This is called by the latex function.
sage: n = -5; n._latex_() '-5' sage: latex(n) -5
) |
Returns the least common multiple of self and
.
sage: n = 60 sage: n._lcm(150) 300
) |
Return mathml representation of this integer.
sage: mathml(-45) <mn>-45</mn> sage: (-45)._mathml_() '<mn>-45</mn>'
) |
Returns the PARI version of this integer.
sage: n = 9390823 sage: m = n._pari_(); m 9390823 sage: type(m) <type 'sage.libs.pari.gen.gen'>
TESTS:
sage: n = 10^10000000 sage: m = n._pari_() ## crash from trac 875 sage: m % 1234567 1041334
) |
sage: 8 * [0] #indirect doctest [0, 0, 0, 0, 0, 0, 0, 0] sage: 8 * 'hi' 'hihihihihihihihi'
) |
Returns int(self) so that rpy can convert self into an object it knows how to work with.
sage: n = 100 sage: n._rpy_() 100 sage: type(n._rpy_()) <type 'int'>
) |
Computes extended gcd of self and
.
Input:
NOTE: If minimal is False, then there is no guarantee that the returned cofactors will be minimal in any sense; the only guarantee is that the Bezout identity will be satisfied (see examples below).
If minimal is True, the cofactors will satisfy the following
conditions. If either self or
are zero, the trivial solution
is returned. If both self and
are nonzero, the function returns
the unique solution such that
(which then must
also satisfy
self
).
sage: Integer(5)._xgcd(7) (1, -4, 3) sage: 5*-4 + 7*3 1 sage: g,s,t = Integer(58526524056)._xgcd(101294172798) sage: g 22544886 sage: 58526524056 * s + 101294172798 * t 22544886
Without minimality guarantees, weird things can happen:
sage: Integer(3)._xgcd(21) (3, -20, 3) sage: Integer(3)._xgcd(24) (3, -15, 2) sage: Integer(3)._xgcd(48) (3, -15, 1)
Weirdness disappears with minimal option:
sage: Integer(3)._xgcd(21, minimal=True) (3, 1, 0) sage: Integer(3)._xgcd(24, minimal=True) (3, 1, 0) sage: Integer(3)._xgcd(48, minimal=True) (3, 1, 0) sage: Integer(21)._xgcd(3, minimal=True) (3, 0, 1)
Try minimal option with various edge cases:
sage: Integer(5)._xgcd(0, minimal=True) (5, 1, 0) sage: Integer(-5)._xgcd(0, minimal=True) (5, -1, 0) sage: Integer(0)._xgcd(5, minimal=True) (5, 0, 1) sage: Integer(0)._xgcd(-5, minimal=True) (5, 0, -1) sage: Integer(0)._xgcd(0, minimal=True) (0, 1, 0)
Exhaustive tests, checking minimality conditions:
sage: for a in srange(-20, 20): ... for b in srange(-20, 20): ... if a == 0 or b == 0: continue ... g, s, t = a._xgcd(b) ... assert g > 0 ... assert a % g == 0 and b % g == 0 ... assert a*s + b*t == g ... g, s, t = a._xgcd(b, minimal=True) ... assert g > 0 ... assert a % g == 0 and b % g == 0 ... assert a*s + b*t == g ... assert s >= 0 and s < abs(b)/g ... assert abs(t) <= abs(a)/g
Author: David Harvey (2007-12-26): added minimality option
Class: IntegerWrapper
Class: long_to_Z
sage: f = ZZ.coerce_map_from(long); f Native morphism: From: Set of Python objects of type 'long' To: Integer Ring sage: f(1rL) 1 sage: f(-10000000000000000000001r) -10000000000000000000001
Special Functions: __init__,
_repr_type
) |
See About this document... for information on suggesting changes.