fmpz – integers

class flint.fmpz(*args)

The fmpz type represents an arbitrary-size integer.

>>> fmpz(3) ** 25
847288609443

classmethod bell_number(cls, ulong n)

Returns the Bell number \(B_n\) as an fmpz.

>>> fmpz.bell_number(10)
115975

classmethod bin_uiui(cls, ulong n, ulong k)

Returns the binomial coefficient \({n \choose k}\) as an fmpz.

bit_length(self)

denominator

divisor_sigma(n, k)

Returns the divisor sum \(\sigma_k(n)\) as an fmpz.

>>> fmpz(60).divisor_sigma(0)
12
>>> fmpz(60).divisor_sigma(1)
168
>>> fmpz(60).divisor_sigma(10)
605263138639095300

classmethod euler_number(cls, ulong n)

Returns the Euler number \(E_n\) as an fmpz.

>>> fmpz.euler_number(10)
-50521

euler_phi(n)

Returns the Euler totient function \(\varphi(n)\) as an fmpz.

>>> fmpz(60).euler_phi()
16
>>> fmpz(3**10).euler_phi()
39366

classmethod fac_ui(cls, ulong n)

Returns the factorial \(n!\) as an fmpz.

>>> fmpz.fac_ui(10)
3628800

factor(self, trial_limit=None)

Factors self into prime numbers, returning a list of (prime, exp) pairs. The sign is ignored.

>>> fmpz(5040).factor()
[(2, 4), (3, 2), (5, 1), (7, 1)]
>>> fmpz(10**35 + 1).factor()
[(11, 1), (9091, 1), (909091, 1), (4147571, 1), (265212793249617641, 1)]
>>> len(fmpz.fac_ui(1000).factor())
168

Warning: factoring large integers can be slow unless all prime factors are small.

If trial_limit is set, perform trial division with at most this many primes, returning an incomplete factorization in which the largest factor may be composite. Factors largers than the trial division limit may still be found if it is cheap to do so, but no expensive algorithms will be run.

>>> fmpz(2**128+10).factor()
[(2, 1), (7, 1), (23, 1), (677, 1), (2957, 1), (1042733, 1), (506256324715258822390969, 1)]
>>> fmpz(2**128+10).factor(trial_limit=200)
[(2, 1), (7, 1), (23, 1), (677, 1), (1560971251139657345905734136865089, 1)]

factor_smooth(self, bits=15, int proved=-1)

classmethod fib_ui(cls, ulong n)

Returns the Fibonacci number \(F_n\) as an fmpz.

>>> fmpz.fib_ui(10)
55

gcd(self, other)

Returns the greatest common divisor of self and other.

>>> fmpz(30).gcd(45)
15

height_bits(self, bool signed=False)

is_perfect_power(self)

Return True if this integer is of the form \(r^k\) with \(k>1\), False otherwise. \(0, 1, -1\) are considered perfect powers.

>>> fmpz(81).is_perfect_power()
True
>>> fmpz(1234).is_perfect_power()
False

is_prime(self)

is_probable_prime(self)

is_square(self)

Return True if perfect square and False otherwise.

>>> fmpz(25).is_square()
True
>>> fmpz(101).is_square()
False

is_zero(self)

isqrt(self)

Return square root rounded down.

>>> fmpz(9).isqrt()
3
>>> fmpz(8).isqrt()
2

jacobi(self, other)

lcm(self, other)

Returns the greatest common divisor of self and other.

>>> fmpz(30).gcd(45)
15

moebius_mu(n)

Returns the Moebius function \(\mu(n)\) as an fmpz.

>>> [fmpz(n).moebius_mu() for n in range(10)]
[0, 1, -1, -1, 0, -1, 1, -1, 0, 0]

numerator

partitions_p(n)

Returns \(p(n)\), the number of partitions of \(n\), as an fmpz.

>>> [fmpz(n).partitions_p() for n in range(8)]
[1, 1, 2, 3, 5, 7, 11, 15]
>>> fmpz(100).partitions_p()
190569292
>>> len(str(fmpz(10**9).partitions_p()))
35219

The partition function grows rapidly. On a 32-bit system, \(n\) must not be larger than about \(10^{16}\). On a 64-bit system, \(n\) must not be larger than about \(10^{20}\). For large \(n\), this function benefits from setting ctx.threads = 2 on multicore systems.

classmethod primorial_ui(cls, ulong n)

Returns the product of all primes less than or equal to n (n primorial) as an fmpz.

>>> fmpz.primorial_ui(10)
210

repr(self)

rising(s, ulong n)

Returns the rising factorial \(s (s+1) \cdots (s+n-1)\) as an fmpz.

>>> fmpz(10).rising(5)
240240

root(self, long n)

sqrt(self)

Return exact integer square root of self or raise an error.

>>> fmpz(9).sqrt()
3
>>> fmpz(8).sqrt()
Traceback (most recent call last):
    ...
flint.utils.flint_exceptions.DomainError: not a square number

sqrtmod(self, p)

Return modular square root of self modulo p or raise an error.

>>> fmpz(10).sqrtmod(13)
6
>>> (6**2) % 13
10
>>> fmpz(11).sqrtmod(13)
Traceback (most recent call last):
    ...
flint.utils.flint_exceptions.DomainError: modular square root does not exist

The modulus p must be a prime number.

sqrtrem(self)

Return the integer square root of self and remainder.

>>> fmpz(9).sqrtrem()
(3, 0)
>>> fmpz(8).sqrtrem()
(2, 4)
>>> c = fmpz(123456789012345678901234567890)
>>> u, v = c.sqrtrem()
>>> u ** 2 + v == c
True

classmethod stirling_s1(cls, ulong n, ulong k)

Returns the Stirling number of the first kind \(S_1(n,k)\) as an fmpz.

>>> fmpz.stirling_s1(10,5)
-269325

classmethod stirling_s2(cls, ulong n, ulong k)

Returns the Stirling number of the second kind \(S_2(n,k)\) as an fmpz.

>>> fmpz.stirling_s2(10,5)
42525

str(self, int base=10, long condense=0)

Converts self to a string, optionally in a non-decimal base and optionally showing only leading and trailing digits.

>>> (fmpz(3) ** 100).str()
'515377520732011331036461129765621272702107522001'
>>> (fmpz(3) ** 100).str(base=3, condense=10)
'1000000000{...81 digits...}0000000000'