Elements of the ring \(\ZZ\) of integers#

Sage has highly optimized and extensive functionality for arithmetic with integers and the ring of integers.

EXAMPLES:

Add 2 integers:

sage: a = Integer(3); b = Integer(4)
sage: a + b == 7
True

>>> from sage.all import *
>>> a = Integer(Integer(3)); b = Integer(Integer(4))
>>> a + b == Integer(7)
True

Add an integer and a real number:

sage: a + 4.0                                                                       # needs sage.rings.real_mpfr
7.00000000000000

>>> from sage.all import *
>>> a + RealNumber('4.0')                                                                       # needs sage.rings.real_mpfr
7.00000000000000

Add an integer and a rational number:

sage: a + Rational(2)/5
17/5

>>> from sage.all import *
>>> a + Rational(Integer(2))/Integer(5)
17/5

Add an integer and a complex number:

sage: # needs sage.rings.real_mpfr
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

>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> b = ComplexField().gen(0) + RealNumber('1.5')
>>> loads((a + b).dumps()) == a + b
True

>>> z = Integer(32)
>>> -z
-32
>>> z = Integer(0); -z
0
>>> z = -Integer(0); -z
0
>>> z = -Integer(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

>>> from sage.all import *
>>> a = Integer(Integer(3)); b = Integer(Integer(4))
>>> a * b == Integer(12)
True
>>> loads((a * RealNumber('4.0')).dumps()) == a*b
True
>>> a * Rational(Integer(2))/Integer(5)
6/5

sage: [2,3] * 4
[2, 3, 2, 3, 2, 3, 2, 3]

>>> from sage.all import *
>>> [Integer(2),Integer(3)] * Integer(4)
[2, 3, 2, 3, 2, 3, 2, 3]

sage: 'sage' * Integer(3)
'sagesagesage'

>>> from sage.all import *
>>> 'sage' * Integer(Integer(3))
'sagesagesage'

COERCIONS:

Return version of this integer in the multi-precision floating real field \(\RR\):

sage: n = 9390823
sage: RR = RealField(200)                                                           # needs sage.rings.real_mpfr
sage: RR(n)                                                                         # needs sage.rings.real_mpfr
9.3908230000000000000000000000000000000000000000000000000000e6

>>> from sage.all import *
>>> n = Integer(9390823)
>>> RR = RealField(Integer(200))                                                           # needs sage.rings.real_mpfr
>>> RR(n)                                                                         # needs sage.rings.real_mpfr
9.3908230000000000000000000000000000000000000000000000000000e6

AUTHORS:

  • William Stein (2005): initial version

  • Gonzalo Tornaria (2006-03-02): vastly improved python/GMP conversion; hashing

  • Didier Deshommes (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

  • Robert Bradshaw (2008-10-02): bounded squarefree part

  • David Loeffler (2011-01-15): fixed bug #10625 (inverse_mod should accept an ideal as argument)

  • Vincent Delecroix (2010-12-28): added unicode in Integer.__init__

  • David Roe (2012-03): deprecate is_power() in favour of is_perfect_power() (see Issue #12116)

  • Vincent Delecroix (2017-05-03): faster integer-rational comparisons

  • Vincent Klein (2017-05-11): add __mpz__() to class Integer

  • Vincent Klein (2017-05-22): Integer constructor support gmpy2.mpz parameter

  • Samuel Lelièvre (2018-08-02): document that divisors are sorted (Issue #25983)

sage.rings.integer.GCD_list(v)[source]#

Return the greatest common divisor of a list of integers.

INPUT:

  • v – list or tuple

Elements of \(v\) are converted to Sage integers. An empty list has GCD zero.

This function is used, for example, by rings/arith.py.

EXAMPLES:

sage: from sage.rings.integer import GCD_list
sage: w = GCD_list([3,9,30]); w
3
sage: type(w)
<class 'sage.rings.integer.Integer'>

>>> from sage.all import *
>>> from sage.rings.integer import GCD_list
>>> w = GCD_list([Integer(3),Integer(9),Integer(30)]); w
3
>>> type(w)
<class 'sage.rings.integer.Integer'>

Check that the bug reported in Issue #3118 has been fixed:

sage: sage.rings.integer.GCD_list([2,2,3])
1

>>> from sage.all import *
>>> sage.rings.integer.GCD_list([Integer(2),Integer(2),Integer(3)])
1

The inputs are converted to Sage integers.

sage: w = GCD_list([int(3), int(9), '30']); w
3
sage: type(w)
<class 'sage.rings.integer.Integer'>

>>> from sage.all import *
>>> w = GCD_list([int(Integer(3)), int(Integer(9)), '30']); w
3
>>> type(w)
<class 'sage.rings.integer.Integer'>

Check that the GCD of the empty list is zero (Issue #17257):

sage: GCD_list([])
0

>>> from sage.all import *
>>> GCD_list([])
0
class sage.rings.integer.Integer[source]#

Bases: EuclideanDomainElement

The Integer class represents arbitrary precision integers. It derives from the Element class, so integers can be used as ring elements anywhere in Sage.

The constructor of Integer interprets strings that begin with 0o as octal numbers, strings that begin with 0x as hexadecimal numbers and strings that begin with 0b as binary numbers.

The class Integer is implemented in Cython, as a wrapper of the GMP mpz_t integer type.

EXAMPLES:

sage: Integer(123)
123
sage: Integer("123")
123

>>> from sage.all import *
>>> Integer(Integer(123))
123
>>> Integer("123")
123

Sage Integers support PEP 3127 literals:

sage: Integer('0x12')
18
sage: Integer('-0o12')
-10
sage: Integer('+0b101010')
42

>>> from sage.all import *
>>> Integer('0x12')
18
>>> Integer('-0o12')
-10
>>> Integer('+0b101010')
42

Conversion from PARI:

sage: Integer(pari('-10380104371593008048799446356441519384'))                  # needs sage.libs.pari
-10380104371593008048799446356441519384
sage: Integer(pari('Pol([-3])'))                                                # needs sage.libs.pari
-3

>>> from sage.all import *
>>> Integer(pari('-10380104371593008048799446356441519384'))                  # needs sage.libs.pari
-10380104371593008048799446356441519384
>>> Integer(pari('Pol([-3])'))                                                # needs sage.libs.pari
-3

Conversion from gmpy2:

sage: from gmpy2 import mpz
sage: Integer(mpz(3))
3

>>> from sage.all import *
>>> from gmpy2 import mpz
>>> Integer(mpz(Integer(3)))
3
__pow__(left, right, modulus)[source]#

Return (left ^ right) % modulus.

EXAMPLES:

sage: 2^-6
1/64
sage: 2^6
64
sage: 2^0
1
sage: 2^-0
1
sage: (-1)^(1/3)                                                            # needs sage.symbolic
(-1)^(1/3)

>>> from sage.all import *
>>> Integer(2)**-Integer(6)
1/64
>>> Integer(2)**Integer(6)
64
>>> Integer(2)**Integer(0)
1
>>> Integer(2)**-Integer(0)
1
>>> (-Integer(1))**(Integer(1)/Integer(3))                                                            # needs sage.symbolic
(-1)^(1/3)

For consistency with Python and MPFR, 0^0 is defined to be 1 in Sage:

sage: 0^0
1

>>> from sage.all import *
>>> Integer(0)**Integer(0)
1

See also http://www.faqs.org/faqs/sci-math-faq/0to0/ and https://math.stackexchange.com/questions/11150/zero-to-the-zero-power-is-00-1.

The base need not be a Sage integer. If it is a Python type, the result is a Python type too:

sage: r = int(2) ^ 10; r; type(r)
1024
<... 'int'>
sage: r = int(3) ^ -3; r; type(r)
0.037037037037037035
<... 'float'>
sage: r = float(2.5) ^ 10; r; type(r)
9536.7431640625
<... 'float'>

>>> from sage.all import *
>>> r = int(Integer(2)) ** Integer(10); r; type(r)
1024
<... 'int'>
>>> r = int(Integer(3)) ** -Integer(3); r; type(r)
0.037037037037037035
<... 'float'>
>>> r = float(RealNumber('2.5')) ** Integer(10); r; type(r)
9536.7431640625
<... 'float'>

We raise 2 to various interesting exponents:

sage: 2^x                # symbolic x                                       # needs sage.symbolic
2^x
sage: 2^1.5              # real number                                      # needs sage.rings.real_mpfr
2.82842712474619
sage: 2^float(1.5)       # python float  abs tol 3e-16
2.8284271247461903
sage: 2^I                # complex number                                   # needs sage.symbolic
2^I
sage: r = 2 ^ int(-3); r; type(r)
1/8
<class 'sage.rings.rational.Rational'>
sage: f = 2^(sin(x)-cos(x)); f                                              # needs sage.symbolic
2^(-cos(x) + sin(x))
sage: f(x=3)                                                                # needs sage.symbolic
2^(-cos(3) + sin(3))

>>> from sage.all import *
>>> Integer(2)**x                # symbolic x                                       # needs sage.symbolic
2^x
>>> Integer(2)**RealNumber('1.5')              # real number                                      # needs sage.rings.real_mpfr
2.82842712474619
>>> Integer(2)**float(RealNumber('1.5'))       # python float  abs tol 3e-16
2.8284271247461903
>>> Integer(2)**I                # complex number                                   # needs sage.symbolic
2^I
>>> r = Integer(2) ** int(-Integer(3)); r; type(r)
1/8
<class 'sage.rings.rational.Rational'>
>>> f = Integer(2)**(sin(x)-cos(x)); f                                              # needs sage.symbolic
2^(-cos(x) + sin(x))
>>> f(x=Integer(3))                                                                # needs sage.symbolic
2^(-cos(3) + sin(3))

A symbolic sum:

sage: # needs sage.symbolic
sage: x, y, z = var('x,y,z')
sage: 2^(x + y + z)
2^(x + y + z)
sage: 2^(1/2)
sqrt(2)
sage: 2^(-1/2)
1/2*sqrt(2)

>>> from sage.all import *
>>> # needs sage.symbolic
>>> x, y, z = var('x,y,z')
>>> Integer(2)**(x + y + z)
2^(x + y + z)
>>> Integer(2)**(Integer(1)/Integer(2))
sqrt(2)
>>> Integer(2)**(-Integer(1)/Integer(2))
1/2*sqrt(2)
additive_order()[source]#

Return the additive order of self.

EXAMPLES:

sage: ZZ(0).additive_order()
1
sage: ZZ(1).additive_order()
+Infinity

>>> from sage.all import *
>>> ZZ(Integer(0)).additive_order()
1
>>> ZZ(Integer(1)).additive_order()
+Infinity
as_integer_ratio()[source]#

Return the pair (self.numerator(), self.denominator()), which is (self, 1).

EXAMPLES:

sage: x = -12
sage: x.as_integer_ratio()
(-12, 1)

>>> from sage.all import *
>>> x = -Integer(12)
>>> x.as_integer_ratio()
(-12, 1)
balanced_digits(base=10, positive_shift=True)[source]#

Return the list of balanced digits for self in the given base.

The balanced base b uses b digits centered around zero. Thus if b is odd, there is only one possibility, namely digits between -b//2 and b//2 (both included). For instance in base 9, one uses digits from -4 to 4. If b is even, one has to choose between digits from -b//2 to b//2 - 1 or -b//2 + 1 to b//2 (base 10 for instance: either \(-5\) to \(4\) or \(-4\) to \(5\)), and this is defined by the value of positive_shift.

INPUT:

  • base – integer (default: 10); when base is 2, only the nonnegative or the nonpositive integers can be represented by balanced_digits. Thus we say base must be greater than 2.

  • positive_shift – boolean (default: True); for even bases, the representation uses digits from -b//2 + 1 to b//2 if set to True, and from -b//2 to b//2 - 1 otherwise. This has no effect for odd bases.

EXAMPLES:

sage: 8.balanced_digits(3)
[-1, 0, 1]
sage: (-15).balanced_digits(5)
[0, 2, -1]
sage: 17.balanced_digits(6)
[-1, 3]
sage: 17.balanced_digits(6, positive_shift=False)
[-1, -3, 1]
sage: (-46).balanced_digits()
[4, 5, -1]
sage: (-46).balanced_digits(positive_shift=False)
[4, -5]
sage: (-23).balanced_digits(12)
[1, -2]
sage: (-23).balanced_digits(12, positive_shift=False)
[1, -2]
sage: 0.balanced_digits(7)
[]
sage: 14.balanced_digits(5.8)
Traceback (most recent call last):
...
ValueError: base must be an integer
sage: 14.balanced_digits(2)
Traceback (most recent call last):
...
ValueError: base must be > 2

>>> from sage.all import *
>>> Integer(8).balanced_digits(Integer(3))
[-1, 0, 1]
>>> (-Integer(15)).balanced_digits(Integer(5))
[0, 2, -1]
>>> Integer(17).balanced_digits(Integer(6))
[-1, 3]
>>> Integer(17).balanced_digits(Integer(6), positive_shift=False)
[-1, -3, 1]
>>> (-Integer(46)).balanced_digits()
[4, 5, -1]
>>> (-Integer(46)).balanced_digits(positive_shift=False)
[4, -5]
>>> (-Integer(23)).balanced_digits(Integer(12))
[1, -2]
>>> (-Integer(23)).balanced_digits(Integer(12), positive_shift=False)
[1, -2]
>>> Integer(0).balanced_digits(Integer(7))
[]
>>> Integer(14).balanced_digits(RealNumber('5.8'))
Traceback (most recent call last):
...
ValueError: base must be an integer
>>> Integer(14).balanced_digits(Integer(2))
Traceback (most recent call last):
...
ValueError: base must be > 2

See also

digits

binary()[source]#

Return the binary digits of self as a string.

EXAMPLES:

sage: print(Integer(15).binary())
1111
sage: print(Integer(16).binary())
10000
sage: print(Integer(16938402384092843092843098243).binary())
1101101011101100011110001110010010100111010001101010001111111000101000000000101111000010000011

>>> from sage.all import *
>>> print(Integer(Integer(15)).binary())
1111
>>> print(Integer(Integer(16)).binary())
10000
>>> print(Integer(Integer(16938402384092843092843098243)).binary())
1101101011101100011110001110010010100111010001101010001111111000101000000000101111000010000011
binomial(m, algorithm='gmp')[source]#

Return the binomial coefficient “self choose m”.

INPUT:

  • m – an integer

  • algorithm – 'gmp' (default), 'mpir' (an alias for gmp), or 'pari'; 'gmp' is faster for small m, and 'pari' tends to be faster for large m

OUTPUT: integer

EXAMPLES:

sage: 10.binomial(2)
45
sage: 10.binomial(2, algorithm='pari')                                      # needs sage.libs.pari
45
sage: 10.binomial(-2)
0
sage: (-2).binomial(3)
-4
sage: (-3).binomial(0)
1

>>> from sage.all import *
>>> Integer(10).binomial(Integer(2))
45
>>> Integer(10).binomial(Integer(2), algorithm='pari')                                      # needs sage.libs.pari
45
>>> Integer(10).binomial(-Integer(2))
0
>>> (-Integer(2)).binomial(Integer(3))
-4
>>> (-Integer(3)).binomial(Integer(0))
1

The argument m or (self - m) must fit into an unsigned long:

sage: (2**256).binomial(2**256)
1
sage: (2**256).binomial(2**256 - 1)
115792089237316195423570985008687907853269984665640564039457584007913129639936
sage: (2**256).binomial(2**128)
Traceback (most recent call last):
...
OverflowError: m must fit in an unsigned long

>>> from sage.all import *
>>> (Integer(2)**Integer(256)).binomial(Integer(2)**Integer(256))
1
>>> (Integer(2)**Integer(256)).binomial(Integer(2)**Integer(256) - Integer(1))
115792089237316195423570985008687907853269984665640564039457584007913129639936
>>> (Integer(2)**Integer(256)).binomial(Integer(2)**Integer(128))
Traceback (most recent call last):
...
OverflowError: m must fit in an unsigned long
bit_length()[source]#

Return the number of bits required to represent this integer.

Identical to int.bit_length().

EXAMPLES:

sage: 500.bit_length()
9
sage: 5.bit_length()
3
sage: 0.bit_length() == len(0.bits()) == 0.ndigits(base=2)
True
sage: 12345.bit_length() == len(12345.binary())
True
sage: 1023.bit_length()
10
sage: 1024.bit_length()
11

>>> from sage.all import *
>>> Integer(500).bit_length()
9
>>> Integer(5).bit_length()
3
>>> Integer(0).bit_length() == len(Integer(0).bits()) == Integer(0).ndigits(base=Integer(2))
True
>>> Integer(12345).bit_length() == len(Integer(12345).binary())
True
>>> Integer(1023).bit_length()
10
>>> Integer(1024).bit_length()
11
bits()[source]#

Return the bits in self as a list, least significant first. The result satisfies the identity

x == sum(b*2^e for e, b in enumerate(x.bits()))

Negative numbers will have negative “bits”. (So, strictly speaking, the entries of the returned list are not really members of \(\ZZ/2\ZZ\).)

This method just calls digits() with base=2.

See also

  • bit_length(), a faster way to compute len(x.bits())

  • binary(), which returns a string in perhaps more familiar notation

EXAMPLES:

sage: 500.bits()
[0, 0, 1, 0, 1, 1, 1, 1, 1]
sage: 11.bits()
[1, 1, 0, 1]
sage: (-99).bits()
[-1, -1, 0, 0, 0, -1, -1]

>>> from sage.all import *
>>> Integer(500).bits()
[0, 0, 1, 0, 1, 1, 1, 1, 1]
>>> Integer(11).bits()
[1, 1, 0, 1]
>>> (-Integer(99)).bits()
[-1, -1, 0, 0, 0, -1, -1]
ceil()[source]#

Return the ceiling of self, which is self since self is an integer.

EXAMPLES:

sage: n = 6
sage: n.ceil()
6

>>> from sage.all import *
>>> n = Integer(6)
>>> n.ceil()
6
class_number(proof=True)[source]#

Return the class number of the quadratic order with this discriminant.

INPUT:

  • self – an integer congruent to \(0\) or \(1\) mod \(4\) which is not a square

  • proof (boolean, default True) – if False, then for negative discriminants a faster algorithm is used by the PARI library which is known to give incorrect results when the class group has many cyclic factors. However, the results are correct for discriminants \(D\) with \(|D|\le 2\cdot10^{10}\).

OUTPUT:

(integer) the class number of the quadratic order with this discriminant.

Note

For positive \(D\), this is not always equal to the number of classes of primitive binary quadratic forms of discriminant \(D\), which is equal to the narrow class number. The two notions are the same when \(D<0\), or \(D>0\) and the fundamental unit of the order has negative norm; otherwise the number of classes of forms is twice this class number.

EXAMPLES:

sage: (-163).class_number()                                                 # needs sage.libs.pari
1
sage: (-104).class_number()                                                 # needs sage.libs.pari
6
sage: [((4*n + 1), (4*n + 1).class_number()) for n in [21..29]]             # needs sage.libs.pari
[(85, 2),
(89, 1),
(93, 1),
(97, 1),
(101, 1),
(105, 2),
(109, 1),
(113, 1),
(117, 1)]

>>> from sage.all import *
>>> (-Integer(163)).class_number()                                                 # needs sage.libs.pari
1
>>> (-Integer(104)).class_number()                                                 # needs sage.libs.pari
6
>>> [((Integer(4)*n + Integer(1)), (Integer(4)*n + Integer(1)).class_number()) for n in (ellipsis_range(Integer(21),Ellipsis,Integer(29)))]             # needs sage.libs.pari
[(85, 2),
(89, 1),
(93, 1),
(97, 1),
(101, 1),
(105, 2),
(109, 1),
(113, 1),
(117, 1)]
conjugate()[source]#

Return the complex conjugate of this integer, which is the integer itself.

EXAMPLES:

sage: n = 205
sage: n.conjugate()
205

>>> from sage.all import *
>>> n = Integer(205)
>>> n.conjugate()
205
coprime_integers(m)[source]#

Return the non-negative integers \(< m\) that are coprime to this integer.

EXAMPLES:

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]

>>> from sage.all import *
>>> n = Integer(8)
>>> n.coprime_integers(Integer(8))
[1, 3, 5, 7]
>>> n.coprime_integers(Integer(11))
[1, 3, 5, 7, 9]
>>> n = Integer(5); n.coprime_integers(Integer(10))
[1, 2, 3, 4, 6, 7, 8, 9]
>>> n.coprime_integers(Integer(5))
[1, 2, 3, 4]
>>> n = Integer(99); n.coprime_integers(Integer(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]

AUTHORS:

  • Naqi Jaffery (2006-01-24): examples

  • David Roe (2017-10-02): Use sieving

  • Jeroen Demeyer (2018-06-25): allow returning zero (only relevant for 1.coprime_integers(n))

ALGORITHM:

Create an integer with \(m\) bits and set bits at every multiple of a prime \(p\) that divides this integer and is less than \(m\). Then return a list of integers corresponding to the unset bits.

crt(y, m, n)[source]#

Return the unique integer between \(0\) and \(mn\) that is congruent to the integer modulo \(m\) and to \(y\) modulo \(n\).

We assume that \(m\) and \(n\) are coprime.

EXAMPLES:

sage: n = 17
sage: m = n.crt(5, 23, 11); m
247
sage: m%23
17
sage: m%11
5

>>> from sage.all import *
>>> n = Integer(17)
>>> m = n.crt(Integer(5), Integer(23), Integer(11)); m
247
>>> m%Integer(23)
17
>>> m%Integer(11)
5
denominator()[source]#

Return the denominator of this integer, which of course is always 1.

EXAMPLES:

sage: x = 5
sage: x.denominator()
1
sage: x = 0
sage: x.denominator()
1

>>> from sage.all import *
>>> x = Integer(5)
>>> x.denominator()
1
>>> x = Integer(0)
>>> x.denominator()
1
digits(base=10, digits=None, padto=0)[source]#

Return a list of digits for self in the given base in little endian order.

The returned value is unspecified if self is a negative number and the digits are given.

INPUT:

  • base – integer (default: 10)

  • digits – optional indexable object as source for the digits

  • padto – the minimal length of the returned list, sufficient number of zeros are added to make the list minimum that length (default: 0)

As a shorthand for digits(2), you can use bits().

Also see ndigits().

EXAMPLES:

sage: 17.digits()
[7, 1]
sage: 5.digits(base=2, 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]

>>> from sage.all import *
>>> Integer(17).digits()
[7, 1]
>>> Integer(5).digits(base=Integer(2), digits=["zero","one"])
['one', 'zero', 'one']
>>> Integer(5).digits(Integer(3))
[2, 1]
>>> Integer(0).digits(base=Integer(10))  # 0 has 0 digits
[]
>>> Integer(0).digits(base=Integer(2))  # 0 has 0 digits
[]
>>> Integer(10).digits(Integer(16),'0123456789abcdef')
['a']
>>> Integer(0).digits(Integer(16),'0123456789abcdef')
[]
>>> Integer(0).digits(Integer(16),'0123456789abcdef',padto=Integer(1))
['0']
>>> Integer(123).digits(base=Integer(10),padto=Integer(5))
[3, 2, 1, 0, 0]
>>> Integer(123).digits(base=Integer(2),padto=Integer(3))       # padto is the minimal length
[1, 1, 0, 1, 1, 1, 1]
>>> Integer(123).digits(base=Integer(2),padto=Integer(10),digits=(Integer(1),-Integer(1)))
[-1, -1, 1, -1, -1, -1, -1, 1, 1, 1]
>>> a=Integer(9939082340); a.digits(Integer(10))
[0, 4, 3, 2, 8, 0, 9, 3, 9, 9]
>>> a.digits(Integer(512))
[100, 302, 26, 74]
>>> (-Integer(12)).digits(Integer(10))
[-2, -1]
>>> (-Integer(12)).digits(Integer(2))
[0, 0, -1, -1]

We support large bases.

sage: n=2^6000
sage: n.digits(2^3000)
[0, 0, 1]

>>> from sage.all import *
>>> n=Integer(2)**Integer(6000)
>>> n.digits(Integer(2)**Integer(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

>>> from sage.all import *
>>> base=Integer(3); n=Integer(25)
>>> l=n.digits(base)
>>> # the next relationship should hold for all n,base
>>> sum(base**i*l[i] for i in range(len(l)))==n
True
>>> base=Integer(3); n=-Integer(30); l=n.digits(base); sum(base**i*l[i] for i in range(len(l)))==n
True

The inverse of this method – constructing an integer from a list of digits and a base – can be done using the above method or by simply using ZZ() with a base:

sage: x = 123; ZZ(x.digits(), 10)
123
sage: x == ZZ(x.digits(6), 6)
True
sage: x == ZZ(x.digits(25), 25)
True

>>> from sage.all import *
>>> x = Integer(123); ZZ(x.digits(), Integer(10))
123
>>> x == ZZ(x.digits(Integer(6)), Integer(6))
True
>>> x == ZZ(x.digits(Integer(25)), Integer(25))
True

Using sum() and enumerate() to do the same thing is slightly faster in many cases (and balanced_sum() may be faster yet). Of course it gives the same result:

sage: base = 4
sage: sum(digit * base^i for i, digit in enumerate(x.digits(base))) == ZZ(x.digits(base), base)
True

>>> from sage.all import *
>>> base = Integer(4)
>>> sum(digit * base**i for i, digit in enumerate(x.digits(base))) == ZZ(x.digits(base), base)
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 = list(range(15))
sage: l = [ZZ(i).digits(15,digits) for i in range(100)]
sage: l[16]
[1, 1]

>>> from sage.all import *
>>> digits = list(range(Integer(15)))
>>> l = [ZZ(i).digits(Integer(15),digits) for i in range(Integer(100))]
>>> l[Integer(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                     # needs sage.rings.real_interval_field
1
sage: n=10^10000
sage: n.digits(base=10)[-1]  # slightly faster than str                     # needs sage.rings.real_interval_field
1

>>> from sage.all import *
>>> n=Integer(3)**Integer(100000)
>>> n.digits(base=Integer(10))[-Integer(1)]  # slightly slower than str                     # needs sage.rings.real_interval_field
1
>>> n=Integer(10)**Integer(10000)
>>> n.digits(base=Integer(10))[-Integer(1)]  # slightly faster than str                     # needs sage.rings.real_interval_field
1

AUTHORS:

  • Joel B. Mohler (2008-03-02): significantly rewrote this entire function

divide_knowing_divisible_by(right)[source]#

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

EXAMPLES:

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

>>> from sage.all import *
>>> a = Integer(8); b = Integer(4)
>>> a.divide_knowing_divisible_by(b)
2
>>> (Integer(100000)).divide_knowing_divisible_by(Integer(25))
4000
>>> (Integer(100000)).divide_knowing_divisible_by(Integer(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

>>> from sage.all import *
>>> a = Integer(2)**Integer(70); a
1180591620717411303424
>>> a // Integer(11)  # floor divide
107326510974310118493
>>> a.divide_knowing_divisible_by(Integer(11)) # way off and possibly random
43215361478743422388970455040
divides(n)[source]#

Return True if self divides n.

EXAMPLES:

sage: Z = IntegerRing()
sage: Z(5).divides(Z(10))
True
sage: Z(0).divides(Z(5))
False
sage: Z(10).divides(Z(5))
False

>>> from sage.all import *
>>> Z = IntegerRing()
>>> Z(Integer(5)).divides(Z(Integer(10)))
True
>>> Z(Integer(0)).divides(Z(Integer(5)))
False
>>> Z(Integer(10)).divides(Z(Integer(5)))
False
divisors(method=None)[source]#

Return the list of all positive integer divisors of this integer, sorted in increasing order.

EXAMPLES:

sage: (-3).divisors()
[1, 3]
sage: 6.divisors()
[1, 2, 3, 6]
sage: 28.divisors()
[1, 2, 4, 7, 14, 28]
sage: (2^5).divisors()
[1, 2, 4, 8, 16, 32]
sage: 100.divisors()
[1, 2, 4, 5, 10, 20, 25, 50, 100]
sage: 1.divisors()
[1]
sage: 0.divisors()
Traceback (most recent call last):
...
ValueError: n must be nonzero
sage: (2^3 * 3^2 * 17).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]
sage: a = odd_part(factorial(31))
sage: v = a.divisors()                                                      # needs sage.libs.pari
sage: len(v)                                                                # needs sage.libs.pari
172800
sage: prod(e + 1 for p, e in factor(a))                                     # needs sage.libs.pari
172800
sage: all(t.divides(a) for t in v)                                          # needs sage.libs.pari
True

>>> from sage.all import *
>>> (-Integer(3)).divisors()
[1, 3]
>>> Integer(6).divisors()
[1, 2, 3, 6]
>>> Integer(28).divisors()
[1, 2, 4, 7, 14, 28]
>>> (Integer(2)**Integer(5)).divisors()
[1, 2, 4, 8, 16, 32]
>>> Integer(100).divisors()
[1, 2, 4, 5, 10, 20, 25, 50, 100]
>>> Integer(1).divisors()
[1]
>>> Integer(0).divisors()
Traceback (most recent call last):
...
ValueError: n must be nonzero
>>> (Integer(2)**Integer(3) * Integer(3)**Integer(2) * Integer(17)).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]
>>> a = odd_part(factorial(Integer(31)))
>>> v = a.divisors()                                                      # needs sage.libs.pari
>>> len(v)                                                                # needs sage.libs.pari
172800
>>> prod(e + Integer(1) for p, e in factor(a))                                     # needs sage.libs.pari
172800
>>> all(t.divides(a) for t in v)                                          # needs sage.libs.pari
True

sage: n = 2^551 - 1
sage: L = n.divisors()                                                      # needs sage.libs.pari
sage: len(L)                                                                # needs sage.libs.pari
256
sage: L[-1] == n                                                            # needs sage.libs.pari
True

>>> from sage.all import *
>>> n = Integer(2)**Integer(551) - Integer(1)
>>> L = n.divisors()                                                      # needs sage.libs.pari
>>> len(L)                                                                # needs sage.libs.pari
256
>>> L[-Integer(1)] == n                                                            # needs sage.libs.pari
True

Note

If one first computes all the divisors and then sorts it, the sorting step can easily dominate the runtime. Note, however, that (non-negative) multiplication on the left preserves relative order. One can leverage this fact to keep the list in order as one computes it using a process similar to that of the merge sort algorithm.

euclidean_degree()[source]#

Return the degree of this element as an element of an Euclidean domain.

If this is an element in the ring of integers, this is simply its absolute value.

EXAMPLES:

sage: ZZ(1).euclidean_degree()
1

>>> from sage.all import *
>>> ZZ(Integer(1)).euclidean_degree()
1
exact_log(m)[source]#

Return the largest integer \(k\) such that \(m^k \leq \text{self}\), i.e., the floor of \(\log_m(\text{self})\).

This is guaranteed to return the correct answer even when the usual log function doesn’t have sufficient precision.

INPUT:

  • m – integer \(\geq 2\)

AUTHORS:

  • David Harvey (2006-09-15)

  • Joel B. Mohler (2009-04-08) – rewrote this to handle small cases and/or easy cases up to 100x faster..

EXAMPLES:

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: Integer(178^1700).exact_log(178)
1700
sage: Integer(178^1700-1).exact_log(178)
1699
sage: Integer(178^1700+1).exact_log(178)
1700
sage: # we need to exercise the large base code path too
sage: Integer(1780^1700-1).exact_log(1780)                                  # needs sage.rings.real_interval_field
1699

sage: # The following are very very fast.
sage: # Note that for base m a perfect power of 2, we get the exact log by counting bits.
sage: n = 2983579823750185701375109835; m = 32
sage: n.exact_log(m)
18
sage: # The next is a favorite of mine.  The log2 approximate is exact and immediately provable.
sage: n = 90153710570912709517902579010793251709257901270941709247901209742124
sage: m = 213509721309572
sage: n.exact_log(m)
4

>>> from sage.all import *
>>> Integer(Integer(125)).exact_log(Integer(5))
3
>>> Integer(Integer(124)).exact_log(Integer(5))
2
>>> Integer(Integer(126)).exact_log(Integer(5))
3
>>> Integer(Integer(3)).exact_log(Integer(5))
0
>>> Integer(Integer(1)).exact_log(Integer(5))
0
>>> Integer(Integer(178)**Integer(1700)).exact_log(Integer(178))
1700
>>> Integer(Integer(178)**Integer(1700)-Integer(1)).exact_log(Integer(178))
1699
>>> Integer(Integer(178)**Integer(1700)+Integer(1)).exact_log(Integer(178))
1700
>>> # we need to exercise the large base code path too
>>> Integer(Integer(1780)**Integer(1700)-Integer(1)).exact_log(Integer(1780))                                  # needs sage.rings.real_interval_field
1699

>>> # The following are very very fast.
>>> # Note that for base m a perfect power of 2, we get the exact log by counting bits.
>>> n = Integer(2983579823750185701375109835); m = Integer(32)
>>> n.exact_log(m)
18
>>> # The next is a favorite of mine.  The log2 approximate is exact and immediately provable.
>>> n = Integer(90153710570912709517902579010793251709257901270941709247901209742124)
>>> m = Integer(213509721309572)
>>> n.exact_log(m)
4

sage: # needs sage.rings.real_mpfr
sage: x = 3^100000
sage: RR(log(RR(x), 3))
100000.000000000
sage: RR(log(RR(x + 100000), 3))
100000.000000000

>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> x = Integer(3)**Integer(100000)
>>> RR(log(RR(x), Integer(3)))
100000.000000000
>>> RR(log(RR(x + Integer(100000)), Integer(3)))
100000.000000000

sage: # needs sage.rings.real_mpfr
sage: x.exact_log(3)
100000
sage: (x + 1).exact_log(3)
100000
sage: (x - 1).exact_log(3)
99999

>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> x.exact_log(Integer(3))
100000
>>> (x + Integer(1)).exact_log(Integer(3))
100000
>>> (x - Integer(1)).exact_log(Integer(3))
99999

sage: # needs sage.rings.real_mpfr
sage: x.exact_log(2.5)
Traceback (most recent call last):
...
TypeError: Attempt to coerce non-integral RealNumber to Integer

>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> x.exact_log(RealNumber('2.5'))
Traceback (most recent call last):
...
TypeError: Attempt to coerce non-integral RealNumber to Integer
exp(prec=None)[source]#

Return the exponential function of self as a real number.

This function is provided only so that Sage integers may be treated in the same manner as real numbers when convenient.

INPUT:

  • prec – integer (default: None): if None, returns symbolic, else to given bits of precision as in RealField

EXAMPLES:

sage: Integer(8).exp()                                                      # needs sage.symbolic
e^8
sage: Integer(8).exp(prec=100)                                              # needs sage.symbolic
2980.9579870417282747435920995
sage: exp(Integer(8))                                                       # needs sage.symbolic
e^8

>>> from sage.all import *
>>> Integer(Integer(8)).exp()                                                      # needs sage.symbolic
e^8
>>> Integer(Integer(8)).exp(prec=Integer(100))                                              # needs sage.symbolic
2980.9579870417282747435920995
>>> exp(Integer(Integer(8)))                                                       # needs sage.symbolic
e^8

For even fairly large numbers, this may not be useful.

sage: y = Integer(145^145)
sage: y.exp()                                                               # needs sage.symbolic
e^25024207011349079210459585279553675697932183658421565260323592409432707306554163224876110094014450895759296242775250476115682350821522931225499163750010280453185147546962559031653355159703678703793369785727108337766011928747055351280379806937944746847277089168867282654496776717056860661614337004721164703369140625
sage: y.exp(prec=53)  # default RealField precision                         # needs sage.symbolic
+infinity

>>> from sage.all import *
>>> y = Integer(Integer(145)**Integer(145))
>>> y.exp()                                                               # needs sage.symbolic
e^25024207011349079210459585279553675697932183658421565260323592409432707306554163224876110094014450895759296242775250476115682350821522931225499163750010280453185147546962559031653355159703678703793369785727108337766011928747055351280379806937944746847277089168867282654496776717056860661614337004721164703369140625
>>> y.exp(prec=Integer(53))  # default RealField precision                         # needs sage.symbolic
+infinity
factor(algorithm='pari', proof=None, limit=None, int_=False, verbose=0)[source]#

Return the prime factorization of this integer as a formal Factorization object.

INPUT:

  • algorithm – string

    • 'pari' – (default) use the PARI library

    • 'flint' – use the FLINT library

    • 'kash' – use the KASH computer algebra system (requires kash)

    • 'magma' – use the MAGMA computer algebra system (requires an installation of MAGMA)

    • 'qsieve' – use Bill Hart’s quadratic sieve code; WARNING: this may not work as expected, see qsieve? for more information

    • 'ecm' – use ECM-GMP, an implementation of Hendrik Lenstra’s elliptic curve method.

  • proof – bool (default: True) whether or not to prove primality of each factor (only applicable for 'pari' and 'ecm').

  • limit – int or None (default: None) if limit is given it must fit in a signed int, and the factorization is done using trial division and primes up to limit.

OUTPUT:

  • a Factorization object containing the prime factors and their multiplicities

EXAMPLES:

sage: n = 2^100 - 1; n.factor()                                             # needs sage.libs.pari
3 * 5^3 * 11 * 31 * 41 * 101 * 251 * 601 * 1801 * 4051 * 8101 * 268501

>>> from sage.all import *
>>> n = Integer(2)**Integer(100) - Integer(1); n.factor()                                             # needs sage.libs.pari
3 * 5^3 * 11 * 31 * 41 * 101 * 251 * 601 * 1801 * 4051 * 8101 * 268501

This factorization can be converted into a list of pairs \((p, e)\), where \(p\) is prime and \(e\) is a positive integer. Each pair can also be accessed directly by its index (ordered by increasing size of the prime):

sage: f = 60.factor()
sage: list(f)
[(2, 2), (3, 1), (5, 1)]
sage: f[2]
(5, 1)

>>> from sage.all import *
>>> f = Integer(60).factor()
>>> list(f)
[(2, 2), (3, 1), (5, 1)]
>>> f[Integer(2)]
(5, 1)

Similarly, the factorization can be converted to a dictionary so the exponent can be extracted for each prime:

sage: f = (3^6).factor()
sage: dict(f)
{3: 6}
sage: dict(f)[3]
6

>>> from sage.all import *
>>> f = (Integer(3)**Integer(6)).factor()
>>> dict(f)
{3: 6}
>>> dict(f)[Integer(3)]
6

We use proof=False, which doesn’t prove correctness of the primes that appear in the factorization:

sage: n = 920384092842390423848290348203948092384082349082
sage: n.factor(proof=False)                                                 # needs sage.libs.pari
2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173
sage: n.factor(proof=True)                                                  # needs sage.libs.pari
2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173

>>> from sage.all import *
>>> n = Integer(920384092842390423848290348203948092384082349082)
>>> n.factor(proof=False)                                                 # needs sage.libs.pari
2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173
>>> n.factor(proof=True)                                                  # needs sage.libs.pari
2 * 11 * 1531 * 4402903 * 10023679 * 619162955472170540533894518173

We factor using trial division only:

sage: n.factor(limit=1000)
2 * 11 * 41835640583745019265831379463815822381094652231

>>> from sage.all import *
>>> n.factor(limit=Integer(1000))
2 * 11 * 41835640583745019265831379463815822381094652231

An example where FLINT is used:

sage: n = 82862385732327628428164127822
sage: n.factor(algorithm='flint')                                           # needs sage.libs.flint
2 * 3 * 11 * 13 * 41 * 73 * 22650083 * 1424602265462161

>>> from sage.all import *
>>> n = Integer(82862385732327628428164127822)
>>> n.factor(algorithm='flint')                                           # needs sage.libs.flint
2 * 3 * 11 * 13 * 41 * 73 * 22650083 * 1424602265462161

We factor using a quadratic sieve algorithm:

sage: # needs sage.libs.pari
sage: p = next_prime(10^20)
sage: q = next_prime(10^21)
sage: n = p * q
sage: n.factor(algorithm='qsieve')                                          # needs sage.libs.flint
doctest:... RuntimeWarning: the factorization returned
by qsieve may be incomplete (the factors may not be prime)
or even wrong; see qsieve? for details
100000000000000000039 * 1000000000000000000117

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> p = next_prime(Integer(10)**Integer(20))
>>> q = next_prime(Integer(10)**Integer(21))
>>> n = p * q
>>> n.factor(algorithm='qsieve')                                          # needs sage.libs.flint
doctest:... RuntimeWarning: the factorization returned
by qsieve may be incomplete (the factors may not be prime)
or even wrong; see qsieve? for details
100000000000000000039 * 1000000000000000000117

We factor using the elliptic curve method:

sage: # needs sage.libs.pari
sage: p = next_prime(10^15)
sage: q = next_prime(10^21)
sage: n = p * q
sage: n.factor(algorithm='ecm')
1000000000000037 * 1000000000000000000117

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> p = next_prime(Integer(10)**Integer(15))
>>> q = next_prime(Integer(10)**Integer(21))
>>> n = p * q
>>> n.factor(algorithm='ecm')
1000000000000037 * 1000000000000000000117
factorial()[source]#

Return the factorial \(n! = 1 \cdot 2 \cdot 3 \cdots n\).

If the input does not fit in an unsigned long int, an OverflowError is raised.

EXAMPLES:

sage: for n in srange(7):
....:     print("{} {}".format(n, n.factorial()))
0 1
1 1
2 2
3 6
4 24
5 120
6 720

>>> from sage.all import *
>>> for n in srange(Integer(7)):
...     print("{} {}".format(n, n.factorial()))
0 1
1 1
2 2
3 6
4 24
5 120
6 720

Large integers raise an OverflowError:

sage: (2**64).factorial()
Traceback (most recent call last):
...
OverflowError: argument too large for factorial

>>> from sage.all import *
>>> (Integer(2)**Integer(64)).factorial()
Traceback (most recent call last):
...
OverflowError: argument too large for factorial

And negative ones a ValueError:

sage: (-1).factorial()
Traceback (most recent call last):
...
ValueError: factorial only defined for non-negative integers

>>> from sage.all import *
>>> (-Integer(1)).factorial()
Traceback (most recent call last):
...
ValueError: factorial only defined for non-negative integers
floor()[source]#

Return the floor of self, which is just self since self is an integer.

EXAMPLES:

sage: n = 6
sage: n.floor()
6

>>> from sage.all import *
>>> n = Integer(6)
>>> n.floor()
6
gamma()[source]#

The gamma function on integers is the factorial function (shifted by one) on positive integers, and \(\pm \infty\) on non-positive integers.

EXAMPLES:

sage: # needs sage.symbolic
sage: gamma(5)
24
sage: gamma(0)
Infinity
sage: gamma(-1)
Infinity
sage: gamma(-2^150)
Infinity

>>> from sage.all import *
>>> # needs sage.symbolic
>>> gamma(Integer(5))
24
>>> gamma(Integer(0))
Infinity
>>> gamma(-Integer(1))
Infinity
>>> gamma(-Integer(2)**Integer(150))
Infinity
global_height(prec=None)[source]#

Return the absolute logarithmic height of this rational integer.

INPUT:

  • prec (int) – desired floating point precision (default: default RealField precision).

OUTPUT:

(real) The absolute logarithmic height of this rational integer.

ALGORITHM:

The height of the integer \(n\) is \(\log |n|\).

EXAMPLES:

sage: # needs sage.rings.real_mpfr
sage: ZZ(5).global_height()
1.60943791243410
sage: ZZ(-2).global_height(prec=100)
0.69314718055994530941723212146
sage: exp(_)
2.0000000000000000000000000000

>>> from sage.all import *
>>> # needs sage.rings.real_mpfr
>>> ZZ(Integer(5)).global_height()
1.60943791243410
>>> ZZ(-Integer(2)).global_height(prec=Integer(100))
0.69314718055994530941723212146
>>> exp(_)
2.0000000000000000000000000000
hex()[source]#

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

EXAMPLES:

sage: print(Integer(15).hex())
f
sage: print(Integer(16).hex())
10
sage: print(Integer(16938402384092843092843098243).hex())
36bb1e3929d1a8fe2802f083

>>> from sage.all import *
>>> print(Integer(Integer(15)).hex())
f
>>> print(Integer(Integer(16)).hex())
10
>>> print(Integer(Integer(16938402384092843092843098243)).hex())
36bb1e3929d1a8fe2802f083
imag()[source]#

Return the imaginary part of self, which is zero.

EXAMPLES:

sage: Integer(9).imag()
0

>>> from sage.all import *
>>> Integer(Integer(9)).imag()
0
inverse_mod(n)[source]#

Return the inverse of self modulo \(n\), if this inverse exists.

Otherwise, raise a ZeroDivisionError exception.

INPUT:

  • self – Integer

  • n – Integer, or ideal of integer ring

OUTPUT:

  • x – Integer such that x*self = 1 (mod m), or raises ZeroDivisionError.

IMPLEMENTATION:

Call the mpz_invert GMP library function.

EXAMPLES:

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 of Mod(189, 1890) does not exist
sage: a = Integer(19)**100000  # long time
sage: c = a.inverse_mod(a*a)   # long time
Traceback (most recent call last):
...
ZeroDivisionError: inverse of Mod(..., ...) does not exist

>>> from sage.all import *
>>> a = Integer(Integer(189))
>>> a.inverse_mod(Integer(10000))
4709
>>> a.inverse_mod(-Integer(10000))
4709
>>> a.inverse_mod(Integer(1890))
Traceback (most recent call last):
...
ZeroDivisionError: inverse of Mod(189, 1890) does not exist
>>> a = Integer(Integer(19))**Integer(100000)  # long time
>>> c = a.inverse_mod(a*a)   # long time
Traceback (most recent call last):
...
ZeroDivisionError: inverse of Mod(..., ...) does not exist

We check that Issue #10625 is fixed:

sage: ZZ(2).inverse_mod(ZZ.ideal(3))
2

>>> from sage.all import *
>>> ZZ(Integer(2)).inverse_mod(ZZ.ideal(Integer(3)))
2

We check that Issue #9955 is fixed:

sage: Rational(3) % Rational(-1)
0

>>> from sage.all import *
>>> Rational(Integer(3)) % Rational(-Integer(1))
0
inverse_of_unit()[source]#

Return inverse of self if self is a unit in the integers, i.e., self is \(-1\) or \(1\). Otherwise, raise a ZeroDivisionError.

EXAMPLES:

sage: (1).inverse_of_unit()
1
sage: (-1).inverse_of_unit()
-1
sage: 5.inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: inverse does not exist
sage: 0.inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: inverse does not exist

>>> from sage.all import *
>>> (Integer(1)).inverse_of_unit()
1
>>> (-Integer(1)).inverse_of_unit()
-1
>>> Integer(5).inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: inverse does not exist
>>> Integer(0).inverse_of_unit()
Traceback (most recent call last):
...
ArithmeticError: inverse does not exist
is_discriminant()[source]#

Return True if this integer is a discriminant.

Note

A discriminant is an integer congruent to 0 or 1 modulo 4.

EXAMPLES:

sage: (-1).is_discriminant()
False
sage: (-4).is_discriminant()
True
sage: 100.is_discriminant()
True
sage: 101.is_discriminant()
True

>>> from sage.all import *
>>> (-Integer(1)).is_discriminant()
False
>>> (-Integer(4)).is_discriminant()
True
>>> Integer(100).is_discriminant()
True
>>> Integer(101).is_discriminant()
True
is_fundamental_discriminant()[source]#

Return True if this integer is a fundamental discriminant.

Note

A fundamental discriminant is a discrimimant, not 0 or 1 and not a square multiple of a smaller discriminant.

EXAMPLES:

sage: (-4).is_fundamental_discriminant()                                    # needs sage.libs.pari
True
sage: (-12).is_fundamental_discriminant()
False
sage: 101.is_fundamental_discriminant()                                     # needs sage.libs.pari
True

>>> from sage.all import *
>>> (-Integer(4)).is_fundamental_discriminant()                                    # needs sage.libs.pari
True
>>> (-Integer(12)).is_fundamental_discriminant()
False
>>> Integer(101).is_fundamental_discriminant()                                     # needs sage.libs.pari
True
is_integer()[source]#

Return True as they are integers

EXAMPLES:

sage: sqrt(4).is_integer()
True

>>> from sage.all import *
>>> sqrt(Integer(4)).is_integer()
True
is_integral()[source]#

Return True since integers are integral, i.e., satisfy a monic polynomial with integer coefficients.

EXAMPLES:

sage: Integer(3).is_integral()
True

>>> from sage.all import *
>>> Integer(Integer(3)).is_integral()
True
is_irreducible()[source]#

Return True if self is irreducible, i.e. +/- prime

EXAMPLES:

sage: z = 2^31 - 1
sage: z.is_irreducible()                                                    # needs sage.libs.pari
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

>>> from sage.all import *
>>> z = Integer(2)**Integer(31) - Integer(1)
>>> z.is_irreducible()                                                    # needs sage.libs.pari
True
>>> z = Integer(2)**Integer(31)
>>> z.is_irreducible()
False
>>> z = Integer(7)
>>> z.is_irreducible()
True
>>> z = -Integer(7)
>>> z.is_irreducible()
True
is_norm(K, element=False, proof=True)[source]#

See QQ(self).is_norm().

EXAMPLES:

sage: n = 7
sage: n.is_norm(QQ)
True
sage: n.is_norm(QQ, element=True)
(True, 7)

sage: # needs sage.rings.number_field
sage: x = polygen(ZZ, 'x')
sage: K = NumberField(x^2 - 2, 'beta')
sage: n = 4
sage: n.is_norm(K)
True
sage: 5.is_norm(K)
False
sage: n.is_norm(K, element=True)
(True, -4*beta + 6)
sage: n.is_norm(K, element=True)[1].norm()
4
sage: n = 5
sage: n.is_norm(K, element=True)
(False, None)

>>> from sage.all import *
>>> n = Integer(7)
>>> n.is_norm(QQ)
True
>>> n.is_norm(QQ, element=True)
(True, 7)

>>> # needs sage.rings.number_field
>>> x = polygen(ZZ, 'x')
>>> K = NumberField(x**Integer(2) - Integer(2), 'beta')
>>> n = Integer(4)
>>> n.is_norm(K)
True
>>> Integer(5).is_norm(K)
False
>>> n.is_norm(K, element=True)
(True, -4*beta + 6)
>>> n.is_norm(K, element=True)[Integer(1)].norm()
4
>>> n = Integer(5)
>>> n.is_norm(K, element=True)
(False, None)
is_one()[source]#

Return True if the integer is \(1\), otherwise False.

EXAMPLES:

sage: Integer(1).is_one()
True
sage: Integer(0).is_one()
False

>>> from sage.all import *
>>> Integer(Integer(1)).is_one()
True
>>> Integer(Integer(0)).is_one()
False
is_perfect_power()[source]#

Return True if self is a perfect power, ie if there exist integers \(a\) and \(b\), \(b > 1\) with self \(= a^b\).

See also

EXAMPLES:

sage: Integer(-27).is_perfect_power()
True
sage: Integer(12).is_perfect_power()
False

sage: z = 8
sage: z.is_perfect_power()
True
sage: 144.is_perfect_power()
True
sage: 10.is_perfect_power()
False
sage: (-8).is_perfect_power()
True
sage: (-4).is_perfect_power()
False

>>> from sage.all import *
>>> Integer(-Integer(27)).is_perfect_power()
True
>>> Integer(Integer(12)).is_perfect_power()
False

>>> z = Integer(8)
>>> z.is_perfect_power()
True
>>> Integer(144).is_perfect_power()
True
>>> Integer(10).is_perfect_power()
False
>>> (-Integer(8)).is_perfect_power()
True
>>> (-Integer(4)).is_perfect_power()
False
is_power_of(n)[source]#

Return True if there is an integer \(b\) with \(\mathtt{self} = n^b\).

See also

  • perfect_power(): Finds the minimal base for which this integer is a perfect power.

  • is_perfect_power(): If you don’t know the base but just want to know if this integer is a perfect power, use this function.

  • is_prime_power(): Checks whether the base is prime.

EXAMPLES:

sage: Integer(64).is_power_of(4)
True
sage: Integer(64).is_power_of(16)
False

>>> from sage.all import *
>>> Integer(Integer(64)).is_power_of(Integer(4))
True
>>> Integer(Integer(64)).is_power_of(Integer(16))
False

Note

For large integers self, is_power_of() is faster than is_perfect_power(). The following examples give 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_perfect_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

>>> from sage.all import *
>>> b = lcm(range(Integer(1),Integer(10000)))
>>> b.exact_log(Integer(2))
14446
>>> t = cputime()
>>> for a in range(Integer(2), Integer(1000)): k = b.is_perfect_power()
>>> cputime(t)      # random
0.53203299999999976
>>> t = cputime()
>>> for a in range(Integer(2), Integer(1000)): k = b.is_power_of(Integer(2))
>>> cputime(t)      # random
0.0
>>> t = cputime()
>>> for a in range(Integer(2), Integer(1000)): k = b.is_power_of(Integer(3))
>>> 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):  # note: changed range from the example above
....:     k = b.is_perfect_power()
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

>>> from sage.all import *
>>> b = lcm(range(Integer(1), Integer(1000)))
>>> b.exact_log(Integer(2))
1437
>>> t = cputime()
>>> for a in range(Integer(2), Integer(10000)):  # note: changed range from the example above
...     k = b.is_perfect_power()
>>> cputime(t)      # random
0.17201100000000036
>>> t = cputime(); TWO = int(Integer(2))
>>> for a in range(Integer(2), Integer(10000)): k = b.is_power_of(TWO)
>>> cputime(t)      # random
0.0040000000000000036
>>> t = cputime()
>>> for a in range(Integer(2), Integer(10000)): k = b.is_power_of(Integer(3))
>>> cputime(t)      # random
0.040003000000000011
>>> t = cputime()
>>> for a in range(Integer(2), Integer(10000)): k = b.is_power_of(a)
>>> cputime(t)      # random
0.02800199999999986
is_prime(proof=None)[source]#

Test whether self is prime.

INPUT:

Note

Integer primes are by definition positive! This is different than Magma, but the same as in PARI. See also the is_irreducible() method.

EXAMPLES:

sage: z = 2^31 - 1
sage: z.is_prime()                                                          # needs sage.libs.pari
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

>>> from sage.all import *
>>> z = Integer(2)**Integer(31) - Integer(1)
>>> z.is_prime()                                                          # needs sage.libs.pari
True
>>> z = Integer(2)**Integer(31)
>>> z.is_prime()
False
>>> z = Integer(7)
>>> z.is_prime()
True
>>> z = -Integer(7)
>>> z.is_prime()
False
>>> z.is_irreducible()
True

sage: z = 10^80 + 129
sage: z.is_prime(proof=False)                                               # needs sage.libs.pari
True
sage: z.is_prime(proof=True)                                                # needs sage.libs.pari
True

>>> from sage.all import *
>>> z = Integer(10)**Integer(80) + Integer(129)
>>> z.is_prime(proof=False)                                               # needs sage.libs.pari
True
>>> z.is_prime(proof=True)                                                # needs sage.libs.pari
True

When starting Sage the arithmetic proof flag is True. We can change it to False as follows:

sage: proof.arithmetic()
True
sage: n = 10^100 + 267
sage: timeit("n.is_prime()")        # not tested                            # needs sage.libs.pari
5 loops, best of 3: 163 ms per loop
sage: proof.arithmetic(False)
sage: proof.arithmetic()
False
sage: timeit("n.is_prime()")        # not tested                            # needs sage.libs.pari
1000 loops, best of 3: 573 us per loop

>>> from sage.all import *
>>> proof.arithmetic()
True
>>> n = Integer(10)**Integer(100) + Integer(267)
>>> timeit("n.is_prime()")        # not tested                            # needs sage.libs.pari
5 loops, best of 3: 163 ms per loop
>>> proof.arithmetic(False)
>>> proof.arithmetic()
False
>>> timeit("n.is_prime()")        # not tested                            # needs sage.libs.pari
1000 loops, best of 3: 573 us per loop

ALGORITHM:

Calls the PARI function pari:isprime.

is_prime_power(proof=None, get_data=False)[source]#

Return True if this integer is a prime power, and False otherwise.

A prime power is a prime number raised to a positive power. Hence \(1\) is not a prime power.

For a method that uses a pseudoprimality test instead see is_pseudoprime_power().

INPUT:

  • proof – Boolean or None (default). If False, use a strong pseudo-primality test (see is_pseudoprime()). If True, use a provable primality test. If unset, use the default arithmetic proof flag.

  • get_data – (default False), if True return a pair (p,k) such that this integer equals p^k with p a prime and k a positive integer or the pair (self,0) otherwise.

See also

EXAMPLES:

sage: # needs sage.libs.pari
sage: 17.is_prime_power()
True
sage: 10.is_prime_power()
False
sage: 64.is_prime_power()
True
sage: (3^10000).is_prime_power()
True
sage: (10000).is_prime_power()
False
sage: (-3).is_prime_power()
False
sage: 0.is_prime_power()
False
sage: 1.is_prime_power()
False
sage: p = next_prime(10^20); p
100000000000000000039
sage: p.is_prime_power()
True
sage: (p^97).is_prime_power()
True
sage: (p + 1).is_prime_power()
False

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> Integer(17).is_prime_power()
True
>>> Integer(10).is_prime_power()
False
>>> Integer(64).is_prime_power()
True
>>> (Integer(3)**Integer(10000)).is_prime_power()
True
>>> (Integer(10000)).is_prime_power()
False
>>> (-Integer(3)).is_prime_power()
False
>>> Integer(0).is_prime_power()
False
>>> Integer(1).is_prime_power()
False
>>> p = next_prime(Integer(10)**Integer(20)); p
100000000000000000039
>>> p.is_prime_power()
True
>>> (p**Integer(97)).is_prime_power()
True
>>> (p + Integer(1)).is_prime_power()
False

With the get_data keyword set to True:

sage: # needs sage.libs.pari
sage: (3^100).is_prime_power(get_data=True)
(3, 100)
sage: 12.is_prime_power(get_data=True)
(12, 0)
sage: (p^97).is_prime_power(get_data=True)
(100000000000000000039, 97)
sage: q = p.next_prime(); q
100000000000000000129
sage: (p*q).is_prime_power(get_data=True)
(10000000000000000016800000000000000005031, 0)

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> (Integer(3)**Integer(100)).is_prime_power(get_data=True)
(3, 100)
>>> Integer(12).is_prime_power(get_data=True)
(12, 0)
>>> (p**Integer(97)).is_prime_power(get_data=True)
(100000000000000000039, 97)
>>> q = p.next_prime(); q
100000000000000000129
>>> (p*q).is_prime_power(get_data=True)
(10000000000000000016800000000000000005031, 0)

The method works for large entries when proof=False:

sage: proof.arithmetic(False)
sage: ((10^500 + 961)^4).is_prime_power()                                   # needs sage.libs.pari
True
sage: proof.arithmetic(True)

>>> from sage.all import *
>>> proof.arithmetic(False)
>>> ((Integer(10)**Integer(500) + Integer(961))**Integer(4)).is_prime_power()                                   # needs sage.libs.pari
True
>>> proof.arithmetic(True)

We check that Issue #4777 is fixed:

sage: n = 150607571^14
sage: n.is_prime_power()                                                    # needs sage.libs.pari
True

>>> from sage.all import *
>>> n = Integer(150607571)**Integer(14)
>>> n.is_prime_power()                                                    # needs sage.libs.pari
True
is_pseudoprime()[source]#

Test whether self is a pseudoprime.

This uses PARI’s Baillie-PSW probabilistic primality test. Currently, there are no known pseudoprimes for Baillie-PSW that are not actually prime. However, it is conjectured that there are infinitely many.

See Wikipedia article Baillie-PSW_primality_test

EXAMPLES:

sage: z = 2^31 - 1
sage: z.is_pseudoprime()                                                    # needs sage.libs.pari
True
sage: z = 2^31
sage: z.is_pseudoprime()                                                    # needs sage.libs.pari
False

>>> from sage.all import *
>>> z = Integer(2)**Integer(31) - Integer(1)
>>> z.is_pseudoprime()                                                    # needs sage.libs.pari
True
>>> z = Integer(2)**Integer(31)
>>> z.is_pseudoprime()                                                    # needs sage.libs.pari
False
is_pseudoprime_power(get_data=False)[source]#

Test if this number is a power of a pseudoprime number.

For large numbers, this method might be faster than is_prime_power().

INPUT:

  • get_data – (default False) if True return a pair \((p,k)\) such that this number equals \(p^k\) with \(p\) a pseudoprime and \(k\) a positive integer or the pair (self,0) otherwise.

EXAMPLES:

sage: # needs sage.libs.pari
sage: x = 10^200 + 357
sage: x.is_pseudoprime()
True
sage: (x^12).is_pseudoprime_power()
True
sage: (x^12).is_pseudoprime_power(get_data=True)
(1000...000357, 12)
sage: (997^100).is_pseudoprime_power()
True
sage: (998^100).is_pseudoprime_power()
False
sage: ((10^1000 + 453)^2).is_pseudoprime_power()
True

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> x = Integer(10)**Integer(200) + Integer(357)
>>> x.is_pseudoprime()
True
>>> (x**Integer(12)).is_pseudoprime_power()
True
>>> (x**Integer(12)).is_pseudoprime_power(get_data=True)
(1000...000357, 12)
>>> (Integer(997)**Integer(100)).is_pseudoprime_power()
True
>>> (Integer(998)**Integer(100)).is_pseudoprime_power()
False
>>> ((Integer(10)**Integer(1000) + Integer(453))**Integer(2)).is_pseudoprime_power()
True
is_rational()[source]#

Return True as an integer is a rational number.

EXAMPLES:

sage: 5.is_rational()
True

>>> from sage.all import *
>>> Integer(5).is_rational()
True
is_square()[source]#

Return True if self is a perfect square.

EXAMPLES:

sage: Integer(4).is_square()
True
sage: Integer(41).is_square()
False

>>> from sage.all import *
>>> Integer(Integer(4)).is_square()
True
>>> Integer(Integer(41)).is_square()
False
is_squarefree()[source]#

Return True if this integer is not divisible by the square of any prime and False otherwise.

EXAMPLES:

sage: 100.is_squarefree()                                                   # needs sage.libs.pari
False
sage: 102.is_squarefree()                                                   # needs sage.libs.pari
True
sage: 0.is_squarefree()                                                     # needs sage.libs.pari
False

>>> from sage.all import *
>>> Integer(100).is_squarefree()                                                   # needs sage.libs.pari
False
>>> Integer(102).is_squarefree()                                                   # needs sage.libs.pari
True
>>> Integer(0).is_squarefree()                                                     # needs sage.libs.pari
False
is_unit()[source]#

Return True if this integer is a unit, i.e., \(1\) or \(-1\).

EXAMPLES:

sage: for n in srange(-2,3):
....:     print("{} {}".format(n, n.is_unit()))
-2 False
-1 True
0 False
1 True
2 False

>>> from sage.all import *
>>> for n in srange(-Integer(2),Integer(3)):
...     print("{} {}".format(n, n.is_unit()))
-2 False
-1 True
0 False
1 True
2 False
isqrt()[source]#

Return the integer floor of the square root of self, or raises an ValueError if self is negative.

EXAMPLES:

sage: a = Integer(5)
sage: a.isqrt()
2

>>> from sage.all import *
>>> a = Integer(Integer(5))
>>> a.isqrt()
2

sage: Integer(-102).isqrt()
Traceback (most recent call last):
...
ValueError: square root of negative integer not defined

>>> from sage.all import *
>>> Integer(-Integer(102)).isqrt()
Traceback (most recent call last):
...
ValueError: square root of negative integer not defined
jacobi(b)[source]#

Calculate the Jacobi symbol \(\left(\frac{\text{self}}{b}\right)\).

EXAMPLES:

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

>>> from sage.all import *
>>> z = -Integer(1)
>>> z.jacobi(Integer(17))
1
>>> z.jacobi(Integer(19))
-1
>>> z.jacobi(Integer(17)*Integer(19))
-1
>>> (Integer(2)).jacobi(Integer(17))
1
>>> (Integer(3)).jacobi(Integer(19))
-1
>>> (Integer(6)).jacobi(Integer(17)*Integer(19))
-1
>>> (Integer(6)).jacobi(Integer(33))
0
>>> a = Integer(3); b = Integer(7)
>>> a.jacobi(b) == -b.jacobi(a)
True
kronecker(b)[source]#

Calculate the Kronecker symbol \(\left(\frac{\text{self}}{b}\right)\) with the Kronecker extension \((\text{self}/2)=(2/\text{self})\) when self is odd, or \((\text{self}/2)=0\) when self is even.

EXAMPLES:

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

>>> from sage.all import *
>>> z = Integer(5)
>>> z.kronecker(Integer(41))
1
>>> z.kronecker(Integer(43))
-1
>>> z.kronecker(Integer(8))
-1
>>> z.kronecker(Integer(15))
0
>>> a = Integer(2); b = Integer(5)
>>> a.kronecker(b) == b.kronecker(a)
True
list()[source]#

Return a list with this integer in it, to be compatible with the method for number fields.

EXAMPLES:

sage: m = 5
sage: m.list()
[5]

>>> from sage.all import *
>>> m = Integer(5)
>>> m.list()
[5]
log(m=None, prec=None)[source]#

Return symbolic log by default, unless the logarithm is exact (for an integer argument). When prec is given, the RealField approximation to that bit precision is used.

This function is provided primarily so that Sage integers may be treated in the same manner as real numbers when convenient. Direct use of exact_log() is probably best for arithmetic log computation.

INPUT:

  • m – default: natural log base e

  • prec – integer (default: None): if None, returns symbolic, else to given bits of precision as in RealField

EXAMPLES:

sage: Integer(124).log(5)                                                   # needs sage.symbolic
log(124)/log(5)
sage: Integer(124).log(5, 100)                                              # needs sage.rings.real_mpfr
2.9950093311241087454822446806
sage: Integer(125).log(5)
3
sage: Integer(125).log(5, prec=53)                                          # needs sage.rings.real_mpfr
3.00000000000000
sage: log(Integer(125))                                                     # needs sage.symbolic
3*log(5)

>>> from sage.all import *
>>> Integer(Integer(124)).log(Integer(5))                                                   # needs sage.symbolic
log(124)/log(5)
>>> Integer(Integer(124)).log(Integer(5), Integer(100))                                              # needs sage.rings.real_mpfr
2.9950093311241087454822446806
>>> Integer(Integer(125)).log(Integer(5))
3
>>> Integer(Integer(125)).log(Integer(5), prec=Integer(53))                                          # needs sage.rings.real_mpfr
3.00000000000000
>>> log(Integer(Integer(125)))                                                     # needs sage.symbolic
3*log(5)

For extremely large numbers, this works:

sage: x = 3^100000
sage: log(x, 3)                                                             # needs sage.rings.real_interval_field
100000

>>> from sage.all import *
>>> x = Integer(3)**Integer(100000)
>>> log(x, Integer(3))                                                             # needs sage.rings.real_interval_field
100000

Also log(x), giving a symbolic output, works in a reasonable amount of time for this x:

sage: x = 3^100000
sage: log(x)                                                                # needs sage.symbolic
log(1334971414230...5522000001)

>>> from sage.all import *
>>> x = Integer(3)**Integer(100000)
>>> log(x)                                                                # needs sage.symbolic
log(1334971414230...5522000001)

But approximations are probably more useful in this case, and work to as high a precision as we desire:

sage: x.log(3, 53)  # default precision for RealField                       # needs sage.rings.real_mpfr
100000.000000000
sage: (x + 1).log(3, 53)                                                    # needs sage.rings.real_mpfr
100000.000000000
sage: (x + 1).log(3, 1000)                                                  # needs sage.rings.real_mpfr
100000.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

>>> from sage.all import *
>>> x.log(Integer(3), Integer(53))  # default precision for RealField                       # needs sage.rings.real_mpfr
100000.000000000
>>> (x + Integer(1)).log(Integer(3), Integer(53))                                                    # needs sage.rings.real_mpfr
100000.000000000
>>> (x + Integer(1)).log(Integer(3), Integer(1000))                                                  # needs sage.rings.real_mpfr
100000.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

We can use non-integer bases, with default e:

sage: x.log(2.5, prec=53)                                                   # needs sage.rings.real_mpfr
119897.784671579

>>> from sage.all import *
>>> x.log(RealNumber('2.5'), prec=Integer(53))                                                   # needs sage.rings.real_mpfr
119897.784671579

We also get logarithms of negative integers, via the symbolic ring, using the branch from \(-\pi\) to \(\pi\):

sage: log(-1)                                                               # needs sage.symbolic
I*pi

>>> from sage.all import *
>>> log(-Integer(1))                                                               # needs sage.symbolic
I*pi

The logarithm of zero is done likewise:

sage: log(0)                                                                # needs sage.symbolic
-Infinity

>>> from sage.all import *
>>> log(Integer(0))                                                                # needs sage.symbolic
-Infinity

Some rational bases yield integer logarithms (Issue #21517):

sage: ZZ(8).log(1/2)
-3

>>> from sage.all import *
>>> ZZ(Integer(8)).log(Integer(1)/Integer(2))
-3

Check that Python ints are accepted (Issue #21518):

sage: ZZ(8).log(int(2))
3

>>> from sage.all import *
>>> ZZ(Integer(8)).log(int(Integer(2)))
3
multifactorial(k)[source]#

Compute the k-th factorial \(n!^{(k)}\) of self.

The multifactorial number \(n!^{(k)}\) is defined for non-negative integers \(n\) as follows. For \(k=1\) this is the standard factorial, and for \(k\) greater than \(1\) it is the product of every \(k\)-th terms down from \(n\) to \(1\). The recursive definition is used to extend this function to the negative integers \(n\).

This function uses direct call to GMP if \(k\) and \(n\) are non-negative and uses simple transformation for other cases.

EXAMPLES:

sage: 5.multifactorial(1)
120
sage: 5.multifactorial(2)
15
sage: 5.multifactorial(3)
10

sage: 23.multifactorial(2)
316234143225
sage: prod([1..23, step=2])
316234143225

sage: (-29).multifactorial(7)
1/2640
sage: (-3).multifactorial(5)
1/2
sage: (-9).multifactorial(3)
Traceback (most recent call last):
...
ValueError: multifactorial undefined

>>> from sage.all import *
>>> Integer(5).multifactorial(Integer(1))
120
>>> Integer(5).multifactorial(Integer(2))
15
>>> Integer(5).multifactorial(Integer(3))
10

>>> Integer(23).multifactorial(Integer(2))
316234143225
>>> prod((ellipsis_range(Integer(1),Ellipsis,Integer(23), step=Integer(2))))
316234143225

>>> (-Integer(29)).multifactorial(Integer(7))
1/2640
>>> (-Integer(3)).multifactorial(Integer(5))
1/2
>>> (-Integer(9)).multifactorial(Integer(3))
Traceback (most recent call last):
...
ValueError: multifactorial undefined

When entries are too large an OverflowError is raised:

sage: (2**64).multifactorial(2)
Traceback (most recent call last):
...
OverflowError: argument too large for multifactorial

>>> from sage.all import *
>>> (Integer(2)**Integer(64)).multifactorial(Integer(2))
Traceback (most recent call last):
...
OverflowError: argument too large for multifactorial
multiplicative_order()[source]#

Return the multiplicative order of self.

EXAMPLES:

sage: ZZ(1).multiplicative_order()
1
sage: ZZ(-1).multiplicative_order()
2
sage: ZZ(0).multiplicative_order()
+Infinity
sage: ZZ(2).multiplicative_order()
+Infinity

>>> from sage.all import *
>>> ZZ(Integer(1)).multiplicative_order()
1
>>> ZZ(-Integer(1)).multiplicative_order()
2
>>> ZZ(Integer(0)).multiplicative_order()
+Infinity
>>> ZZ(Integer(2)).multiplicative_order()
+Infinity
nbits()[source]#

Alias for bit_length().

ndigits(base=10)[source]#

Return the number of digits of self expressed in the given base.

INPUT:

  • base – integer (default: 10)

EXAMPLES:

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()                                                           # needs sage.rings.real_interval_field
3000001
sage: n = 1000**1000000-1
sage: n.ndigits()                                                           # needs sage.rings.real_interval_field
3000000
sage: n = 10**10000000-10**9999990
sage: n.ndigits()                                                           # needs sage.rings.real_interval_field
10000000

>>> from sage.all import *
>>> n = Integer(52)
>>> n.ndigits()
2
>>> n = -Integer(10003)
>>> n.ndigits()
5
>>> n = Integer(15)
>>> n.ndigits(Integer(2))
4
>>> n = Integer(1000)**Integer(1000000)+Integer(1)
>>> n.ndigits()                                                           # needs sage.rings.real_interval_field
3000001
>>> n = Integer(1000)**Integer(1000000)-Integer(1)
>>> n.ndigits()                                                           # needs sage.rings.real_interval_field
3000000
>>> n = Integer(10)**Integer(10000000)-Integer(10)**Integer(9999990)
>>> n.ndigits()                                                           # needs sage.rings.real_interval_field
10000000
next_prime(proof=None)[source]#

Return the next prime after self.

This method calls the PARI function pari:nextprime.

INPUT:

  • proof – bool or None (default: None, see proof.arithmetic or sage.structure.proof) Note that the global Sage default is proof=True

EXAMPLES:

sage: 100.next_prime()                                                      # needs sage.libs.pari
101
sage: (10^50).next_prime()                                                  # needs sage.libs.pari
100000000000000000000000000000000000000000000000151

>>> from sage.all import *
>>> Integer(100).next_prime()                                                      # needs sage.libs.pari
101
>>> (Integer(10)**Integer(50)).next_prime()                                                  # needs sage.libs.pari
100000000000000000000000000000000000000000000000151

Use proof=False, which is way faster since it does not need a primality proof:

sage: b = (2^1024).next_prime(proof=False)                                  # needs sage.libs.pari
sage: b - 2^1024                                                            # needs sage.libs.pari
643

>>> from sage.all import *
>>> b = (Integer(2)**Integer(1024)).next_prime(proof=False)                                  # needs sage.libs.pari
>>> b - Integer(2)**Integer(1024)                                                            # needs sage.libs.pari
643

sage: Integer(0).next_prime()                                               # needs sage.libs.pari
2
sage: Integer(1001).next_prime()                                            # needs sage.libs.pari
1009

>>> from sage.all import *
>>> Integer(Integer(0)).next_prime()                                               # needs sage.libs.pari
2
>>> Integer(Integer(1001)).next_prime()                                            # needs sage.libs.pari
1009
next_prime_power(proof=None)[source]#

Return the next prime power after self.

INPUT:

  • proof – if True ensure that the returned value is the next prime power and if set to False uses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (see proof.arithmetic or sage.structure.proof).

ALGORITHM:

The algorithm is naive. It computes the next power of 2 and goes through the odd numbers calling is_prime_power().

See also

EXAMPLES:

sage: (-1).next_prime_power()
2
sage: 2.next_prime_power()
3
sage: 103.next_prime_power()                                                # needs sage.libs.pari
107
sage: 107.next_prime_power()
109
sage: 2044.next_prime_power()                                               # needs sage.libs.pari
2048

>>> from sage.all import *
>>> (-Integer(1)).next_prime_power()
2
>>> Integer(2).next_prime_power()
3
>>> Integer(103).next_prime_power()                                                # needs sage.libs.pari
107
>>> Integer(107).next_prime_power()
109
>>> Integer(2044).next_prime_power()                                               # needs sage.libs.pari
2048
next_probable_prime()[source]#

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

EXAMPLES:

sage: # needs sage.libs.pari
sage: (-37).next_probable_prime()
2
sage: (100).next_probable_prime()
101
sage: (2^512).next_probable_prime()
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
sage: 0.next_probable_prime()
2
sage: 126.next_probable_prime()
127
sage: 144168.next_probable_prime()
144169

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> (-Integer(37)).next_probable_prime()
2
>>> (Integer(100)).next_probable_prime()
101
>>> (Integer(2)**Integer(512)).next_probable_prime()
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171
>>> Integer(0).next_probable_prime()
2
>>> Integer(126).next_probable_prime()
127
>>> Integer(144168).next_probable_prime()
144169
nth_root(n, truncate_mode=0)[source]#

Return the (possibly truncated) n-th root of self.

INPUT:

  • n – integer \(\geq 1\) (must fit in the C int type).

  • truncate_mode – boolean, whether to allow truncation if self is not an n-th power.

OUTPUT:

If truncate_mode is 0 (default), then returns the exact n’th root if self is an n’th power, or raises a ValueError if it is not.

If truncate_mode is 1, then if either n is odd or self is positive, returns a pair (root, exact_flag) where root is the truncated n-th root (rounded towards zero) and exact_flag is a boolean indicating whether the root extraction was exact; otherwise raises a ValueError.

AUTHORS:

  • David Harvey (2006-09-15)

  • Interface changed by John Cremona (2009-04-04)

EXAMPLES:

sage: Integer(125).nth_root(3)
5
sage: Integer(124).nth_root(3)
Traceback (most recent call last):
...
ValueError: 124 is not a 3rd power
sage: Integer(124).nth_root(3, truncate_mode=1)
(4, False)
sage: Integer(125).nth_root(3, truncate_mode=1)
(5, True)
sage: Integer(126).nth_root(3, truncate_mode=1)
(5, False)

>>> from sage.all import *
>>> Integer(Integer(125)).nth_root(Integer(3))
5
>>> Integer(Integer(124)).nth_root(Integer(3))
Traceback (most recent call last):
...
ValueError: 124 is not a 3rd power
>>> Integer(Integer(124)).nth_root(Integer(3), truncate_mode=Integer(1))
(4, False)
>>> Integer(Integer(125)).nth_root(Integer(3), truncate_mode=Integer(1))
(5, True)
>>> Integer(Integer(126)).nth_root(Integer(3), truncate_mode=Integer(1))
(5, False)

sage: Integer(-125).nth_root(3)
-5
sage: Integer(-125).nth_root(3,truncate_mode=1)
(-5, True)
sage: Integer(-124).nth_root(3,truncate_mode=1)
(-4, False)
sage: Integer(-126).nth_root(3,truncate_mode=1)
(-5, False)

>>> from sage.all import *
>>> Integer(-Integer(125)).nth_root(Integer(3))
-5
>>> Integer(-Integer(125)).nth_root(Integer(3),truncate_mode=Integer(1))
(-5, True)
>>> Integer(-Integer(124)).nth_root(Integer(3),truncate_mode=Integer(1))
(-4, False)
>>> Integer(-Integer(126)).nth_root(Integer(3),truncate_mode=Integer(1))
(-5, False)

sage: Integer(125).nth_root(2, True)
(11, False)
sage: Integer(125).nth_root(3, True)
(5, True)

>>> from sage.all import *
>>> Integer(Integer(125)).nth_root(Integer(2), True)
(11, False)
>>> Integer(Integer(125)).nth_root(Integer(3), True)
(5, True)

sage: Integer(125).nth_root(-5)
Traceback (most recent call last):
...
ValueError: n (=-5) must be positive

>>> from sage.all import *
>>> Integer(Integer(125)).nth_root(-Integer(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

>>> from sage.all import *
>>> Integer(-Integer(25)).nth_root(Integer(2))
Traceback (most recent call last):
...
ValueError: cannot take even root of negative number

sage: a=9
sage: a.nth_root(3)
Traceback (most recent call last):
...
ValueError: 9 is not a 3rd power

sage: a.nth_root(22)
Traceback (most recent call last):
...
ValueError: 9 is not a 22nd power

sage: ZZ(2^20).nth_root(21)
Traceback (most recent call last):
...
ValueError: 1048576 is not a 21st power

sage: ZZ(2^20).nth_root(21, truncate_mode=1)
(1, False)

>>> from sage.all import *
>>> a=Integer(9)
>>> a.nth_root(Integer(3))
Traceback (most recent call last):
...
ValueError: 9 is not a 3rd power

>>> a.nth_root(Integer(22))
Traceback (most recent call last):
...
ValueError: 9 is not a 22nd power

>>> ZZ(Integer(2)**Integer(20)).nth_root(Integer(21))
Traceback (most recent call last):
...
ValueError: 1048576 is not a 21st power

>>> ZZ(Integer(2)**Integer(20)).nth_root(Integer(21), truncate_mode=Integer(1))
(1, False)
numerator()[source]#

Return the numerator of this integer.

EXAMPLES:

sage: x = 5
sage: x.numerator()
5

>>> from sage.all import *
>>> x = Integer(5)
>>> x.numerator()
5

sage: x = 0
sage: x.numerator()
0

>>> from sage.all import *
>>> x = Integer(0)
>>> x.numerator()
0
oct()[source]#

Return the digits of self in base 8.

Note

‘0’ (or ‘0o’) is not prepended to the result like is done by the corresponding Python function on int. 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.

EXAMPLES:

sage: print(Integer(800).oct())
1440
sage: print(Integer(8).oct())
10
sage: print(Integer(-50).oct())
-62
sage: print(Integer(-899).oct())
-1603
sage: print(Integer(16938402384092843092843098243).oct())
15535436162247215217705000570203

>>> from sage.all import *
>>> print(Integer(Integer(800)).oct())
1440
>>> print(Integer(Integer(8)).oct())
10
>>> print(Integer(-Integer(50)).oct())
-62
>>> print(Integer(-Integer(899)).oct())
-1603
>>> print(Integer(Integer(16938402384092843092843098243)).oct())
15535436162247215217705000570203

Behavior of Sage integers vs. Python integers:

sage: Integer(10).oct()
'12'
sage: oct(int(10))
'0o12'

sage: Integer(-23).oct()
'-27'
sage: oct(int(-23))
'-0o27'

>>> from sage.all import *
>>> Integer(Integer(10)).oct()
'12'
>>> oct(int(Integer(10)))
'0o12'

>>> Integer(-Integer(23)).oct()
'-27'
>>> oct(int(-Integer(23)))
'-0o27'
odd_part()[source]#

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

IMPLEMENTATION:

Currently returns 0 when self is 0. This behaviour is fairly arbitrary, and in Sage 4.6 this special case was not handled at all, eventually propagating a TypeError. The caller should not rely on the behaviour in case self is 0.

EXAMPLES:

sage: odd_part(5)
5
sage: odd_part(4)
1
sage: odd_part(factorial(31))
122529844256906551386796875

>>> from sage.all import *
>>> odd_part(Integer(5))
5
>>> odd_part(Integer(4))
1
>>> odd_part(factorial(Integer(31)))
122529844256906551386796875
ord(p)[source]#

Return the p-adic valuation of self.

INPUT:

  • p – an integer at least 2.

EXAMPLES:

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.

>>> from sage.all import *
>>> n = Integer(60)
>>> n.valuation(Integer(2))
2
>>> n.valuation(Integer(3))
1
>>> n.valuation(Integer(7))
0
>>> n.valuation(Integer(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

>>> from sage.all import *
>>> (Integer(2)**Integer(11)).valuation(Integer(4))
5
ordinal_str()[source]#

Return a string representation of the ordinal associated to self.

EXAMPLES:

sage: [ZZ(n).ordinal_str() for n in range(25)]
['0th',
'1st',
'2nd',
'3rd',
'4th',
...
'10th',
'11th',
'12th',
'13th',
'14th',
...
'20th',
'21st',
'22nd',
'23rd',
'24th']

sage: ZZ(1001).ordinal_str()
'1001st'

sage: ZZ(113).ordinal_str()
'113th'
sage: ZZ(112).ordinal_str()
'112th'
sage: ZZ(111).ordinal_str()
'111th'

>>> from sage.all import *
>>> [ZZ(n).ordinal_str() for n in range(Integer(25))]
['0th',
'1st',
'2nd',
'3rd',
'4th',
...
'10th',
'11th',
'12th',
'13th',
'14th',
...
'20th',
'21st',
'22nd',
'23rd',
'24th']

>>> ZZ(Integer(1001)).ordinal_str()
'1001st'

>>> ZZ(Integer(113)).ordinal_str()
'113th'
>>> ZZ(Integer(112)).ordinal_str()
'112th'
>>> ZZ(Integer(111)).ordinal_str()
'111th'
p_primary_part(p)[source]#

Return the p-primary part of self.

INPUT:

  • p – a prime integer.

OUTPUT: Largest power of p dividing self.

EXAMPLES:

sage: n = 40
sage: n.p_primary_part(2)
8
sage: n.p_primary_part(5)
5
sage: n.p_primary_part(7)
1
sage: n.p_primary_part(6)
Traceback (most recent call last):
...
ValueError: 6 is not a prime number

>>> from sage.all import *
>>> n = Integer(40)
>>> n.p_primary_part(Integer(2))
8
>>> n.p_primary_part(Integer(5))
5
>>> n.p_primary_part(Integer(7))
1
>>> n.p_primary_part(Integer(6))
Traceback (most recent call last):
...
ValueError: 6 is not a prime number
perfect_power()[source]#

Return (a, b), where this integer is \(a^b\) and \(b\) is maximal.

If called on \(-1\), \(0\) or \(1\), \(b\) will be \(1\), since there is no maximal value of \(b\).

See also

  • is_perfect_power(): testing whether an integer is a perfect power is usually faster than finding \(a\) and \(b\).

  • is_prime_power(): checks whether the base is prime.

  • is_power_of(): if you know the base already, this method is the fastest option.

EXAMPLES:

sage: 144.perfect_power()                                                   # needs sage.libs.pari
(12, 2)
sage: 1.perfect_power()
(1, 1)
sage: 0.perfect_power()
(0, 1)
sage: (-1).perfect_power()
(-1, 1)
sage: (-8).perfect_power()                                                  # needs sage.libs.pari
(-2, 3)
sage: (-4).perfect_power()
(-4, 1)
sage: (101^29).perfect_power()                                              # needs sage.libs.pari
(101, 29)
sage: (-243).perfect_power()                                                # needs sage.libs.pari
(-3, 5)
sage: (-64).perfect_power()                                                 # needs sage.libs.pari
(-4, 3)

>>> from sage.all import *
>>> Integer(144).perfect_power()                                                   # needs sage.libs.pari
(12, 2)
>>> Integer(1).perfect_power()
(1, 1)
>>> Integer(0).perfect_power()
(0, 1)
>>> (-Integer(1)).perfect_power()
(-1, 1)
>>> (-Integer(8)).perfect_power()                                                  # needs sage.libs.pari
(-2, 3)
>>> (-Integer(4)).perfect_power()
(-4, 1)
>>> (Integer(101)**Integer(29)).perfect_power()                                              # needs sage.libs.pari
(101, 29)
>>> (-Integer(243)).perfect_power()                                                # needs sage.libs.pari
(-3, 5)
>>> (-Integer(64)).perfect_power()                                                 # needs sage.libs.pari
(-4, 3)
popcount()[source]#

Return the number of 1 bits in the binary representation. If self < 0, we return Infinity.

EXAMPLES:

sage: n = 123
sage: n.str(2)
'1111011'
sage: n.popcount()
6

sage: n = -17
sage: n.popcount()
+Infinity

>>> from sage.all import *
>>> n = Integer(123)
>>> n.str(Integer(2))
'1111011'
>>> n.popcount()
6

>>> n = -Integer(17)
>>> n.popcount()
+Infinity
powermod(exp, mod)[source]#

Compute self**exp modulo mod.

EXAMPLES:

sage: z = 2
sage: z.powermod(31,31)
2
sage: z.powermod(0,31)
1
sage: z.powermod(-31,31) == 2^-31 % 31
True

>>> from sage.all import *
>>> z = Integer(2)
>>> z.powermod(Integer(31),Integer(31))
2
>>> z.powermod(Integer(0),Integer(31))
1
>>> z.powermod(-Integer(31),Integer(31)) == Integer(2)**-Integer(31) % Integer(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

>>> from sage.all import *
>>> z.powermod(Integer(31),Integer(0))
Traceback (most recent call last):
...
ZeroDivisionError: cannot raise to a power modulo 0
previous_prime(proof=None)[source]#

Return the previous prime before self.

This method calls the PARI function pari:precprime.

INPUT:

  • proof – if True ensure that the returned value is the next prime power and if set to False uses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (see proof.arithmetic or sage.structure.proof).

See also

EXAMPLES:

sage: 10.previous_prime()                                                   # needs sage.libs.pari
7
sage: 7.previous_prime()                                                    # needs sage.libs.pari
5
sage: 14376485.previous_prime()                                             # needs sage.libs.pari
14376463

sage: 2.previous_prime()
Traceback (most recent call last):
...
ValueError: no prime less than 2

>>> from sage.all import *
>>> Integer(10).previous_prime()                                                   # needs sage.libs.pari
7
>>> Integer(7).previous_prime()                                                    # needs sage.libs.pari
5
>>> Integer(14376485).previous_prime()                                             # needs sage.libs.pari
14376463

>>> Integer(2).previous_prime()
Traceback (most recent call last):
...
ValueError: no prime less than 2

An example using proof=False, which is way faster since it does not need a primality proof:

sage: b = (2^1024).previous_prime(proof=False)                              # needs sage.libs.pari
sage: 2^1024 - b                                                            # needs sage.libs.pari
105

>>> from sage.all import *
>>> b = (Integer(2)**Integer(1024)).previous_prime(proof=False)                              # needs sage.libs.pari
>>> Integer(2)**Integer(1024) - b                                                            # needs sage.libs.pari
105
previous_prime_power(proof=None)[source]#

Return the previous prime power before self.

INPUT:

  • proof – if True ensure that the returned value is the next prime power and if set to False uses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (see proof.arithmetic or sage.structure.proof).

ALGORITHM:

The algorithm is naive. It computes the previous power of 2 and goes through the odd numbers calling the method is_prime_power().

See also

EXAMPLES:

sage: # needs sage.libs.pari
sage: 3.previous_prime_power()
2
sage: 103.previous_prime_power()
101
sage: 107.previous_prime_power()
103
sage: 2044.previous_prime_power()
2039

sage: 2.previous_prime_power()
Traceback (most recent call last):
...
ValueError: no prime power less than 2

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> Integer(3).previous_prime_power()
2
>>> Integer(103).previous_prime_power()
101
>>> Integer(107).previous_prime_power()
103
>>> Integer(2044).previous_prime_power()
2039

>>> Integer(2).previous_prime_power()
Traceback (most recent call last):
...
ValueError: no prime power less than 2
prime_divisors(*args, **kwds)[source]#

Return the prime divisors of this integer, sorted in increasing order.

If this integer is negative, we do not include \(-1\) among its prime divisors, since \(-1\) is not a prime number.

INPUT:

  • limit – (integer, optional keyword argument) Return only prime divisors up to this bound, and the factorization is done by checking primes up to limit using trial division.

Any additional arguments are passed on to the factor() method.

EXAMPLES:

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]

>>> from sage.all import *
>>> a = Integer(1); a.prime_divisors()
[]
>>> a = Integer(100); a.prime_divisors()
[2, 5]
>>> a = -Integer(100); a.prime_divisors()
[2, 5]
>>> a = Integer(2004); a.prime_divisors()
[2, 3, 167]

Setting the optional limit argument works as expected:

sage: a = 10^100 + 1
sage: a.prime_divisors()                                                    # needs sage.libs.pari
[73, 137, 401, 1201, 1601, 1676321, 5964848081,
 129694419029057750551385771184564274499075700947656757821537291527196801]
sage: a.prime_divisors(limit=10^3)
[73, 137, 401]
sage: a.prime_divisors(limit=10^7)
[73, 137, 401, 1201, 1601, 1676321]

>>> from sage.all import *
>>> a = Integer(10)**Integer(100) + Integer(1)
>>> a.prime_divisors()                                                    # needs sage.libs.pari
[73, 137, 401, 1201, 1601, 1676321, 5964848081,
 129694419029057750551385771184564274499075700947656757821537291527196801]
>>> a.prime_divisors(limit=Integer(10)**Integer(3))
[73, 137, 401]
>>> a.prime_divisors(limit=Integer(10)**Integer(7))
[73, 137, 401, 1201, 1601, 1676321]
prime_factors(*args, **kwds)[source]#

Return the prime divisors of this integer, sorted in increasing order.

If this integer is negative, we do not include \(-1\) among its prime divisors, since \(-1\) is not a prime number.

INPUT:

  • limit – (integer, optional keyword argument) Return only prime divisors up to this bound, and the factorization is done by checking primes up to limit using trial division.

Any additional arguments are passed on to the factor() method.

EXAMPLES:

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]

>>> from sage.all import *
>>> a = Integer(1); a.prime_divisors()
[]
>>> a = Integer(100); a.prime_divisors()
[2, 5]
>>> a = -Integer(100); a.prime_divisors()
[2, 5]
>>> a = Integer(2004); a.prime_divisors()
[2, 3, 167]

Setting the optional limit argument works as expected:

sage: a = 10^100 + 1
sage: a.prime_divisors()                                                    # needs sage.libs.pari
[73, 137, 401, 1201, 1601, 1676321, 5964848081,
 129694419029057750551385771184564274499075700947656757821537291527196801]
sage: a.prime_divisors(limit=10^3)
[73, 137, 401]
sage: a.prime_divisors(limit=10^7)
[73, 137, 401, 1201, 1601, 1676321]

>>> from sage.all import *
>>> a = Integer(10)**Integer(100) + Integer(1)
>>> a.prime_divisors()                                                    # needs sage.libs.pari
[73, 137, 401, 1201, 1601, 1676321, 5964848081,
 129694419029057750551385771184564274499075700947656757821537291527196801]
>>> a.prime_divisors(limit=Integer(10)**Integer(3))
[73, 137, 401]
>>> a.prime_divisors(limit=Integer(10)**Integer(7))
[73, 137, 401, 1201, 1601, 1676321]
prime_to_m_part(m)[source]#

Return the prime-to-\(m\) part of self, i.e., the largest divisor of self that is coprime to \(m\).

INPUT:

  • m – Integer

OUTPUT: Integer

EXAMPLES:

sage: 43434.prime_to_m_part(20)
21717
sage: 2048.prime_to_m_part(2)
1
sage: 2048.prime_to_m_part(3)
2048

sage: 0.prime_to_m_part(2)
Traceback (most recent call last):
...
ArithmeticError: self must be nonzero

>>> from sage.all import *
>>> Integer(43434).prime_to_m_part(Integer(20))
21717
>>> Integer(2048).prime_to_m_part(Integer(2))
1
>>> Integer(2048).prime_to_m_part(Integer(3))
2048

>>> Integer(0).prime_to_m_part(Integer(2))
Traceback (most recent call last):
...
ArithmeticError: self must be nonzero
quo_rem(other)[source]#

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

  • other – the divisor

OUTPUT:

  • q – the quotient of self/other

  • r – the remainder of self/other

EXAMPLES:

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: Integer division by zero

sage: a = ZZ.random_element(10**50)
sage: b = ZZ.random_element(10**15)
sage: q, r = a.quo_rem(b)
sage: q*b + r == a
True

sage: 3.quo_rem(ZZ['x'].0)
(0, 3)

>>> from sage.all import *
>>> z = Integer(Integer(231))
>>> z.quo_rem(Integer(2))
(115, 1)
>>> z.quo_rem(-Integer(2))
(-116, -1)
>>> z.quo_rem(Integer(0))
Traceback (most recent call last):
...
ZeroDivisionError: Integer division by zero

>>> a = ZZ.random_element(Integer(10)**Integer(50))
>>> b = ZZ.random_element(Integer(10)**Integer(15))
>>> q, r = a.quo_rem(b)
>>> q*b + r == a
True

>>> Integer(3).quo_rem(ZZ['x'].gen(0))
(0, 3)
rational_reconstruction(m)[source]#

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

INPUT:

  • self – Integer

  • m – Integer

OUTPUT:

EXAMPLES:

sage: (3/7)%100
29
sage: (29).rational_reconstruction(100)
3/7

>>> from sage.all import *
>>> (Integer(3)/Integer(7))%Integer(100)
29
>>> (Integer(29)).rational_reconstruction(Integer(100))
3/7
real()[source]#

Return the real part of self, which is self.

EXAMPLES:

sage: Integer(-4).real()
-4

>>> from sage.all import *
>>> Integer(-Integer(4)).real()
-4
round(mode='away')[source]#

Return the nearest integer to self, which is self since self is an integer.

EXAMPLES:

This example addresses Issue #23502:

sage: n = 6
sage: n.round()
6

>>> from sage.all import *
>>> n = Integer(6)
>>> n.round()
6
sign()[source]#

Return the sign of this integer, which is \(-1\), \(0\), or \(1\) depending on whether this number is negative, zero, or positive respectively.

OUTPUT: Integer

EXAMPLES:

sage: 500.sign()
1
sage: 0.sign()
0
sage: (-10^43).sign()
-1

>>> from sage.all import *
>>> Integer(500).sign()
1
>>> Integer(0).sign()
0
>>> (-Integer(10)**Integer(43)).sign()
-1
sqrt(prec=None, extend=True, all=False)[source]#

The square root function.

INPUT:

  • prec – integer (default: None): if None, return an exact square root; otherwise return a numerical square root, to the given bits of precision.

  • extend – bool (default: True); if True, return a square root in an extension ring, if necessary. Otherwise, raise a ValueError if the square is not in the base ring. Ignored if prec is not None.

  • all – bool (default: False); if True, return all square roots of self (a list of length 0, 1, or 2).

EXAMPLES:

sage: Integer(144).sqrt()
12
sage: sqrt(Integer(144))
12
sage: Integer(102).sqrt()                                                   # needs sage.symbolic
sqrt(102)

>>> from sage.all import *
>>> Integer(Integer(144)).sqrt()
12
>>> sqrt(Integer(Integer(144)))
12
>>> Integer(Integer(102)).sqrt()                                                   # needs sage.symbolic
sqrt(102)

sage: n = 2
sage: n.sqrt(all=True)                                                      # needs sage.symbolic
[sqrt(2), -sqrt(2)]
sage: n.sqrt(prec=10)                                                       # needs sage.rings.real_mpfr
1.4
sage: n.sqrt(prec=100)                                                      # needs sage.rings.real_mpfr
1.4142135623730950488016887242
sage: n.sqrt(prec=100, all=True)                                            # needs sage.rings.real_mpfr
[1.4142135623730950488016887242, -1.4142135623730950488016887242]
sage: n.sqrt(extend=False)
Traceback (most recent call last):
...
ArithmeticError: square root of 2 is not an integer
sage: (-1).sqrt(extend=False)
Traceback (most recent call last):
...
ArithmeticError: square root of -1 is not an integer
sage: Integer(144).sqrt(all=True)
[12, -12]
sage: Integer(0).sqrt(all=True)
[0]

>>> from sage.all import *
>>> n = Integer(2)
>>> n.sqrt(all=True)                                                      # needs sage.symbolic
[sqrt(2), -sqrt(2)]
>>> n.sqrt(prec=Integer(10))                                                       # needs sage.rings.real_mpfr
1.4
>>> n.sqrt(prec=Integer(100))                                                      # needs sage.rings.real_mpfr
1.4142135623730950488016887242
>>> n.sqrt(prec=Integer(100), all=True)                                            # needs sage.rings.real_mpfr
[1.4142135623730950488016887242, -1.4142135623730950488016887242]
>>> n.sqrt(extend=False)
Traceback (most recent call last):
...
ArithmeticError: square root of 2 is not an integer
>>> (-Integer(1)).sqrt(extend=False)
Traceback (most recent call last):
...
ArithmeticError: square root of -1 is not an integer
>>> Integer(Integer(144)).sqrt(all=True)
[12, -12]
>>> Integer(Integer(0)).sqrt(all=True)
[0]
sqrtrem()[source]#

Return \((s, r)\) where \(s\) is the integer square root of self and \(r\) is the remainder such that \(\text{self} = s^2 + r\). Raises ValueError if self is negative.

EXAMPLES:

sage: 25.sqrtrem()
(5, 0)
sage: 27.sqrtrem()
(5, 2)
sage: 0.sqrtrem()
(0, 0)

>>> from sage.all import *
>>> Integer(25).sqrtrem()
(5, 0)
>>> Integer(27).sqrtrem()
(5, 2)
>>> Integer(0).sqrtrem()
(0, 0)

sage: Integer(-102).sqrtrem()
Traceback (most recent call last):
...
ValueError: square root of negative integer not defined

>>> from sage.all import *
>>> Integer(-Integer(102)).sqrtrem()
Traceback (most recent call last):
...
ValueError: square root of negative integer not defined
squarefree_part(bound=-1)[source]#

Return the square free part of \(x\) (=self), i.e., the unique integer \(z\) that \(x = z y^2\), with \(y^2\) a perfect square and \(z\) square-free.

Use self.radical() for the product of the primes that divide self.

If self is 0, just returns 0.

EXAMPLES:

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

>>> from sage.all import *
>>> squarefree_part(Integer(100))
1
>>> squarefree_part(Integer(12))
3
>>> squarefree_part(Integer(17)*Integer(37)*Integer(37))
17
>>> squarefree_part(-Integer(17)*Integer(32))
-34
>>> squarefree_part(Integer(1))
1
>>> squarefree_part(-Integer(1))
-1
>>> squarefree_part(-Integer(2))
-2
>>> squarefree_part(-Integer(4))
-1

sage: a = 8 * 5^6 * 101^2
sage: a.squarefree_part(bound=2).factor()
2 * 5^6 * 101^2
sage: a.squarefree_part(bound=5).factor()
2 * 101^2
sage: a.squarefree_part(bound=1000)
2
sage: a.squarefree_part(bound=2**14)
2
sage: a = 7^3 * next_prime(2^100)^2 * next_prime(2^200)                     # needs sage.libs.pari
sage: a / a.squarefree_part(bound=1000)                                     # needs sage.libs.pari
49

>>> from sage.all import *
>>> a = Integer(8) * Integer(5)**Integer(6) * Integer(101)**Integer(2)
>>> a.squarefree_part(bound=Integer(2)).factor()
2 * 5^6 * 101^2
>>> a.squarefree_part(bound=Integer(5)).factor()
2 * 101^2
>>> a.squarefree_part(bound=Integer(1000))
2
>>> a.squarefree_part(bound=Integer(2)**Integer(14))
2
>>> a = Integer(7)**Integer(3) * next_prime(Integer(2)**Integer(100))**Integer(2) * next_prime(Integer(2)**Integer(200))                     # needs sage.libs.pari
>>> a / a.squarefree_part(bound=Integer(1000))                                     # needs sage.libs.pari
49
str(base=10)[source]#

Return the string representation of self in the given base.

EXAMPLES:

sage: Integer(2^10).str(2)
'10000000000'
sage: Integer(2^10).str(17)
'394'

>>> from sage.all import *
>>> Integer(Integer(2)**Integer(10)).str(Integer(2))
'10000000000'
>>> Integer(Integer(2)**Integer(10)).str(Integer(17))
'394'

sage: two = Integer(2)
sage: two.str(1)
Traceback (most recent call last):
...
ValueError: base (=1) must be between 2 and 36

>>> from sage.all import *
>>> two = Integer(Integer(2))
>>> two.str(Integer(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

>>> from sage.all import *
>>> two.str(Integer(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 (2s on sage.math, 2014)
sage: len(s)              # long time (depends on above defn of s)
5000001
sage: s[:10]              # long time (depends on above defn of s)
'1000000000'

>>> from sage.all import *
>>> big = Integer(10)**Integer(5000000)
>>> s = big.str()       # long time (2s on sage.math, 2014)
>>> len(s)              # long time (depends on above defn of s)
5000001
>>> s[:Integer(10)]              # long time (depends on above defn of s)
'1000000000'
support()[source]#

Return a sorted list of the primes dividing this integer.

OUTPUT: The sorted list of primes appearing in the factorization of this rational with positive exponent.

EXAMPLES:

sage: factorial(10).support()
[2, 3, 5, 7]
sage: (-999).support()
[3, 37]

>>> from sage.all import *
>>> factorial(Integer(10)).support()
[2, 3, 5, 7]
>>> (-Integer(999)).support()
[3, 37]

Trying to find the support of 0 raises an ArithmeticError:

sage: 0.support()
Traceback (most recent call last):
...
ArithmeticError: support of 0 not defined

>>> from sage.all import *
>>> Integer(0).support()
Traceback (most recent call last):
...
ArithmeticError: support of 0 not defined
test_bit(index)[source]#

Return the bit at index.

If the index is negative, returns 0.

Although internally a sign-magnitude representation is used for integers, this method pretends to use a two’s complement representation. This is illustrated with a negative integer below.

EXAMPLES:

sage: w = 6
sage: w.str(2)
'110'
sage: w.test_bit(2)
1
sage: w.test_bit(-1)
0
sage: x = -20
sage: x.str(2)
'-10100'
sage: x.test_bit(4)
0
sage: x.test_bit(5)
1
sage: x.test_bit(6)
1

>>> from sage.all import *
>>> w = Integer(6)
>>> w.str(Integer(2))
'110'
>>> w.test_bit(Integer(2))
1
>>> w.test_bit(-Integer(1))
0
>>> x = -Integer(20)
>>> x.str(Integer(2))
'-10100'
>>> x.test_bit(Integer(4))
0
>>> x.test_bit(Integer(5))
1
>>> x.test_bit(Integer(6))
1
to_bytes(length=1, byteorder='big', is_signed=False)[source]#

Return an array of bytes representing an integer.

Internally relies on the python int.to_bytes() method.

INPUT:

  • length – positive integer (default: 1); integer is represented in length bytes

  • byteorder – str (default: "big"); determines the byte order of the output; can only be "big" or "little"

  • is_signed – boolean (default: False); determines whether to use two’s compliment to represent the integer

Todo

It should be possible to convert straight from the gmp type in cython. This could be significantly faster, but I am unsure of the fastest and cleanest way to do this.

EXAMPLES:

sage: (1024).to_bytes(2, byteorder='big')
b'\x04\x00'
sage: (1024).to_bytes(10, byteorder='big')
b'\x00\x00\x00\x00\x00\x00\x00\x00\x04\x00'
sage: (-1024).to_bytes(10, byteorder='big', is_signed=True)
b'\xff\xff\xff\xff\xff\xff\xff\xff\xfc\x00'
sage: x = 1000
sage: x.to_bytes((x.bit_length() + 7) // 8, byteorder='little')
b'\xe8\x03'

>>> from sage.all import *
>>> (Integer(1024)).to_bytes(Integer(2), byteorder='big')
b'\x04\x00'
>>> (Integer(1024)).to_bytes(Integer(10), byteorder='big')
b'\x00\x00\x00\x00\x00\x00\x00\x00\x04\x00'
>>> (-Integer(1024)).to_bytes(Integer(10), byteorder='big', is_signed=True)
b'\xff\xff\xff\xff\xff\xff\xff\xff\xfc\x00'
>>> x = Integer(1000)
>>> x.to_bytes((x.bit_length() + Integer(7)) // Integer(8), byteorder='little')
b'\xe8\x03'
trailing_zero_bits()[source]#

Return the number of trailing zero bits in self, i.e. the exponent of the largest power of 2 dividing self.

EXAMPLES:

sage: 11.trailing_zero_bits()
0
sage: (-11).trailing_zero_bits()
0
sage: (11<<5).trailing_zero_bits()
5
sage: (-11<<5).trailing_zero_bits()
5
sage: 0.trailing_zero_bits()
0

>>> from sage.all import *
>>> Integer(11).trailing_zero_bits()
0
>>> (-Integer(11)).trailing_zero_bits()
0
>>> (Integer(11)<<Integer(5)).trailing_zero_bits()
5
>>> (-Integer(11)<<Integer(5)).trailing_zero_bits()
5
>>> Integer(0).trailing_zero_bits()
0
trial_division(bound='LONG_MAX', start=2)[source]#

Return smallest prime divisor of self up to bound, beginning checking at start, or abs(self) if no such divisor is found.

INPUT:

  • bound – a positive integer that fits in a C signed long

  • start – a positive integer that fits in a C signed long

OUTPUT: A positive integer

EXAMPLES:

sage: # needs sage.libs.pari
sage: n = next_prime(10^6)*next_prime(10^7); n.trial_division()
1000003
sage: (-n).trial_division()
1000003
sage: n.trial_division(bound=100)
10000049000057
sage: n.trial_division(bound=-10)
Traceback (most recent call last):
...
ValueError: bound must be positive
sage: n.trial_division(bound=0)
Traceback (most recent call last):
...
ValueError: bound must be positive
sage: ZZ(0).trial_division()
Traceback (most recent call last):
...
ValueError: self must be nonzero

sage: # needs sage.libs.pari
sage: n = next_prime(10^5) * next_prime(10^40); n.trial_division()
100003
sage: n.trial_division(bound=10^4)
1000030000000000000000000000000000000012100363
sage: (-n).trial_division(bound=10^4)
1000030000000000000000000000000000000012100363
sage: (-n).trial_division()
100003
sage: n = 2 * next_prime(10^40); n.trial_division()
2
sage: n = 3 * next_prime(10^40); n.trial_division()
3
sage: n = 5 * next_prime(10^40); n.trial_division()
5
sage: n = 2 * next_prime(10^4); n.trial_division()
2
sage: n = 3 * next_prime(10^4); n.trial_division()
3
sage: n = 5 * next_prime(10^4); n.trial_division()
5

>>> from sage.all import *
>>> # needs sage.libs.pari
>>> n = next_prime(Integer(10)**Integer(6))*next_prime(Integer(10)**Integer(7)); n.trial_division()
1000003
>>> (-n).trial_division()
1000003
>>> n.trial_division(bound=Integer(100))
10000049000057
>>> n.trial_division(bound=-Integer(10))
Traceback (most recent call last):
...
ValueError: bound must be positive
>>> n.trial_division(bound=Integer(0))
Traceback (most recent call last):
...
ValueError: bound must be positive
>>> ZZ(Integer(0)).trial_division()
Traceback (most recent call last):
...
ValueError: self must be nonzero

>>> # needs sage.libs.pari
>>> n = next_prime(Integer(10)**Integer(5)) * next_prime(Integer(10)**Integer(40)); n.trial_division()
100003
>>> n.trial_division(bound=Integer(10)**Integer(4))
1000030000000000000000000000000000000012100363
>>> (-n).trial_division(bound=Integer(10)**Integer(4))
1000030000000000000000000000000000000012100363
>>> (-n).trial_division()
100003
>>> n = Integer(2) * next_prime(Integer(10)**Integer(40)); n.trial_division()
2
>>> n = Integer(3) * next_prime(Integer(10)**Integer(40)); n.trial_division()
3
>>> n = Integer(5) * next_prime(Integer(10)**Integer(40)); n.trial_division()
5
>>> n = Integer(2) * next_prime(Integer(10)**Integer(4)); n.trial_division()
2
>>> n = Integer(3) * next_prime(Integer(10)**Integer(4)); n.trial_division()
3
>>> n = Integer(5) * next_prime(Integer(10)**Integer(4)); n.trial_division()
5

You can specify a starting point:

sage: n = 3*5*101*103
sage: n.trial_division(start=50)
101

>>> from sage.all import *
>>> n = Integer(3)*Integer(5)*Integer(101)*Integer(103)
>>> n.trial_division(start=Integer(50))
101
trunc()[source]#

Round this number to the nearest integer, which is self since self is an integer.

EXAMPLES:

sage: n = 6
sage: n.trunc()
6

>>> from sage.all import *
>>> n = Integer(6)
>>> n.trunc()
6
val_unit(p)[source]#

Return a pair: the p-adic valuation of self, and the p-adic unit of self.

INPUT:

  • p – an integer at least 2.

OUTPUT:

  • v_p(self) – the p-adic valuation of self

  • u_p(self) – self / \(p^{v_p(\mathrm{self})}\)

EXAMPLES:

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)

>>> from sage.all import *
>>> n = Integer(60)
>>> n.val_unit(Integer(2))
(2, 15)
>>> n.val_unit(Integer(3))
(1, 20)
>>> n.val_unit(Integer(7))
(0, 60)
>>> (Integer(2)**Integer(11)).val_unit(Integer(4))
(5, 2)
>>> Integer(0).val_unit(Integer(2))
(+Infinity, 1)
valuation(p)[source]#

Return the p-adic valuation of self.

INPUT:

  • p – an integer at least 2.

EXAMPLES:

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.

>>> from sage.all import *
>>> n = Integer(60)
>>> n.valuation(Integer(2))
2
>>> n.valuation(Integer(3))
1
>>> n.valuation(Integer(7))
0
>>> n.valuation(Integer(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

>>> from sage.all import *
>>> (Integer(2)**Integer(11)).valuation(Integer(4))
5
xgcd(n)[source]#

Return the extended gcd of this element and n.

INPUT:

  • n – an integer

OUTPUT:

A triple (g, s, t) such that g is the non-negative gcd of self and n, and s and t are cofactors satisfying the Bezout identity

\[g = s \cdot \mathrm{self} + t \cdot n.\]

Note

There is no guarantee that the cofactors will be minimal. If you need the cofactors to be minimal use _xgcd(). Also, using _xgcd() directly might be faster in some cases, see Issue #13628.

EXAMPLES:

sage: 6.xgcd(4)
(2, 1, -1)

>>> from sage.all import *
>>> Integer(6).xgcd(Integer(4))
(2, 1, -1)
class sage.rings.integer.IntegerWrapper[source]#

Bases: Integer

Rationale for the IntegerWrapper class:

With Integer objects, the allocation/deallocation function slots are hijacked with custom functions that stick already allocated Integer objects (with initialized parent and mpz_t fields) into a pool on “deallocation” and then pull them out whenever a new one is needed. Because Integers objects are so common, this is actually a significant savings. However, this does cause issues with subclassing a Python class directly from Integer (but that’s ok for a Cython class).

As a workaround, one can instead derive a class from the intermediate class IntegerWrapper, which sets statically its alloc/dealloc methods to the original Integer alloc/dealloc methods, before they are swapped manually for the custom ones.

The constructor of IntegerWrapper further allows for specifying an alternative parent to IntegerRing.

sage.rings.integer.free_integer_pool()[source]#
class sage.rings.integer.int_to_Z[source]#

Bases: Morphism

EXAMPLES:

sage: f = ZZ.coerce_map_from(int)
sage: f
Native morphism:
  From: Set of Python objects of class 'int'
  To:   Integer Ring
sage: f(1rL)
1

>>> from sage.all import *
>>> f = ZZ.coerce_map_from(int)
>>> f
Native morphism:
  From: Set of Python objects of class 'int'
  To:   Integer Ring
>>> f(1)
1
sage.rings.integer.is_Integer(x)[source]#

Return True if x is of the Sage Integer type.

EXAMPLES:

sage: from sage.rings.integer import is_Integer
sage: is_Integer(2)
doctest:warning...
DeprecationWarning: The function is_Integer is deprecated;
use 'isinstance(..., Integer)' instead.
See https://github.com/sagemath/sage/issues/38128 for details.
True
sage: is_Integer(2/1)
False
sage: is_Integer(int(2))
False
sage: is_Integer('5')
False

>>> from sage.all import *
>>> from sage.rings.integer import is_Integer
>>> is_Integer(Integer(2))
doctest:warning...
DeprecationWarning: The function is_Integer is deprecated;
use 'isinstance(..., Integer)' instead.
See https://github.com/sagemath/sage/issues/38128 for details.
True
>>> is_Integer(Integer(2)/Integer(1))
False
>>> is_Integer(int(Integer(2)))
False
>>> is_Integer('5')
False
sage.rings.integer.make_integer(s)[source]#

Create a Sage integer from the base-32 Python string s. This is used in unpickling integers.

EXAMPLES:

sage: from sage.rings.integer import make_integer
sage: make_integer('-29')
-73
sage: make_integer(29)
Traceback (most recent call last):
...
TypeError: expected str...Integer found

>>> from sage.all import *
>>> from sage.rings.integer import make_integer
>>> make_integer('-29')
-73
>>> make_integer(Integer(29))
Traceback (most recent call last):
...
TypeError: expected str...Integer found