Goulib.math2 module

more math than math standard library, without numpy

Goulib.math2.longint(mantissa, exponent)

Returns:int equivalent to int(mantissa*10^exponent) without rounding errors

Goulib.math2.cmp(x, y)

Compare the two objects x and y and return an integer according to the outcome. The return value is negative if x < y, zero if x == y and strictly positive if x > y.

Goulib.math2.allclose(a, b, rel_tol=1e-09, abs_tol=0.0)

Returns:True if two arrays are element-wise equal within a tolerance.

Goulib.math2.is_number(x)

Returns:True if x is a number of any type, including Complex

Goulib.math2.is_complex(x)

Goulib.math2.is_real(x)

Goulib.math2.sign(number)

Returns:1 if number is positive, -1 if negative, 0 if ==0

Goulib.math2.rint(v)

Returns:int value nearest to float v

Goulib.math2.is_integer(x, rel_tol=0, abs_tol=0)

Returns:True if float x is an integer within tolerances

Goulib.math2.int_or_float(x, rel_tol=0, abs_tol=0)

Parameters:x – int or float Returns:int if x is (almost) an integer, otherwise float

Goulib.math2.format(x, decimals=3)

formats a float with given number of decimals, but not an int

Returns:string repr of x with decimals if not int

Goulib.math2.gcd(*args)

greatest common divisor of an arbitrary number of args

Goulib.math2.lcm(*args)

least common multiple of any number of integers

Goulib.math2.xgcd(a, b)

Extended GCD

Returns:(gcd, x, y) where gcd is the greatest common divisor of a and b

with the sign of b if b is nonzero, and with the sign of a if b is 0. The numbers x,y are such that gcd = ax+by.

Goulib.math2.coprime(*args)

Returns:True if args are coprime to each other

Goulib.math2.coprimes_gen(limit)

generates coprime pairs using Farey sequence

Goulib.math2.carmichael(n)

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. :param n: int :see: https://en.wikipedia.org/wiki/Carmichael_function :see: https://oeis.org/A002322

also known as the reduced totient function or the least universal exponent function.

Goulib.math2.is_primitive_root(x, m, s={})

returns True if x is a primitive root of m

Parameters:s – set of coprimes to m, if already known

Goulib.math2.primitive_root_gen(m)

generate primitive roots modulo m

Goulib.math2.primitive_roots(modulo)

Goulib.math2.quad(a, b, c, allow_complex=False)

solves quadratic equations aX^2+bX+c=0

Parameters:

• a,b,c – floats
• allow_complex – function returns complex roots if True

Returns:

x1,x2 real or complex solutions

Goulib.math2.ceildiv(a, b)

Goulib.math2.ipow(x, y, z=0)

Parameters:

• x – number (int or float)
• y – int power
• z – int optional modulus

Returns:

(x**y) % z as integer if possible

Goulib.math2.pow(x, y, z=0)

Returns:(x**y) % z as integer

Goulib.math2.sqrt(n)

square root :return: int, float or complex depending on n

Goulib.math2.isqrt(n)

integer square root

Returns:largest int x for which x * x <= n

Goulib.math2.icbrt(n)

integer cubic root

Returns:largest int x for which x * x * x <= n

Goulib.math2.is_square(n)

Goulib.math2.introot(n, r=2)

integer r-th root

Returns:int, greatest integer less than or equal to the r-th root of n.

For negative n, returns the least integer greater than or equal to the r-th root of n, or None if r is even.

Goulib.math2.is_power(n)

Returns:integer that, when squared/cubed/etc, yields n,

or 0 if no such integer exists. Note that the power to which this number is raised will be prime.

Goulib.math2.multiply(x, y)

Karatsuba fast multiplication algorithm

https://en.wikipedia.org/wiki/Karatsuba_algorithm

Copyright (c) 2014 Project Nayuki http://www.nayuki.io/page/karatsuba-multiplication

Goulib.math2.accsum(it)

Yield accumulated sums of iterable: accsum(count(1)) -> 1,3,6,10,…

Goulib.math2.cumsum(it)

Yield accumulated sums of iterable: accsum(count(1)) -> 1,3,6,10,…

Goulib.math2.mul(nums, init=1)

Returns:Product of nums

Goulib.math2.dot_vv(a, b, default=0)

dot product for vectors

Parameters:

• a – vector (iterable)
• b – vector (iterable)
• default – default value of the multiplication operator

