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
a = Integer(3); b = Integer(4) a + b == 7
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
a + 4.0 # needs sage.rings.real_mpfr
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
a + Rational(2)/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
# needs sage.rings.real_mpfr b = ComplexField().0 + 1.5 loads((a + b).dumps()) == a + b z = 32 -z z = 0; -z z = -0; -z z = -1; -z
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
a = Integer(3); b = Integer(4) a * b == 12 loads((a * 4.0).dumps()) == a*b a * Rational(2)/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]
[2,3] * 4
>>> from sage.all import *
>>> [Integer(2),Integer(3)] * Integer(4)
[2, 3, 2, 3, 2, 3, 2, 3]
[2,3] * 4
sage: 'sage' * Integer(3)
'sagesagesage'
>>> from sage.all import *
>>> 'sage' * Integer(Integer(3))
'sagesagesage'
'sage' * Integer(3)
>>> from sage.all import *
>>> 'sage' * Integer(Integer(3))
'sagesagesage'
'sage' * Integer(3)
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
n = 9390823 RR = RealField(200) # needs sage.rings.real_mpfr RR(n) # needs sage.rings.real_mpfr
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 ofis_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'>
from sage.rings.integer import GCD_list w = GCD_list([3,9,30]); w type(w)
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
sage.rings.integer.GCD_list([2,2,3])
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'>
w = GCD_list([int(3), int(9), '30']); w type(w)
Check that the GCD of the empty list is zero (Issue #17257):
sage: GCD_list([]) 0
>>> from sage.all import * >>> GCD_list([]) 0
GCD_list([])
- class sage.rings.integer.Integer[source]¶
Bases:
EuclideanDomainElementThe
Integerclass represents arbitrary precision integers. It derives from theElementclass, so integers can be used as ring elements anywhere in Sage.The constructor of
Integerinterprets strings that begin with0oas octal numbers, strings that begin with0xas hexadecimal numbers and strings that begin with0bas binary numbers.The class
Integeris implemented in Cython, as a wrapper of the GMPmpz_tinteger type.EXAMPLES:
sage: Integer(123) 123 sage: Integer("123") 123
>>> from sage.all import * >>> Integer(Integer(123)) 123 >>> Integer("123") 123
Integer(123) Integer("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
Integer('0x12') Integer('-0o12') Integer('+0b101010')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
Integer(pari('-10380104371593008048799446356441519384')) # needs sage.libs.pari Integer(pari('Pol([-3])')) # needs sage.libs.pariConversion 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
from gmpy2 import mpz Integer(mpz(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)
2^-6 2^6 2^0 2^-0 (-1)^(1/3) # needs sage.symbolic
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
0^0
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'>
r = int(2) ^ 10; r; type(r) r = int(3) ^ -3; r; type(r) r = float(2.5) ^ 10; r; type(r)
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))
2^x # symbolic x # needs sage.symbolic 2^1.5 # real number # needs sage.rings.real_mpfr 2^float(1.5) # python float abs tol 3e-16 2^I # complex number # needs sage.symbolic r = 2 ^ int(-3); r; type(r) f = 2^(sin(x)-cos(x)); f # needs sage.symbolic f(x=3) # needs sage.symbolic
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)
# needs sage.symbolic x, y, z = var('x,y,z') 2^(x + y + z) 2^(1/2) 2^(-1/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
ZZ(0).additive_order() ZZ(1).additive_order()
- 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)
x = -12 x.as_integer_ratio()
- balanced_digits(base=10, positive_shift=True)[source]¶
Return the list of balanced digits for
selfin the given base.The balanced base
busesbdigits centered around zero. Thus ifbis odd, there is only one possibility, namely digits between-b//2andb//2(both included). For instance in base 9, one uses digits from -4 to 4. Ifbis even, one has to choose between digits from-b//2tob//2 - 1or-b//2 + 1tob//2(base 10 for instance: either \(-5\) to \(4\) or \(-4\) to \(5\)), and this is defined by the value ofpositive_shift.INPUT:
base– integer (default: 10); whenbaseis 2, only the nonnegative or the nonpositive integers can be represented bybalanced_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 + 1tob//2if set toTrue, and from-b//2tob//2 - 1otherwise. 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
8.balanced_digits(3) (-15).balanced_digits(5) 17.balanced_digits(6) 17.balanced_digits(6, positive_shift=False) (-46).balanced_digits() (-46).balanced_digits(positive_shift=False) (-23).balanced_digits(12) (-23).balanced_digits(12, positive_shift=False) 0.balanced_digits(7) 14.balanced_digits(5.8) 14.balanced_digits(2)
See also
- binary()[source]¶
Return the binary digits of
selfas 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
print(Integer(15).binary()) print(Integer(16).binary()) print(Integer(16938402384092843092843098243).binary())
- binomial(m, algorithm='gmp')[source]¶
Return the binomial coefficient “
selfchoosem”.INPUT:
m– integeralgorithm–'gmp'(default),'mpir'(an alias forgmp), or'pari';'gmp'is faster for smallm, and'pari'tends to be faster for largem
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
10.binomial(2) 10.binomial(2, algorithm='pari') # needs sage.libs.pari 10.binomial(-2) (-2).binomial(3) (-3).binomial(0)
The argument
mor (self - m) must fit into anunsigned 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
(2**256).binomial(2**256) (2**256).binomial(2**256 - 1) (2**256).binomial(2**128)
- 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
500.bit_length() 5.bit_length() 0.bit_length() == len(0.bits()) == 0.ndigits(base=2) 12345.bit_length() == len(12345.binary()) 1023.bit_length() 1024.bit_length()
- bits()[source]¶
Return the bits in
selfas a list, least significant first. The result satisfies the identityx == 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()withbase=2.See also
bit_length(), a faster way to computelen(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]
500.bits() 11.bits() (-99).bits()
- ceil()[source]¶
Return the ceiling of
self, which isselfsinceselfis an integer.EXAMPLES:
sage: n = 6 sage: n.ceil() 6
>>> from sage.all import * >>> n = Integer(6) >>> n.ceil() 6
n = 6 n.ceil()
- class_number(proof=True)[source]¶
Return the class number of the quadratic order with this discriminant.
INPUT:
self– integer congruent to \(0\) or \(1\) mod \(4\) which is not a squareproof– boolean (default:True); ifFalse, 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)]
(-163).class_number() # needs sage.libs.pari (-104).class_number() # needs sage.libs.pari [((4*n + 1), (4*n + 1).class_number()) for n in [21..29]] # needs sage.libs.pari
- 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
n = 205 n.conjugate()
- coprime_integers(m)[source]¶
Return the nonnegative 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]
n = 8 n.coprime_integers(8) n.coprime_integers(11) n = 5; n.coprime_integers(10) n.coprime_integers(5) n = 99; n.coprime_integers(99)
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
n = 17 m = n.crt(5, 23, 11); m m%23 m%11
- 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
x = 5 x.denominator() x = 0 x.denominator()
- digits(base=10, digits=None, padto=0)[source]¶
Return a list of digits for
selfin the given base in little endian order.The returned value is unspecified if
selfis a negative number and the digits are given.INPUT:
base– integer (default: 10)digits– (optional) indexable object as source for the digitspadto– 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 usebits().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]
17.digits() 5.digits(base=2, digits=["zero","one"]) 5.digits(3) 0.digits(base=10) # 0 has 0 digits 0.digits(base=2) # 0 has 0 digits 10.digits(16,'0123456789abcdef') 0.digits(16,'0123456789abcdef') 0.digits(16,'0123456789abcdef',padto=1) 123.digits(base=10,padto=5) 123.digits(base=2,padto=3) # padto is the minimal length 123.digits(base=2,padto=10,digits=(1,-1)) a=9939082340; a.digits(10) a.digits(512) (-12).digits(10) (-12).digits(2)
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]
n=2^6000 n.digits(2^3000)
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
base=3; n=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 base=3; n=-30; l=n.digits(base); sum(base^i*l[i] for i in range(len(l)))==n
>>> 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
base=3; n=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 base=3; n=-30; l=n.digits(base); sum(base^i*l[i] for i in range(len(l)))==n
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
x = 123; ZZ(x.digits(), 10) x == ZZ(x.digits(6), 6) x == ZZ(x.digits(25), 25)
Using
sum()andenumerate()to do the same thing is slightly faster in many cases (andbalanced_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
base = 4 sum(digit * base^i for i, digit in enumerate(x.digits(base))) == ZZ(x.digits(base), base)
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]
digits = list(range(15)) l = [ZZ(i).digits(15,digits) for i in range(100)] l[16]
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
n=3^100000 n.digits(base=10)[-1] # slightly slower than str # needs sage.rings.real_interval_field n=10^10000 n.digits(base=10)[-1] # slightly faster than str # needs sage.rings.real_interval_field
AUTHORS:
Joel B. Mohler (2008-03-02): significantly rewrote this entire function
- divide_knowing_divisible_by(right)[source]¶
Return the integer
self/rightwhenselfis divisible byright.If
selfis not divisible by right, the return value is undefined, and may not even be close toself/rightfor 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
a = 8; b = 4 a.divide_knowing_divisible_by(b) (100000).divide_knowing_divisible_by(25) (100000).divide_knowing_divisible_by(26) # close (random)
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
a = 2^70; a a // 11 # floor divide a.divide_knowing_divisible_by(11) # way off and possibly random
- divides(n)[source]¶
Return
Trueifselfdividesn.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
Z = IntegerRing() Z(5).divides(Z(10)) Z(0).divides(Z(5)) Z(10).divides(Z(5))
- 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
(-3).divisors() 6.divisors() 28.divisors() (2^5).divisors() 100.divisors() 1.divisors() 0.divisors() (2^3 * 3^2 * 17).divisors() a = odd_part(factorial(31)) v = a.divisors() # needs sage.libs.pari len(v) # needs sage.libs.pari prod(e + 1 for p, e in factor(a)) # needs sage.libs.pari all(t.divides(a) for t in v) # needs sage.libs.pari
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
n = 2^551 - 1 L = n.divisors() # needs sage.libs.pari len(L) # needs sage.libs.pari L[-1] == n # needs sage.libs.pari
>>> 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
n = 2^551 - 1 L = n.divisors() # needs sage.libs.pari len(L) # needs sage.libs.pari L[-1] == n # needs sage.libs.pari
Note
If one first computes all the divisors and then sorts it, the sorting step can easily dominate the runtime. Note, however, that (nonnegative) 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 a 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
ZZ(1).euclidean_degree()
- 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
Integer(125).exact_log(5) Integer(124).exact_log(5) Integer(126).exact_log(5) Integer(3).exact_log(5) Integer(1).exact_log(5) Integer(178^1700).exact_log(178) Integer(178^1700-1).exact_log(178) Integer(178^1700+1).exact_log(178) # we need to exercise the large base code path too Integer(1780^1700-1).exact_log(1780) # needs sage.rings.real_interval_field # 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 = 2983579823750185701375109835; m = 32 n.exact_log(m) # The next is a favorite of mine. The log2 approximate is exact and immediately provable. n = 90153710570912709517902579010793251709257901270941709247901209742124 m = 213509721309572 n.exact_log(m)
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
# needs sage.rings.real_mpfr x = 3^100000 RR(log(RR(x), 3)) RR(log(RR(x + 100000), 3))
>>> 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
# needs sage.rings.real_mpfr x = 3^100000 RR(log(RR(x), 3)) RR(log(RR(x + 100000), 3))
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
# needs sage.rings.real_mpfr x.exact_log(3) (x + 1).exact_log(3) (x - 1).exact_log(3)
>>> 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
# needs sage.rings.real_mpfr x.exact_log(3) (x + 1).exact_log(3) (x - 1).exact_log(3)
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
# needs sage.rings.real_mpfr x.exact_log(2.5)
>>> 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
# needs sage.rings.real_mpfr x.exact_log(2.5)
- exp(prec=None)[source]¶
Return the exponential function of
selfas 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); ifNone, returns symbolic, else to given bits of precision as inRealField
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
Integer(8).exp() # needs sage.symbolic Integer(8).exp(prec=100) # needs sage.symbolic exp(Integer(8)) # needs sage.symbolic
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
y = Integer(145^145) y.exp() # needs sage.symbolic y.exp(prec=53) # default RealField precision # needs sage.symbolic
- 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; one of'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– boolean (default:True); whether or not to prove primality of each factor (only applicable for'pari'and'ecm')limit– integer orNone(default:None); if limit is given it must fit in asigned 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
n = 2^100 - 1; n.factor() # needs sage.libs.pari
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)
f = 60.factor() list(f) f[2]
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
f = (3^6).factor() dict(f) dict(f)[3]
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
n = 920384092842390423848290348203948092384082349082 n.factor(proof=False) # needs sage.libs.pari n.factor(proof=True) # needs sage.libs.pari
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
n.factor(limit=1000)
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
n = 82862385732327628428164127822 n.factor(algorithm='flint') # needs sage.libs.flint
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
# needs sage.libs.pari p = next_prime(10^20) q = next_prime(10^21) n = p * q n.factor(algorithm='qsieve') # needs sage.libs.flint
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
# needs sage.libs.pari p = next_prime(10^15) q = next_prime(10^21) n = p * q n.factor(algorithm='ecm')
- factorial()[source]¶
Return the factorial \(n! = 1 \cdot 2 \cdot 3 \cdots n\).
If the input does not fit in an
unsigned long int, anOverflowErroris 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
for n in srange(7): print("{} {}".format(n, n.factorial()))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
(2**64).factorial()
And negative ones a
ValueError:sage: (-1).factorial() Traceback (most recent call last): ... ValueError: factorial only defined for nonnegative integers
>>> from sage.all import * >>> (-Integer(1)).factorial() Traceback (most recent call last): ... ValueError: factorial only defined for nonnegative integers
(-1).factorial()
- floor()[source]¶
Return the floor of
self, which is justselfsinceselfis an integer.EXAMPLES:
sage: n = 6 sage: n.floor() 6
>>> from sage.all import * >>> n = Integer(6) >>> n.floor() 6
n = 6 n.floor()
- gamma()[source]¶
The gamma function on integers is the factorial function (shifted by one) on positive integers, and \(\pm \infty\) on nonpositive 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
# needs sage.symbolic gamma(5) gamma(0) gamma(-1) gamma(-2^150)
- global_height(prec=None)[source]¶
Return the absolute logarithmic height of this rational integer.
INPUT:
prec– integer; 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
# needs sage.rings.real_mpfr ZZ(5).global_height() ZZ(-2).global_height(prec=100) exp(_)
- hex()[source]¶
Return the hexadecimal digits of
selfin 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
print(Integer(15).hex()) print(Integer(16).hex()) print(Integer(16938402384092843092843098243).hex())
- 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
Integer(9).imag()
- inverse_mod(n)[source]¶
Return the inverse of
selfmodulo \(n\), if this inverse exists.Otherwise, raise a
ZeroDivisionErrorexception.INPUT:
self– integern– integer or ideal of integer ring
OUTPUT:
x– integer such that x *self= 1 (mod m), or raisesZeroDivisionError
IMPLEMENTATION:
Call the
mpz_invertGMP 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
a = Integer(189) a.inverse_mod(10000) a.inverse_mod(-10000) a.inverse_mod(1890) a = Integer(19)**100000 # long time c = a.inverse_mod(a*a) # long time
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
ZZ(2).inverse_mod(ZZ.ideal(3))
We check that Issue #9955 is fixed:
sage: Rational(3) % Rational(-1) 0
>>> from sage.all import * >>> Rational(Integer(3)) % Rational(-Integer(1)) 0
Rational(3) % Rational(-1)
- inverse_of_unit()[source]¶
Return inverse of
selfifselfis a unit in the integers, i.e.,selfis \(-1\) or \(1\). Otherwise, raise aZeroDivisionError.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
(1).inverse_of_unit() (-1).inverse_of_unit() 5.inverse_of_unit() 0.inverse_of_unit()
- is_discriminant()[source]¶
Return
Trueif 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
(-1).is_discriminant() (-4).is_discriminant() 100.is_discriminant() 101.is_discriminant()
- is_fundamental_discriminant()[source]¶
Return
Trueif 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
(-4).is_fundamental_discriminant() # needs sage.libs.pari (-12).is_fundamental_discriminant() 101.is_fundamental_discriminant() # needs sage.libs.pari
- is_integer()[source]¶
Return
Trueas they are integers.EXAMPLES:
sage: sqrt(4).is_integer() True
>>> from sage.all import * >>> sqrt(Integer(4)).is_integer() True
sqrt(4).is_integer()
- is_integral()[source]¶
Return
Truesince 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
Integer(3).is_integral()
- is_irreducible()[source]¶
Return
Trueifselfis irreducible, i.e. +/- primeEXAMPLES:
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
z = 2^31 - 1 z.is_irreducible() # needs sage.libs.pari z = 2^31 z.is_irreducible() z = 7 z.is_irreducible() z = -7 z.is_irreducible()
- 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)
n = 7 n.is_norm(QQ) n.is_norm(QQ, element=True) # needs sage.rings.number_field x = polygen(ZZ, 'x') K = NumberField(x^2 - 2, 'beta') n = 4 n.is_norm(K) 5.is_norm(K) n.is_norm(K, element=True) n.is_norm(K, element=True)[1].norm() n = 5 n.is_norm(K, element=True)
- is_one()[source]¶
Return
Trueif the integer is \(1\), otherwiseFalse.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
Integer(1).is_one() Integer(0).is_one()
- is_perfect_power()[source]¶
Return
Trueifselfis a perfect power, ie if there exist integers \(a\) and \(b\), \(b > 1\) withself\(= a^b\).See also
perfect_power(): Finds the minimal base for which this integer is a perfect power.is_power_of(): If you know the base already, this method is the fastest option.is_prime_power(): Checks whether the base is prime.
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
Integer(-27).is_perfect_power() Integer(12).is_perfect_power() z = 8 z.is_perfect_power() 144.is_perfect_power() 10.is_perfect_power() (-8).is_perfect_power() (-4).is_perfect_power()
- is_power_of(n)[source]¶
Return
Trueif 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
Integer(64).is_power_of(4) Integer(64).is_power_of(16)
Note
For large integers
self,is_power_of()is faster thanis_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
b = lcm(range(1,10000)) b.exact_log(2) t = cputime() for a in range(2, 1000): k = b.is_perfect_power() cputime(t) # random t = cputime() for a in range(2, 1000): k = b.is_power_of(2) cputime(t) # random t = cputime() for a in range(2, 1000): k = b.is_power_of(3) cputime(t) # random
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
b = lcm(range(1, 1000)) b.exact_log(2) t = cputime() for a in range(2, 10000): # note: changed range from the example above k = b.is_perfect_power() cputime(t) # random t = cputime(); TWO = int(2) for a in range(2, 10000): k = b.is_power_of(TWO) cputime(t) # random t = cputime() for a in range(2, 10000): k = b.is_power_of(3) cputime(t) # random t = cputime() for a in range(2, 10000): k = b.is_power_of(a) cputime(t) # random>>> 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
b = lcm(range(1, 1000)) b.exact_log(2) t = cputime() for a in range(2, 10000): # note: changed range from the example above k = b.is_perfect_power() cputime(t) # random t = cputime(); TWO = int(2) for a in range(2, 10000): k = b.is_power_of(TWO) cputime(t) # random t = cputime() for a in range(2, 10000): k = b.is_power_of(3) cputime(t) # random t = cputime() for a in range(2, 10000): k = b.is_power_of(a) cputime(t) # random
- is_prime(proof=None)[source]¶
Test whether
selfis prime.INPUT:
proof– boolean orNone(default). IfFalse, use a strong pseudo-primality test (seeis_pseudoprime()). IfTrue, use a provable primality test. If unset, use thedefault arithmetic proof flag.
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
z = 2^31 - 1 z.is_prime() # needs sage.libs.pari z = 2^31 z.is_prime() z = 7 z.is_prime() z = -7 z.is_prime() z.is_irreducible()
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
z = 10^80 + 129 z.is_prime(proof=False) # needs sage.libs.pari z.is_prime(proof=True) # needs sage.libs.pari
>>> 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
z = 10^80 + 129 z.is_prime(proof=False) # needs sage.libs.pari z.is_prime(proof=True) # needs sage.libs.pari
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
proof.arithmetic() n = 10^100 + 267 timeit("n.is_prime()") # not tested # needs sage.libs.pari proof.arithmetic(False) proof.arithmetic() timeit("n.is_prime()") # not tested # needs sage.libs.pariALGORITHM:
Calls the PARI function pari:isprime.
- is_prime_power(proof=None, get_data=False)[source]¶
Return
Trueif this integer is a prime power, andFalseotherwise.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 orNone(default). IfFalse, use a strong pseudo-primality test (seeis_pseudoprime()). IfTrue, use a provable primality test. If unset, use the default arithmetic proof flag.get_data– (default:False), ifTruereturn a pair(p,k)such that this integer equalsp^kwithpa prime andka positive integer or the pair(self,0)otherwise.
See also
perfect_power(): Finds the minimal base for which integer is a perfect power.is_perfect_power(): Doesn’t test whether the base is prime.is_power_of(): If you know the base already this method is the fastest option.is_pseudoprime_power(): If the entry is very large.
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
# needs sage.libs.pari 17.is_prime_power() 10.is_prime_power() 64.is_prime_power() (3^10000).is_prime_power() (10000).is_prime_power() (-3).is_prime_power() 0.is_prime_power() 1.is_prime_power() p = next_prime(10^20); p p.is_prime_power() (p^97).is_prime_power() (p + 1).is_prime_power()
With the
get_datakeyword set toTrue: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)
# needs sage.libs.pari (3^100).is_prime_power(get_data=True) 12.is_prime_power(get_data=True) (p^97).is_prime_power(get_data=True) q = p.next_prime(); q (p*q).is_prime_power(get_data=True)
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)
proof.arithmetic(False) ((10^500 + 961)^4).is_prime_power() # needs sage.libs.pari 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
n = 150607571^14 n.is_prime_power() # needs sage.libs.pari
- is_pseudoprime()[source]¶
Test whether
selfis 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
z = 2^31 - 1 z.is_pseudoprime() # needs sage.libs.pari z = 2^31 z.is_pseudoprime() # needs sage.libs.pari
- 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) ifTruereturn 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
# needs sage.libs.pari x = 10^200 + 357 x.is_pseudoprime() (x^12).is_pseudoprime_power() (x^12).is_pseudoprime_power(get_data=True) (997^100).is_pseudoprime_power() (998^100).is_pseudoprime_power() ((10^1000 + 453)^2).is_pseudoprime_power()
- is_rational()[source]¶
Return
Trueas an integer is a rational number.EXAMPLES:
sage: 5.is_rational() True
>>> from sage.all import * >>> Integer(5).is_rational() True
5.is_rational()
- is_square()[source]¶
Return
Trueifselfis 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
Integer(4).is_square() Integer(41).is_square()
- is_squarefree()[source]¶
Return
Trueif this integer is not divisible by the square of any prime andFalseotherwise.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
100.is_squarefree() # needs sage.libs.pari 102.is_squarefree() # needs sage.libs.pari 0.is_squarefree() # needs sage.libs.pari
- is_unit()[source]¶
Return
Trueif 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
for n in srange(-2,3): print("{} {}".format(n, n.is_unit()))
- isqrt()[source]¶
Return the integer floor of the square root of
self, or raises anValueErrorifselfis negative.EXAMPLES:
sage: a = Integer(5) sage: a.isqrt() 2
>>> from sage.all import * >>> a = Integer(Integer(5)) >>> a.isqrt() 2
a = Integer(5) a.isqrt()
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
Integer(-102).isqrt()
>>> from sage.all import * >>> Integer(-Integer(102)).isqrt() Traceback (most recent call last): ... ValueError: square root of negative integer not defined
Integer(-102).isqrt()
- 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
z = -1 z.jacobi(17) z.jacobi(19) z.jacobi(17*19) (2).jacobi(17) (3).jacobi(19) (6).jacobi(17*19) (6).jacobi(33) a = 3; b = 7 a.jacobi(b) == -b.jacobi(a)
- kronecker(b)[source]¶
Calculate the Kronecker symbol \(\left(\frac{\text{self}}{b}\right)\) with the Kronecker extension \((\text{self}/2)=(2/\text{self})\) when
selfis odd, or \((\text{self}/2)=0\) whenselfis 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
z = 5 z.kronecker(41) z.kronecker(43) z.kronecker(8) z.kronecker(15) a = 2; b = 5 a.kronecker(b) == b.kronecker(a)
- 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]
m = 5 m.list()
- log(m=None, prec=None)[source]¶
Return symbolic log by default, unless the logarithm is exact (for an integer argument). When
precis given, theRealFieldapproximation 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 eprec– integer (default:None); ifNone, returns symbolic, else to given bits of precision as inRealField
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)
Integer(124).log(5) # needs sage.symbolic Integer(124).log(5, 100) # needs sage.rings.real_mpfr Integer(125).log(5) Integer(125).log(5, prec=53) # needs sage.rings.real_mpfr log(Integer(125)) # needs sage.symbolic
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
x = 3^100000 log(x, 3) # needs sage.rings.real_interval_field
Also
log(x), giving a symbolic output, works in a reasonable amount of time for thisx: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)
x = 3^100000 log(x) # needs sage.symbolic
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
x.log(3, 53) # default precision for RealField # needs sage.rings.real_mpfr (x + 1).log(3, 53) # needs sage.rings.real_mpfr (x + 1).log(3, 1000) # needs sage.rings.real_mpfr
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
x.log(2.5, prec=53) # needs sage.rings.real_mpfr
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
log(-1) # needs sage.symbolic
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
log(0) # needs sage.symbolic
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
ZZ(8).log(1/2)
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
ZZ(8).log(int(2))
- multifactorial(k)[source]¶
Compute the \(k\)-th factorial \(n!^{(k)}\) of
self.The multifactorial number \(n!^{(k)}\) is defined for nonnegative 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 nonnegative 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
5.multifactorial(1) 5.multifactorial(2) 5.multifactorial(3) 23.multifactorial(2) prod([1..23, step=2]) (-29).multifactorial(7) (-3).multifactorial(5) (-9).multifactorial(3)
When entries are too large an
OverflowErroris 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
(2**64).multifactorial(2)
- 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
ZZ(1).multiplicative_order() ZZ(-1).multiplicative_order() ZZ(0).multiplicative_order() ZZ(2).multiplicative_order()
- nbits()[source]¶
Alias for
bit_length().
- ndigits(base=10)[source]¶
Return the number of digits of
selfexpressed 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
n = 52 n.ndigits() n = -10003 n.ndigits() n = 15 n.ndigits(2) n = 1000**1000000+1 n.ndigits() # needs sage.rings.real_interval_field n = 1000**1000000-1 n.ndigits() # needs sage.rings.real_interval_field n = 10**10000000-10**9999990 n.ndigits() # needs sage.rings.real_interval_field
- next_prime(proof=None)[source]¶
Return the next prime after
self.This method calls the PARI function pari:nextprime.
INPUT:
proof– boolean orNone(default:None, seeproof.arithmeticorsage.structure.proof); note that the global Sage default isproof=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
100.next_prime() # needs sage.libs.pari (10^50).next_prime() # needs sage.libs.pari
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
b = (2^1024).next_prime(proof=False) # needs sage.libs.pari b - 2^1024 # needs sage.libs.pari
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
Integer(0).next_prime() # needs sage.libs.pari Integer(1001).next_prime() # needs sage.libs.pari
>>> from sage.all import * >>> Integer(Integer(0)).next_prime() # needs sage.libs.pari 2 >>> Integer(Integer(1001)).next_prime() # needs sage.libs.pari 1009
Integer(0).next_prime() # needs sage.libs.pari Integer(1001).next_prime() # needs sage.libs.pari
- next_prime_power(proof=None)[source]¶
Return the next prime power after
self.INPUT:
proof– ifTrueensure that the returned value is the next prime power and if set toFalseuses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (seeproof.arithmeticorsage.structure.proof).
ALGORITHM:
The algorithm is naive. It computes the next power of 2 and goes through the odd numbers calling
is_prime_power().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
(-1).next_prime_power() 2.next_prime_power() 103.next_prime_power() # needs sage.libs.pari 107.next_prime_power() 2044.next_prime_power() # needs sage.libs.pari
- 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
# needs sage.libs.pari (-37).next_probable_prime() (100).next_probable_prime() (2^512).next_probable_prime() 0.next_probable_prime() 126.next_probable_prime() 144168.next_probable_prime()
- nth_root(n, truncate_mode=0)[source]¶
Return the (possibly truncated)
n-th root ofself.INPUT:
n– integer \(\geq 1\) (must fit in the Cinttype)truncate_mode– boolean, whether to allow truncation ifselfis not ann-th power
OUTPUT:
If
truncate_modeis 0 (default), then returns the exact n’th root ifselfis an n’th power, or raises aValueErrorif it is not.If
truncate_modeis 1, then if eithernis odd orselfis positive, returns a pair(root, exact_flag)whererootis the truncatedn-th root (rounded towards zero) andexact_flagis a boolean indicating whether the root extraction was exact; otherwise raises aValueError.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)
Integer(125).nth_root(3) Integer(124).nth_root(3) Integer(124).nth_root(3, truncate_mode=1) Integer(125).nth_root(3, truncate_mode=1) Integer(126).nth_root(3, truncate_mode=1)
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)
Integer(-125).nth_root(3) Integer(-125).nth_root(3,truncate_mode=1) Integer(-124).nth_root(3,truncate_mode=1) Integer(-126).nth_root(3,truncate_mode=1)
>>> 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)
Integer(-125).nth_root(3) Integer(-125).nth_root(3,truncate_mode=1) Integer(-124).nth_root(3,truncate_mode=1) Integer(-126).nth_root(3,truncate_mode=1)
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)
Integer(125).nth_root(2, True) Integer(125).nth_root(3, 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)
Integer(125).nth_root(2, True) Integer(125).nth_root(3, 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
Integer(125).nth_root(-5)
>>> from sage.all import * >>> Integer(Integer(125)).nth_root(-Integer(5)) Traceback (most recent call last): ... ValueError: n (=-5) must be positive
Integer(125).nth_root(-5)
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
Integer(-25).nth_root(2)
>>> from sage.all import * >>> Integer(-Integer(25)).nth_root(Integer(2)) Traceback (most recent call last): ... ValueError: cannot take even root of negative number
Integer(-25).nth_root(2)
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)
a=9 a.nth_root(3) a.nth_root(22) ZZ(2^20).nth_root(21) ZZ(2^20).nth_root(21, truncate_mode=1)
>>> 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)
a=9 a.nth_root(3) a.nth_root(22) ZZ(2^20).nth_root(21) ZZ(2^20).nth_root(21, truncate_mode=1)
- 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
x = 5 x.numerator()
sage: x = 0 sage: x.numerator() 0
>>> from sage.all import * >>> x = Integer(0) >>> x.numerator() 0
x = 0 x.numerator()
>>> from sage.all import * >>> x = Integer(0) >>> x.numerator() 0
x = 0 x.numerator()
- oct()[source]¶
Return the digits of
selfin 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
print(Integer(800).oct()) print(Integer(8).oct()) print(Integer(-50).oct()) print(Integer(-899).oct()) print(Integer(16938402384092843092843098243).oct())
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'
Integer(10).oct() oct(int(10)) Integer(-23).oct() oct(int(-23))
- 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
selfis 0. This behaviour is fairly arbitrary, and in Sage 4.6 this special case was not handled at all, eventually propagating aTypeError. The caller should not rely on the behaviour in caseselfis 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
odd_part(5) odd_part(4) odd_part(factorial(31))
- ord(p)[source]¶
Return the \(p\)-adic valuation of
self.INPUT:
p– 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.
n = 60 n.valuation(2) n.valuation(3) n.valuation(7) n.valuation(1)
We do not require that
pis a prime:sage: (2^11).valuation(4) 5
>>> from sage.all import * >>> (Integer(2)**Integer(11)).valuation(Integer(4)) 5
(2^11).valuation(4)
- 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'
[ZZ(n).ordinal_str() for n in range(25)] ZZ(1001).ordinal_str() ZZ(113).ordinal_str() ZZ(112).ordinal_str() ZZ(111).ordinal_str()
- p_primary_part(p)[source]¶
Return the
p-primary part ofself.INPUT:
p– prime integer
OUTPUT: largest power of
pdividingselfEXAMPLES:
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
n = 40 n.p_primary_part(2) n.p_primary_part(5) n.p_primary_part(7) n.p_primary_part(6)
- 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)
144.perfect_power() # needs sage.libs.pari 1.perfect_power() 0.perfect_power() (-1).perfect_power() (-8).perfect_power() # needs sage.libs.pari (-4).perfect_power() (101^29).perfect_power() # needs sage.libs.pari (-243).perfect_power() # needs sage.libs.pari (-64).perfect_power() # needs sage.libs.pari
- 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
n = 123 n.str(2) n.popcount() n = -17 n.popcount()
- powermod(exp, mod)[source]¶
Compute
self**expmodulomod.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
z = 2 z.powermod(31,31) z.powermod(0,31) z.powermod(-31,31) == 2^-31 % 31
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
z.powermod(31,0)
- previous_prime(proof=None)[source]¶
Return the previous prime before
self.This method calls the PARI function pari:precprime.
INPUT:
proof– ifTrueensure that the returned value is the next prime power and if set toFalseuses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (seeproof.arithmeticorsage.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
10.previous_prime() # needs sage.libs.pari 7.previous_prime() # needs sage.libs.pari 14376485.previous_prime() # needs sage.libs.pari 2.previous_prime()
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
b = (2^1024).previous_prime(proof=False) # needs sage.libs.pari 2^1024 - b # needs sage.libs.pari
- previous_prime_power(proof=None)[source]¶
Return the previous prime power before
self.INPUT:
proof– ifTrueensure that the returned value is the next prime power and if set toFalseuses probabilistic methods (i.e. the result is not guaranteed). By default it uses global configuration variables to determine which alternative to use (seeproof.arithmeticorsage.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().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
# needs sage.libs.pari 3.previous_prime_power() 103.previous_prime_power() 107.previous_prime_power() 2044.previous_prime_power() 2.previous_prime_power()
- 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 tolimitusing 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]
a = 1; a.prime_divisors() a = 100; a.prime_divisors() a = -100; a.prime_divisors() a = 2004; a.prime_divisors()
Setting the optional
limitargument 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]
a = 10^100 + 1 a.prime_divisors() # needs sage.libs.pari a.prime_divisors(limit=10^3) a.prime_divisors(limit=10^7)
- 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 tolimitusing 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]
a = 1; a.prime_divisors() a = 100; a.prime_divisors() a = -100; a.prime_divisors() a = 2004; a.prime_divisors()
Setting the optional
limitargument 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]
a = 10^100 + 1 a.prime_divisors() # needs sage.libs.pari a.prime_divisors(limit=10^3) a.prime_divisors(limit=10^7)
- prime_to_m_part(m)[source]¶
Return the prime-to-\(m\) part of
self, i.e., the largest divisor ofselfthat 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
43434.prime_to_m_part(20) 2048.prime_to_m_part(2) 2048.prime_to_m_part(3) 0.prime_to_m_part(2)
- quo_rem(other)[source]¶
Return the quotient and the remainder of
selfdivided byother. Note that the remainder returned is always either zero or of the same sign asother.INPUT:
other– the divisor
OUTPUT:
q– the quotient ofself/otherr– the remainder ofself/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)
z = Integer(231) z.quo_rem(2) z.quo_rem(-2) z.quo_rem(0) a = ZZ.random_element(10**50) b = ZZ.random_element(10**15) q, r = a.quo_rem(b) q*b + r == a 3.quo_rem(ZZ['x'].0)
- 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
selfmodulo m and whose numerator and denominator is bounded by \(\sqrt{m/2}\).INPUT:
self– integerm– integer
OUTPUT: a
RationalEXAMPLES:
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
(3/7)%100 (29).rational_reconstruction(100)
- real()[source]¶
Return the real part of
self, which isself.EXAMPLES:
sage: Integer(-4).real() -4
>>> from sage.all import * >>> Integer(-Integer(4)).real() -4
Integer(-4).real()
- round(mode='away')[source]¶
Return the nearest integer to
self, which isselfsinceselfis 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
n = 6 n.round()
- 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
500.sign() 0.sign() (-10^43).sign()
- sqrt(prec=None, extend=True, all=False)[source]¶
The square root function.
INPUT:
prec– integer (default:None); ifNone, return an exact square root; otherwise return a numerical square root, to the given bits of precision.extend– boolean (default:True); ifTrue, return a square root in an extension ring, if necessary. Otherwise, raise aValueErrorif the square is not in the base ring. Ignored ifprecis notNone.all– boolean (default:False); ifTrue, return all square roots ofself(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)
Integer(144).sqrt() sqrt(Integer(144)) Integer(102).sqrt() # needs sage.symbolic
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]
n = 2 n.sqrt(all=True) # needs sage.symbolic n.sqrt(prec=10) # needs sage.rings.real_mpfr n.sqrt(prec=100) # needs sage.rings.real_mpfr n.sqrt(prec=100, all=True) # needs sage.rings.real_mpfr n.sqrt(extend=False) (-1).sqrt(extend=False) Integer(144).sqrt(all=True) Integer(0).sqrt(all=True)
>>> 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]
n = 2 n.sqrt(all=True) # needs sage.symbolic n.sqrt(prec=10) # needs sage.rings.real_mpfr n.sqrt(prec=100) # needs sage.rings.real_mpfr n.sqrt(prec=100, all=True) # needs sage.rings.real_mpfr n.sqrt(extend=False) (-1).sqrt(extend=False) Integer(144).sqrt(all=True) Integer(0).sqrt(all=True)
- sqrtrem()[source]¶
Return \((s, r)\) where \(s\) is the integer square root of
selfand \(r\) is the remainder such that \(\text{self} = s^2 + r\). RaisesValueErrorifselfis 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)
25.sqrtrem() 27.sqrtrem() 0.sqrtrem()
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
Integer(-102).sqrtrem()
>>> from sage.all import * >>> Integer(-Integer(102)).sqrtrem() Traceback (most recent call last): ... ValueError: square root of negative integer not defined
Integer(-102).sqrtrem()
- 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 divideself.If
selfis 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
squarefree_part(100) squarefree_part(12) squarefree_part(17*37*37) squarefree_part(-17*32) squarefree_part(1) squarefree_part(-1) squarefree_part(-2) squarefree_part(-4)
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
a = 8 * 5^6 * 101^2 a.squarefree_part(bound=2).factor() a.squarefree_part(bound=5).factor() a.squarefree_part(bound=1000) a.squarefree_part(bound=2**14) a = 7^3 * next_prime(2^100)^2 * next_prime(2^200) # needs sage.libs.pari a / a.squarefree_part(bound=1000) # needs sage.libs.pari
>>> 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
a = 8 * 5^6 * 101^2 a.squarefree_part(bound=2).factor() a.squarefree_part(bound=5).factor() a.squarefree_part(bound=1000) a.squarefree_part(bound=2**14) a = 7^3 * next_prime(2^100)^2 * next_prime(2^200) # needs sage.libs.pari a / a.squarefree_part(bound=1000) # needs sage.libs.pari
- str(base=10)[source]¶
Return the string representation of
selfin 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'
Integer(2^10).str(2) Integer(2^10).str(17)
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
two = Integer(2) two.str(1)
>>> 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
two = Integer(2) two.str(1)
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
two.str(37)
>>> from sage.all import * >>> two.str(Integer(37)) Traceback (most recent call last): ... ValueError: base (=37) must be between 2 and 36
two.str(37)
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'
big = 10^5000000 s = big.str() # long time (2s on sage.math, 2014) len(s) # long time (depends on above defn of s) s[:10] # long time (depends on above defn of s)
>>> 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'
big = 10^5000000 s = big.str() # long time (2s on sage.math, 2014) len(s) # long time (depends on above defn of s) s[:10] # long time (depends on above defn of s)
- 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]
factorial(10).support() (-999).support()
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
0.support()
- 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
w = 6 w.str(2) w.test_bit(2) w.test_bit(-1) x = -20 x.str(2) x.test_bit(4) x.test_bit(5) x.test_bit(6)
- 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 represented inlengthbytesbyteorder– string (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'
(1024).to_bytes(2, byteorder='big') (1024).to_bytes(10, byteorder='big') (-1024).to_bytes(10, byteorder='big', is_signed=True) x = 1000 x.to_bytes((x.bit_length() + 7) // 8, byteorder='little')
- trailing_zero_bits()[source]¶
Return the number of trailing zero bits in
self, i.e. the exponent of the largest power of 2 dividingself.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
11.trailing_zero_bits() (-11).trailing_zero_bits() (11<<5).trailing_zero_bits() (-11<<5).trailing_zero_bits() 0.trailing_zero_bits()
- trial_division(bound='LONG_MAX', start=2)[source]¶
Return smallest prime divisor of
selfup to bound, beginning checking atstart, orabs(self)if no such divisor is found.INPUT:
bound– positive integer that fits in a Csigned longstart– positive integer that fits in a Csigned 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
# needs sage.libs.pari n = next_prime(10^6)*next_prime(10^7); n.trial_division() (-n).trial_division() n.trial_division(bound=100) n.trial_division(bound=-10) n.trial_division(bound=0) ZZ(0).trial_division() # needs sage.libs.pari n = next_prime(10^5) * next_prime(10^40); n.trial_division() n.trial_division(bound=10^4) (-n).trial_division(bound=10^4) (-n).trial_division() n = 2 * next_prime(10^40); n.trial_division() n = 3 * next_prime(10^40); n.trial_division() n = 5 * next_prime(10^40); n.trial_division() n = 2 * next_prime(10^4); n.trial_division() n = 3 * next_prime(10^4); n.trial_division() n = 5 * next_prime(10^4); n.trial_division()
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
n = 3*5*101*103 n.trial_division(start=50)
- trunc()[source]¶
Round this number to the nearest integer, which is
selfsinceselfis an integer.EXAMPLES:
sage: n = 6 sage: n.trunc() 6
>>> from sage.all import * >>> n = Integer(6) >>> n.trunc() 6
n = 6 n.trunc()
- val_unit(p)[source]¶
Return a pair: the \(p\)-adic valuation of
self, and th`p`-adicic unit ofself.INPUT:
p– integer at least 2
OUTPUT:
v_p(self)– the \(p\)-adic valuation ofselfu_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)
n = 60 n.val_unit(2) n.val_unit(3) n.val_unit(7) (2^11).val_unit(4) 0.val_unit(2)
- valuation(p)[source]¶
Return the \(p\)-adic valuation of
self.INPUT:
p– 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.
n = 60 n.valuation(2) n.valuation(3) n.valuation(7) n.valuation(1)
We do not require that
pis a prime:sage: (2^11).valuation(4) 5
>>> from sage.all import * >>> (Integer(2)**Integer(11)).valuation(Integer(4)) 5
(2^11).valuation(4)
- xgcd(n)[source]¶
Return the extended gcd of this element and
n.INPUT:
n– integer
OUTPUT:
A triple
(g, s, t)such thatgis the nonnegative gcd ofselfandn, andsandtare 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)
6.xgcd(4)
- class sage.rings.integer.IntegerWrapper[source]¶
Bases:
IntegerRationale for the
IntegerWrapperclass:With
Integerobjects, the allocation/deallocation function slots are hijacked with custom functions that stick already allocatedIntegerobjects (with initializedparentandmpz_tfields) into a pool on “deallocation” and then pull them out whenever a new one is needed. BecauseIntegersobjects are so common, this is actually a significant savings. However, this does cause issues with subclassing a Python class directly fromInteger(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 originalIntegeralloc/dealloc methods, before they are swapped manually for the custom ones.The constructor of
IntegerWrapperfurther allows for specifying an alternative parent toIntegerRing.
- class sage.rings.integer.int_to_Z[source]¶
Bases:
MorphismEXAMPLES:
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
f = ZZ.coerce_map_from(int) f f(1rL)
- sage.rings.integer.is_Integer(x)[source]¶
Return
Trueifxis of the SageIntegertype.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
from sage.rings.integer import is_Integer is_Integer(2) is_Integer(2/1) is_Integer(int(2)) is_Integer('5')
- 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
from sage.rings.integer import make_integer make_integer('-29') make_integer(29)