package euler

The type of the factorized form of an integer. The factorization of n is a list [ (p1, k1) ; … ; (pℓ, kℓ) ] such that n = p1k1 × … × pℓkℓ and p1 < … < pℓ are prime.

The logarithmic integral function. It is defined only for numbers (strictly) greater than 1.0.

• parameter precision

  The series summation stops as soon as the increment becomes smaller than precision.

overestimate_number_of_primes nmax gives a relatively precise upper bound on the number of prime numbers below nmax.

The twenty‐five prime numbers less than 100, in ascending order.

The prime numbers less than 10 000, in ascending order.

iter_primes nmax ~do_prime:f calls f on all prime numbers in ascending order from 2 to slightly more than nmax, as soon as they are found. This is useful to iterate on prime numbers and stop when some condition is met. Complexity: time 𝒪(nmax×log(log(nmax))), space 𝒪(π(√nmax)) = 𝒪(√nmax ∕ log(nmax)).

The sequence of prime numbers up to a specified bound. This is significantly slower than iter_primes (about 50 times slower for nmax = 1_000_000_000), but has the advantage that advancing through the sequence is controlled by the consumer, This is a purely functional algorithm, hence the produced sequence is persistent. Complexity: time 𝒪(nmax×log(nmax)×log(log(nmax))), space 𝒪(√nmax ∕ log(nmax)).

Extended prime sieve. factorizing_sieve nmax ~do_factors:f computes the factorization of all numbers up to nmax (included). The result is an array s such that s.(n) is the factorization of n. The function also calls f on the factorization of each number from 2 to nmax, in order. This is useful to iterate on the factorized form of (small) numbers and stop when some condition is met. Note that this is costly both in time and in space, so nmax is bridled with an internal upper bound. Complexity: time 𝒪(nmax×log(log(nmax))), space 𝒪(nmax×log(log(nmax))).

Primality test. is_prime n is true if and only if n is a prime number. Note that this is a deterministic test. Complexity: 𝒪(fast).

Integer factorization. This uses Lenstra’s elliptic‐curve algorithm for finding factors (as of 2018, it is the most efficient known algorithm for 64‐bit numbers). Complexity: 𝒪(terrible).

• parameter tries

  The number of elliptic curves to try before resigning.

• parameter max_fact

  The “small exponents” tried by Lenstra’s algorithm are the factorial numbers up to the factorial of max_fact.

• returns

  the prime factorization of the given number. It may contain non‐prime factors d, if their factorization failed within the allowed time; this is signaled by negating their value, as in (−d, 1). This is highly unlikely with default parameters.

• raises Assert_failure

  when the number to factorize is not positive.

number_of_divisors n is the number of divisors of n (including 1 and n itself), provided that n is positive.

Divisor sum. sum_of_divisors ~k n, often noted σ_k(n), is the sum of the k-th powers of all the divisors of n (including 1 and n itself), provided that k is non-negative and n is positive. In particular, for k = 0 it gives the number of divisors, and for k = 1 it gives the sum of the divisors. The default value of k is 1.

• raises Overflow

  when the result overflows.

divisors n is the list of all divisors of n (including 1 and n itself) in ascending order, provided that n is positive.

divisor_pairs n is the list of all pairs (d, n/d) where d divides n and 1 ≤ d ≤ √n, provided that n is positive. Pairs are presented in ascending order of d. When n is a perfect square, the pair (√n, √n) is presented once.

Same as divisor_pairs but returns a Seq.t.

Euler’s totient function. eulerphi n, often noted φ(n), is the number of integers between 1 and n which are coprime with n, provided that n is positive.

eulerphi_from_file nmax loads precomputed values of φ from a file on disk.

• returns

  an array phi such that phi.(n) = φ(n) for all 1 ≤ n ≤ nmax.

Jordan’s totient function. jordan ~k n, often noted J_k(n), is the number of k-tuples (a₁, …, a_k) such that every a_i is between 1 and n, and gcd(a₁, …, a_k, n) = 1 (in other words, the tuple is setwise-coprime with n, but not necessarily pairwise-coprime). This is a generalization of Euler’s totient, which is obtained with k = 1. It requires that k and n are positive.

• raises Overflow

  when the result overflows.

Carmichael’s function. carmichael n, often noted λ(n), is the smallest positive exponent k such that, for all a coprime with n, we have a^k ≡ 1 (mod n). In other words, it is the exponent of the multiplicative group of integers modulo n, that is, the least common multiple of the orders of all the invertible integers modulo n. It divides Euler’s totient but may be strictly smaller than it. This function requires that n is positive.

Möbius’ function. mobius n, often noted μ(n), is 0 if n has a square factor, −1 if n has an odd number of prime factors, or +1 if n has an even number of prime factors. This function requires that n is positive.

Arithmetic derivative of an integer. derivative n, often noted D(n), is such that D(0) = 0, D(−1) = −1, D(p) = 1 for all primes p, and D(m×n) = D(m)×n + m×D(n) for all integers m, n.

• raises Overflow

  when the result overflows.

order ~modulo:m a, where m ≠ 0, is the multiplicative order of a modulo m, This is the smallest positive exponent n such that aⁿ ≡ 1 (mod m).

If given, factors_mod must be the factorization of m.

If given, factors_pred_primes must be the factorizations of all the p−1 where p are the prime factors of m, sorted by p.

• raises Division_by_zero

  when a is not invertible modulo m.

order_with_known_multiple ~phi ~modulo:m a is the same as order ~modulo:m a, but exploits the fact that the order is a divisor of phi. Values suitable for phi always include λ(m) (carmichael m) and φ(m) (eulerphi m); in some situations, a smaller value may be known.

If given, factors_phi must be the factorization of phi.

• raises Division_by_zero

  when a is not invertible modulo m.

order_mod_prime_pow ~modulo:(p, k) a, where p is a prime and k > 0, is the multiplicative order of a modulo pk, It is assumed that pk does not overflow.

If given, factors_pred_prime must be the factorization of p−1.

• raises Division_by_zero

  when a is not invertible modulo m.