Goulib.math2.dot_mv(a, b, default=0)

dot product for vectors

Parameters:

• a – matrix (iterable or iterables)
• b – vector (iterable)
• default – default value of the multiplication operator

Goulib.math2.dot_mm(a, b, default=0)

dot product for matrices

Parameters:

• a – matrix (iterable or iterables)
• b – matrix (iterable or iterables)
• default – default value of the multiplication operator

Goulib.math2.dot(a, b, default=0)

dot product

general but slow : use dot_vv, dot_mv or dot_mm if you know a and b’s dimensions

Goulib.math2.zeros(shape)

See:https://docs.scipy.org/doc/numpy/reference/generated/numpy.zeros.html

Goulib.math2.diag(v)

Create a two-dimensional array with the flattened input as a diagonal.

Parameters:v – If v is a 2-D array, return a copy of its diagonal. If v is a 1-D array, return a 2-D array with v on the diagonal See:https://docs.scipy.org/doc/numpy/reference/generated/numpy.diag.html#numpy.diag

Goulib.math2.identity(n)

Goulib.math2.eye(n)

Goulib.math2.transpose(m)

Returns:matrix m transposed

Goulib.math2.maximum(m)

Compare N arrays and returns a new array containing the element-wise maxima

Parameters:m – list of arrays (matrix) Returns:list of maximal values found in each column of m See:http://docs.scipy.org/doc/numpy/reference/generated/numpy.maximum.html

Goulib.math2.minimum(m)

Compare N arrays and returns a new array containing the element-wise minima

Parameters:m – list of arrays (matrix) Returns:list of minimal values found in each column of m See:http://docs.scipy.org/doc/numpy/reference/generated/numpy.minimum.html

Goulib.math2.vecadd(a, b, fillvalue=0)

addition of vectors of inequal lengths

Goulib.math2.vecsub(a, b, fillvalue=0)

substraction of vectors of inequal lengths

Goulib.math2.vecneg(a)

unary negation

Goulib.math2.vecmul(a, b)

product of vectors of inequal lengths

Goulib.math2.vecdiv(a, b)

quotient of vectors of inequal lengths

Goulib.math2.veccompare(a, b)

compare values in 2 lists. returns triple number of pairs where [a<b, a==b, a>b]

Goulib.math2.sat(x, low=0, high=None)

saturates x between low and high

Goulib.math2.norm_2(v)

Returns:“normal” euclidian norm of vector v

Goulib.math2.norm_1(v)

Returns:“manhattan” norm of vector v

Goulib.math2.norm_inf(v)

Returns:infinite norm of vector v

Goulib.math2.norm(v, order=2)

See:http://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.norm.html

Goulib.math2.dist(a, b, norm=<function norm_2>)

Goulib.math2.vecunit(v, norm=<function norm_2>)

Returns:vector normalized

Goulib.math2.hamming(s1, s2)

Calculate the Hamming distance between two iterables

Goulib.math2.sets_dist(a, b)

See:http://stackoverflow.com/questions/11316539/calculating-the-distance-between-two-unordered-sets

Goulib.math2.sets_levenshtein(a, b)

levenshtein distance on sets

See:http://en.wikipedia.org/wiki/Levenshtein_distance

Goulib.math2.levenshtein(seq1, seq2)

levenshtein distance

Returns:distance between 2 iterables See:http://en.wikipedia.org/wiki/Levenshtein_distance

Goulib.math2.recurrence(factors, values, cst=0, max=None, mod=0)

general generator for recurrences

Parameters:

• signature – factors defining the recurrence
• values – list of initial values

Goulib.math2.lucasU(p, q)

Goulib.math2.lucasV(p, q)

Goulib.math2.kfibonacci_gen(k, init=None, max=None, mod=0)

Generate k-fibonacci serie

Goulib.math2.fibonacci_gen(max=None, mod=0)

Generate fibonacci serie (k=2)

Goulib.math2.kfibonacci(k, mod=0)

k-fibonacci series n-th element

Parameters:

• k – int number of consecutive terms to add
• mod – int optional modulo

Returns:

function(n) returning the n-th element

Goulib.math2.fibonacci(n, mod=0)

fibonacci series n-th element :param n: int can be extremely high, like 1e19 ! :param mod: int optional modulo

Goulib.math2.is_fibonacci(n)

