goulib.math2¶
more math than math standard library, without numpy
Functions
|
|
|
|
|
Yield accumulated sums of iterable: accsum(count(1)) -> 1,3,6,10,... |
|
|
|
|
|
solves Discrete Logarithm Problem (DLP) y = a**x mod n |
|
|
|
generator of Bernouilli numbers |
|
Number of prime divisors of n counted with multiplicity |
|
binomial coefficient "n choose k" :param: n, k int :return: int, number of ways to chose n items in k, unordered |
|
|
|
|
|
Carmichael function :return : int smallest positive integer m such that a^m mod n = 1 for every integer a between 1 and n that is coprime to n. |
|
|
|
Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). |
|
Generate Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). |
|
|
|
solves x^2 - n*y^2 = 1 for x,y integers |
|
|
|
binomial coefficient "n choose k" :param: n, k int :return: int, number of ways to chose n items in k, unordered |
|
Compare the two objects x and y and return an integer according to the outcome. |
|
|
|
|
|
|
|
|
|
generates coprime pairs using Farey sequence |
|
|
|
Yield accumulated sums of iterable: accsum(count(1)) -> 1,3,6,10,... |
|
De Bruijn sequence for alphabet k and subsequences of length n. |
|
Create a two-dimensional array with the flattened input as a diagonal. |
|
|
|
generates int digits of num in base BACKWARDS |
|
sum of digits |
|
|
|
|
|
dot product |
|
dot product for matrices |
|
dot product for vectors |
|
dot product for vectors |
|
|
|
|
|
|
|
|
|
generates Euclid numbers: 1 + product of the first n primes |
|
Euler totient function |
|
|
|
Factors n using the elliptic curve method, using Montgomery curves and an algorithm analogous to the two-phase variant of Pollard’s p-1 method. |
|
|
|
Generator of factorial :param f: optional function to apply at each step |
|
Multifactorial of n of order k, n(!!...!). |
|
find the prime factors of n along with their frequencies. |
|
|
|
sum of the p-th powers of the first n positive integers |
|
fibonacci series n-th element :param n: int can be extremely high, like 1e19 ! :param mod: int optional modulo |
|
Generate fibonacci serie (k=2) |
|
formats a float with given number of decimals, but not an int |
|
Inverse the gamma function. |
|
greatest common divisor of an arbitrary number of args |
|
Get cardinal name for number (0 to 1 million) |
|
greatest prime factor |
|
Calculate the Hamming distance between two iterables |
|
|
|
|
|
integer cubic root |
|
|
|
discrete logarithm x such that b^x=a |
|
|
|
|
|
|
|
integer r-th root |
|
|
|
Check if 'num1' and 'num2' have the same digits in base |
|
|
|
returns True if n is in Fibonacci series |
|
|
|
|
|
|
|
|
|
|
|
return True if n has ONLY factors as prime factors |
|
|
|
|
|
Check if 'num' in base 'base' is a palindrome, that's it, if it can be read equally from left to right and right to left. |
|
|
|
|
|
|
|
|
|
main primality test. |
|
Euler's primality test |
|
returns True if x is a primitive root of m |
|
|
|
|
|
|
|
|
|
|
|
integer square root |
|
Computes the Jacobi symbol (a|p), where p is a positive odd number. |
|
"Kempner function, also called Smarandache function |
|
k-fibonacci series n-th element |
|
Generate k-fibonacci serie |
|
Lambert W function, principal branch. |
|
least common multiple of any number of integers |
|
Functions to comptue the Legendre symbol (a|p). |
|
Functions to comptue the Legendre symbol (a|p). |
|
levenshtein distance |
|
|
|
|
|
|
|
greatest prime factor |
|
|
|
|
|
Lucas Lehmer primality test for Mersenne exponent p |
|
generates lucky numbers :see: https://en.wikipedia.org/wiki/Lucky_number :see: https://oeis.org/A000959 |
|
number of lychrel iterations before n becomes palindromic |
|
|
|
|
|
Compare N arrays and returns a new array containing the element-wise maxima |
|
Compare N arrays and returns a new array containing the element-wise minima |
|
Helper function for williams_pp1(). |
|
calculates C(n,k) mod m for large n,k,m |
|
|
|
modular factorial : return n! % modulo if module is prime, use Wilson's theorem https://en.wikipedia.org/wiki/Wilson%27s_theorem |
|
|
|
|
|
|
|
|
|
modular sqrt(n) mod p |
|
Möbius (or Moebius) function mu(n). |
|
|
|
Karatsuba fast multiplication algorithm |
|
binomial coefficient "n choose k" :param: n, k int :return: int, number of ways to chose n items in k, unordered |
|
Determines, with some semblance of efficiency, the least prime number strictly greater than n. |
|
|
|
|
|
|
|
|
|
|
|
Return number of digits of num (expressed in base 'base') |
|
|
|
|
|
Number of distinct primes dividing n |
|
The partition function p(n) |
|
|
|
Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0<=k<=n. |
|
|
|
Helper function for sprp. |
|
generates pi digits as a sequence of INTEGERS ! using Jeremy Gibbons spigot generator |
|
|
|
|
|
Brent’s improvement on Pollard’s rho algorithm. |
|
Pollard’s p+1 algorithm, two-phase version. |
|
|
|
|
|
|
|
|
|
Determines, very inefficiently, the largest prime number strictly smaller than n. |
|
generates unique prime divisors (ordered) of num |
|
generates all prime factors (ordered) of num |
|
generates tuples of primes with specified differences |
|
memoized list of n first primes |
|
generate prime numbers from start |
|
generate primitive roots modulo m |
|
|
|
generates primitive Pythagorean triplets x<y<z |
|
|
|
assign n seats proportionaly to votes using the https://en.wikipedia.org/wiki/Hagenbach-Bischoff_quota method |
|
|
|
solves quadratic equations aX^2+bX+c=0 |
|
returns a random number of the specified bit length |
|
periodic part of the decimal expansion of num/den. |
|
information about the decimal representation of a rational number. |
|
|
|
divide 1 into n fractions such that: |
|
general generator for recurrences |
|
|
|
generate repunits |
|
|
|
|
|
saturates x between low and high |
|
|
|
levenshtein distance on sets |
|
|
|
|
|
|
|
prime numbers from 2 to a prime < n |
|
|
|
|
|
numerically safe sin(x)/x |
|
spherical linear interpolation |
|
Checks n for primality using the Strong Probable Primality Test to base a. |
|
square root :return: int, float or complex depending on n |
|
|
|
|
|
|
|
|
|
|
|
Euler totient function |
|
|
|
|
|
|
|
|
|
divide 1 into n fractions such that: |
|
generates all Pythagorean triplets triplets x<y<z sorted by hypotenuse z, then longest side y |
|
|
|
addition of vectors of inequal lengths |
|
compare values in 2 lists. |
|
quotient of vectors of inequal lengths |
|
product of vectors of inequal lengths |
|
unary negation |
|
substraction of vectors of inequal lengths |
|
|
|
Williams’ p+1 algorithm. |
|
Extended GCD |
|
Classes
|
General sieve |