returns True if n is in Fibonacci series

Goulib.math2.pisano_cycle(mod)

Goulib.math2.pisano_period(mod)

Goulib.math2.collatz(n)

Goulib.math2.collatz_gen(n=0)

Goulib.math2.collatz_period(n)

Goulib.math2.pascal_gen()

Pascal’s triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0<=k<=n.

https://oeis.org/A007318

Goulib.math2.catalan(n)

Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

Goulib.math2.catalan_gen()

Generate Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!). Also called Segner numbers.

Goulib.math2.is_pythagorean_triple(a, b, c)

Goulib.math2.primitive_triples()

generates primitive Pythagorean triplets x<y<z

sorted by hypotenuse z, then longest side y through Berggren’s matrices and breadth first traversal of ternary tree :see: https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples

Goulib.math2.triples()

generates all Pythagorean triplets triplets x<y<z sorted by hypotenuse z, then longest side y

Goulib.math2.divisors(n)

Parameters:n – int Returns:all divisors of n: divisors(12) -> 1,2,3,4,6,12

including 1 and n, except for 1 which returns a single 1 to avoid messing with sum of divisors…

Goulib.math2.proper_divisors(n)

Returns:all divisors of n except n itself.

class Goulib.math2.Sieve(f, init)

Bases: object

__init__(f, init)

Initialize self. See help(type(self)) for accurate signature.

__len__()

__getitem__(index)

__call__(n)

Call self as a function.

resize(n)

__class__

alias of builtins.type

__delattr__

Implement delattr(self, name).

__dir__()

Default dir() implementation.

__eq__

Return self==value.

__format__()

Default object formatter.

__ge__

Return self>=value.

__getattribute__

Return getattr(self, name).

__gt__

Return self>value.

__hash__

Return hash(self).

__init_subclass__()

This method is called when a class is subclassed.

The default implementation does nothing. It may be overridden to extend subclasses.

__le__

Return self<=value.

__lt__

Return self<value.

__ne__

Return self!=value.

__new__()

Create and return a new object. See help(type) for accurate signature.

__reduce__()

Helper for pickle.

__reduce_ex__()

Helper for pickle.

__repr__

Return repr(self).

__setattr__

Implement setattr(self, name, value).

__sizeof__()

Size of object in memory, in bytes.

__str__

Return str(self).

Goulib.math2.erathostene(n)

Goulib.math2.sieve(n, oneisprime=False)

prime numbers from 2 to a prime < n

Goulib.math2.primes(n)

memoized list of n first primes

Warning:do not call with large n, use prime_gen instead

Goulib.math2.is_prime_euler(n, eb=(2, ))

Euler’s primality test

Parameters:

• n – int number to test
• eb – test basis

Returns:

False if not prime, True if prime, but also for many pseudoprimes…

See:

https://en.wikipedia.org/wiki/Euler_pseudoprime

Goulib.math2.is_prime(n, oneisprime=False, tb=(3, 5, 7, 11), eb=(2, ), mrb=None)

main primality test.

Parameters:

• n – int number to test
• oneisprime – bool True if 1 should be considered prime (it was, a long time ago)
• tb – trial division basis
• eb – Euler’s test basis
• mrb – Miller-Rabin basis, automatic if None

See:

https://en.wikipedia.org/wiki/Baillie%E2%80%93PSW_primality_test

It’s an implementation of the BPSW test (Baillie-Pomerance-Selfridge-Wagstaff) with some prefiltes for speed and is deterministic for all numbers less than 2^64 Iin fact, while infinitely many false positives are conjectured to exist, no false positives are currently known. The prefilters consist of trial division against 2 and the elements of the tuple tb, checking whether n is square, and Euler’s primality test to the bases in the tuple eb. If the number is less than 3825123056546413051, we use the Miller-Rabin test on a set of bases for which the test is known to be deterministic over this range.

Goulib.math2.nextprime(n)

Determines, with some semblance of efficiency, the least prime number strictly greater than n.

Goulib.math2.prevprime(n)

Determines, very inefficiently, the largest prime number strictly smaller than n.

Goulib.math2.primes_gen(start=2, stop=None)

generate prime numbers from start

Goulib.math2.random_prime(bits)

returns a random number of the specified bit length

Goulib.math2.euclid_gen()

generates Euclid numbers: 1 + product of the first n primes

Goulib.math2.prime_factors(num, start=2)

generates all prime factors (ordered) of num

Goulib.math2.lpf(n)

greatest prime factor

Goulib.math2.gpf(n)

greatest prime factor

Goulib.math2.prime_divisors(num, start=2)

generates unique prime divisors (ordered) of num

Goulib.math2.is_multiple(n, factors)

return True if n has ONLY factors as prime factors

Goulib.math2.factorize(n)

find the prime factors of n along with their frequencies. Example:

>>> factor(786456)
[(2,3), (3,3), (11,1), (331,1)]

Goulib.math2.factors(n)

Goulib.math2.sigma(n)

Goulib.math2.number_of_divisors(n)

Goulib.math2.omega(n)

Number of distinct primes dividing n

Goulib.math2.bigomega(n)

Number of prime divisors of n counted with multiplicity

Goulib.math2.moebius(n)

Möbius (or Moebius) function mu(n). mu(1) = 1; mu(n) = (-1)^k if n is the product of k different primes; otherwise mu(n) = 0.

Goulib.math2.euler_phi(n)

Euler totient function

See:http://stackoverflow.com/questions/1019040/how-many-numbers-below-n-are-coprimes-to-n

Goulib.math2.totient(n)

Euler totient function

See:http://stackoverflow.com/questions/1019040/how-many-numbers-below-n-are-coprimes-to-n

Goulib.math2.kempner(n)

“Kempner function, also called Smarandache function

Returns:int smallest positive integer m such that n divides m!. Parameters:n – int See:https://en.wikipedia.org/wiki/Kempner_function See:http://mathworld.wolfram.com/SmarandacheFunction.html

Goulib.math2.prime_ktuple(constellation)

generates tuples of primes with specified differences

Parameters:constellation – iterable of int differences betwwen primes to return Note:negative int means the difference must NOT be prime See:https://en.wikipedia.org/wiki/Prime_k-tuple

(0, 2) twin primes (0, 4) cousin primes (0, 6) sexy primes (0, 2, 6), (0, 4, 6) prime triplets (0, 6, 12, -18) sexy prime triplets (0, 2, 6, 8) prime quadruplets (0, 6, 12, 18) sexy prime quadruplets (0, 2, 6, 8, 12), (0, 4, 6, 10, 12) quintuplet primes (0, 4, 6, 10, 12, 16) sextuplet primes

Goulib.math2.twin_primes()

Goulib.math2.cousin_primes()

Goulib.math2.sexy_primes()

Goulib.math2.sexy_prime_triplets()

Goulib.math2.sexy_prime_quadruplets()

Goulib.math2.lucas_lehmer(p)

Lucas Lehmer primality test for Mersenne exponent p

Parameters:p – int Returns:True if 2^p-1 is prime

Goulib.math2.digits_gen(num, base=10)

generates int digits of num in base BACKWARDS

Goulib.math2.digits(num, base=10, rev=False)

Returns:list of digits of num expressed in base, optionally reversed

Goulib.math2.digsum(num, f=None, base=10)

sum of digits

Parameters:

• num – number
• f – int power or function applied to each digit
• base – optional base

Returns:

sum of f(digits) of num

digsum(num) -> sum of digits digsum(num,base=2) -> number of 1 bits in binary represenation of num digsum(num,2) -> sum of the squares of digits digsum(num,f=lambda x:x**x) -> sum of the digits elevaed to their own power

Goulib.math2.integer_exponent(a, b=10)

Returns:int highest power of b that divides a. See:https://reference.wolfram.com/language/ref/IntegerExponent.html

Goulib.math2.trailing_zeros(a, b=10)

Returns:int highest power of b that divides a. See:https://reference.wolfram.com/language/ref/IntegerExponent.html

Goulib.math2.power_tower(v)

Returns:v[0]**v[1]**v[2] … See:http://ajcr.net#Python-power-tower/

Goulib.math2.carries(a, b, base=10, pos=0)

Returns:int number of carries required to add a+b in base

Goulib.math2.powertrain(n)

Returns:v[0]**v[1]*v[2]**v[3] …**(v[-1] or 0) Author:# Chai Wah Wu, Jun 16 2017 See:http://oeis.org/A133500

Goulib.math2.str_base(num, base=10, numerals='0123456789abcdefghijklmnopqrstuvwxyz')

Returns:

string representation of num in base

Parameters:

• num – int number (decimal)
• base – int base, 10 by default
• numerals – string with all chars representing numbers in base base. chars after the base-th are ignored

Goulib.math2.int_base(num, base)

Returns:

int representation of num in base

Parameters:

• num – int number (decimal)
• base – int base, <= 10

Goulib.math2.num_from_digits(digits, base=10)

Parameters:

• digits – string or list of digits representing a number in given base
• base – int base, 10 by default

Returns:

int number

Goulib.math2.reverse(i)

Goulib.math2.is_palindromic(num, base=10)

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.

Goulib.math2.is_anagram(num1, num2, base=10)

Check if ‘num1’ and ‘num2’ have the same digits in base

Goulib.math2.is_pandigital(num, base=10)

Returns:True if num contains all digits in specified base

Goulib.math2.bouncy(n, up=False, down=False)

Parameters:

• n – int number to test
• up – bool
• down – bool

bouncy(x) returns True for Bouncy numbers (digits form a strictly non-monotonic sequence) (A152054) bouncy(x,True,None) returns True for Numbers with digits in nondecreasing order (OEIS A009994) bouncy(x,None,True) returns True for Numbers with digits in nonincreasing order (OEIS A009996)

Goulib.math2.repunit_gen(base=10, digit=1)

generate repunits

Goulib.math2.repunit(n, base=10, digit=1)

Returns:nth repunit

Goulib.math2.rational_form(numerator, denominator)

information about the decimal representation of a rational number.

Returns:5 integer : integer, decimal, shift, repeat, cycle

• shift is the len of decimal with leading zeroes if any
• cycle is the len of repeat with leading zeroes if any

Goulib.math2.rational_str(n, d)

Goulib.math2.rational_cycle(num, den)

periodic part of the decimal expansion of num/den. Any initial 0’s are placed at end of cycle.

See:https://oeis.org/A036275

Goulib.math2.tetrahedral(n)

Returns:int n-th tetrahedral number See:https://en.wikipedia.org/wiki/Tetrahedral_number

Goulib.math2.sum_of_squares(n)

Returns:1^2 + 2^2 + 3^2 + … + n^2 See:https://en.wikipedia.org/wiki/Square_pyramidal_number

Goulib.math2.pyramidal(n)

Returns:1^2 + 2^2 + 3^2 + … + n^2 See:https://en.wikipedia.org/wiki/Square_pyramidal_number

Goulib.math2.sum_of_cubes(n)

Returns:1^3 + 2^3 + 3^3 + … + n^3 See:https://en.wikipedia.org/wiki/Squared_triangular_number

Goulib.math2.bernouilli_gen(init=1)

generator of Bernouilli numbers

Parameters:init – int -1 or +1.

• -1 for “first Bernoulli numbers” with B1=-1/2
• +1 for “second Bernoulli numbers” with B1=+1/2

https://en.wikipedia.org/wiki/Bernoulli_number https://rosettacode.org/wiki/Bernoulli_numbers#Python:_Optimised_task_algorithm

Goulib.math2.bernouilli(n, init=1)

Goulib.math2.faulhaber(n, p)

sum of the p-th powers of the first n positive integers

Returns:1^p + 2^p + 3^p + … + n^p See:https://en.wikipedia.org/wiki/Faulhaber%27s_formula

Goulib.math2.is_happy(n)

Goulib.math2.lychrel_seq(n)

Goulib.math2.lychrel_count(n, limit=96)

number of lychrel iterations before n becomes palindromic

Parameters:

• n – int number to test
• limit – int max number of loops. default 96 corresponds to the known most retarded non lychrel number

Warning:

there are palindrom lychrel numbers such as 4994

Goulib.math2.is_lychrel(n, limit=96)

Warning:there are palindrom lychrel numbers such as 4994

Goulib.math2.polygonal(s, n)

Goulib.math2.triangle(n)

Returns:nth triangle number, defined as the sum of [1,n] values. See:http://en.wikipedia.org/wiki/Triangular_number

Goulib.math2.triangular(n)

Returns:nth triangle number, defined as the sum of [1,n] values. See:http://en.wikipedia.org/wiki/Triangular_number

Goulib.math2.is_triangle(x)

Returns:True if x is a triangle number

Goulib.math2.is_triangular(x)

Returns:True if x is a triangle number

Goulib.math2.square(n)

Goulib.math2.pentagonal(n)

Returns:nth pentagonal number See:https://en.wikipedia.org/wiki/Pentagonal_number

Goulib.math2.is_pentagonal(n)

Returns:True if x is a pentagonal number

Goulib.math2.hexagonal(n)

Returns:nth hexagonal number See:https://en.wikipedia.org/wiki/Hexagonal_number

Goulib.math2.is_hexagonal(n)

Goulib.math2.heptagonal(n)

Goulib.math2.is_heptagonal(n)

Goulib.math2.octagonal(n)

Goulib.math2.is_octagonal(n)

Goulib.math2.partition(n)

The partition function p(n)

gives the number of partitions of a nonnegative integer n into positive integers. (There is one partition of zero into positive integers, i.e. the empty partition, since the empty sum is defined as 0.)

See:http://oeis.org/wiki/Partition_function https://oeis.org/A000041

Goulib.math2.partitionsQ(n, d=0)

Goulib.math2.get_cardinal_name(num)

Get cardinal name for number (0 to 1 million)

Goulib.math2.abundance(n)

Goulib.math2.is_perfect(n)

Returns:-1 if n is deficient, 0 if perfect, 1 if abundant See:https://en.wikipedia.org/wiki/Perfect_number,

https://en.wikipedia.org/wiki/Abundant_number, https://en.wikipedia.org/wiki/Deficient_number

Goulib.math2.number_of_digits(num, base=10)

Return number of digits of num (expressed in base ‘base’)

Goulib.math2.chakravala(n)

solves x^2 - n*y^2 = 1 for x,y integers

https://en.wikipedia.org/wiki/Pell%27s_equation https://en.wikipedia.org/wiki/Chakravala_method

Goulib.math2.factorialk(n, k)

Multifactorial of n of order k, n(!!…!).

This is the multifactorial of n skipping k values. For example,

factorialk(17, 4) = 17!!!! = 17 * 13 * 9 * 5 * 1

In particular, for any integer n, we have

factorialk(n, 1) = factorial(n) factorialk(n, 2) = factorial2(n)

Parameters:n – int Calculate multifactorial. If n < 0, the return value is 0.

:param k : int Order of multifactorial. :return: int Multifactorial of n.

Goulib.math2.factorial2(n)

Goulib.math2.factorial_gen(f=<function <lambda>>)

Generator of factorial :param f: optional function to apply at each step

Goulib.math2.binomial(n, k)

binomial coefficient “n choose k” :param: n, k int :return: int, number of ways to chose n items in k, unordered

See:https://en.wikipedia.org/wiki/binomial

Goulib.math2.choose(n, k)

binomial coefficient “n choose k” :param: n, k int :return: int, number of ways to chose n items in k, unordered

See:https://en.wikipedia.org/wiki/binomial

Goulib.math2.ncombinations(n, k)

binomial coefficient “n choose k” :param: n, k int :return: int, number of ways to chose n items in k, unordered

See:https://en.wikipedia.org/wiki/binomial

Goulib.math2.binomial_exponent(n, k, p)

Returns:int largest power of p that divides binomial(n,k)

Goulib.math2.log_factorial(n)

Returns:float approximation of ln(n!) by Ramanujan formula

Goulib.math2.log_binomial(n, k)

Returns:float approximation of ln(binomial(n,k))

Goulib.math2.ilog(a, b, upper_bound=False)

discrete logarithm x such that b^x=a

Parameters:

• a,b – integer
• upper_bound – bool. if True, returns smallest x such that b^x>=a

Returns:

x integer such that b^x=a, or upper_bound, or None

https://en.wikipedia.org/wiki/Discrete_logarithm

Goulib.math2.angle(u, v, unit=True)

Parameters:

• u,v – iterable vectors
• unit – bool True if vectors are unit vectors. False increases computations

Returns:

float angle n radians between u and v unit vectors i

Goulib.math2.sin_over_x(x)

numerically safe sin(x)/x

Goulib.math2.slerp(u, v, t)

spherical linear interpolation

Parameters:

• u,v – 3D unit vectors
• t – float in [0,1] interval

Returns:

vector interpolated between u and v

Goulib.math2.proportional(nseats, votes)

assign n seats proportionaly to votes using the https://en.wikipedia.org/wiki/Hagenbach-Bischoff_quota method

Parameters:

• nseats – int number of seats to assign
• votes – iterable of int or float weighting each party

Result:

list of ints seats allocated to each party

Goulib.math2.triangular_repartition(x, n)

divide 1 into n fractions such that:

• their sum is 1
• they follow a triangular linear repartition (sorry, no better name for now) where x/1 is the maximum

Goulib.math2.rectangular_repartition(x, n, h)

divide 1 into n fractions such that:

• their sum is 1
• they follow a repartition along a pulse of height h<1

Goulib.math2.de_bruijn(k, n)

De Bruijn sequence for alphabet k and subsequences of length n.

https://en.wikipedia.org/wiki/De_Bruijn_sequence

Goulib.math2.mod_inv(a, b)

Goulib.math2.mod_div(a, b, m)

Returns:x such that (b*x) mod m = a mod m

Goulib.math2.mod_fact(n, m)

Returns:n! mod m

Goulib.math2.chinese_remainder(m, a)

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Parameters:

• m – list of int moduli
• a – list of int remainders

Returns:

smallest int x such that x mod ni=ai

Goulib.math2.mod_binomial(n, k, m, q=None)

calculates C(n,k) mod m for large n,k,m

Parameters:

• n – int total number of elements
• k – int number of elements to pick
• m – int modulo (or iterable of (m,p) tuples used internally)
• q – optional int power of m for prime m, used internally

Goulib.math2.baby_step_giant_step(y, a, n)

solves Discrete Logarithm Problem (DLP) y = a**x mod n

Goulib.math2.mod_matmul(A, B, mod=0)

Goulib.math2.mod_matpow(M, power, mod=0)

Goulib.math2.matrix_power(M, power, mod=0)

Goulib.math2.mod_sqrt(n, p)

modular sqrt(n) mod p

Goulib.math2.mod_fac(n, mod, mod_is_prime=False)

modular factorial : return n! % modulo if module is prime, use Wilson’s theorem https://en.wikipedia.org/wiki/Wilson%27s_theorem

Goulib.math2.pi_digits_gen()

generates pi digits as a sequence of INTEGERS ! using Jeremy Gibbons spigot generator

:see :http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

Goulib.math2.lucky_gen()

generates lucky numbers :see: https://en.wikipedia.org/wiki/Lucky_number :see: https://oeis.org/A000959

Goulib.math2.pfactor(n)

Helper function for sprp.

Returns the tuple (x,y) where n - 1 == (2 ** x) * y and y is odd. We have this bit separated out so that we don’t waste time recomputing s and d for each base when we want to check n against multiple bases.

Goulib.math2.sprp(n, a, s=None, d=None)

Checks n for primality using the Strong Probable Primality Test to base a. If present, s and d should be the first and second items, respectively, of the tuple returned by the function pfactor(n)

Goulib.math2.jacobi(a, p)

Computes the Jacobi symbol (a|p), where p is a positive odd number. :see: https://en.wikipedia.org/wiki/Jacobi_symbol

Goulib.math2.pollardRho_brent(n)

Brent’s improvement on Pollard’s rho algorithm.

Returns:int n if n is prime

otherwise, we keep chugging until we find a factor of n strictly between 1 and n. :see: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm

Goulib.math2.pollard_pm1(n, B1=100, B2=1000)

Pollard’s p+1 algorithm, two-phase version.

Returns:n if n is prime; otherwise, we keep chugging until we find a factor of n strictly between 1 and n.

Goulib.math2.mlucas(v, a, n)

Helper function for williams_pp1(). Multiplies along a Lucas sequence modulo n.

Goulib.math2.williams_pp1(n)

Williams’ p+1 algorithm. :return: n if n is prime otherwise, we keep chugging until we find a factor of n strictly between 1 and n.

Goulib.math2.ecadd(p1, p2, p0, n)

Goulib.math2.ecdub(p, A, n)

Goulib.math2.ecmul(m, p, A, n)

Goulib.math2.factor_ecm(n, B1=10, B2=20)

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. :return: n if n is prime otherwise, we keep chugging until we find a factor of n strictly between 1 and n

Goulib.math2.legendre(a, p)

Functions to comptue the Legendre symbol (a|p). The return value isn’t meaningful if p is composite :see: https://en.wikipedia.org/wiki/Legendre_symbol

Goulib.math2.legendre2(a, p)

Functions to comptue the Legendre symbol (a|p). The return value isn’t meaningful if p is composite :see: https://en.wikipedia.org/wiki/Legendre_symbol