arith.h

Set the result to the harmonic number H_n = \sum_{k=1}^n 1/k, or to 0 for n \le 0. Wrappers of fmpq_harmonic_ui.

Set the result to the Bernoulli number B_n, in lowest terms with a positive denominator. Wrappers of bernoulli_fmpq_ui: the value is read from the Bernoulli cache if present and otherwise computed from the zeta function or by the multimodular algorithm.

Set the entries to B_0, B_1, \ldots, B_{n-1}. For n < 700 the function calls _arith_bernoulli_number_vec_recursive, otherwise _arith_bernoulli_number_vec_multi_mod. For long vectors, bernoulli_fmpq_vec_no_cache (which uses the zeta function and several threads) is usually faster.

Sets the numerators and denominators of B_0, \ldots, B_{n-1} using Ramanujan's recurrence, which expresses B_m in terms of the B_k with k \equiv m \pmod 6. Intended for n up to a few thousand.

Sets the numerators and denominators of B_0, \ldots, B_{n-1} by power series inversion modulo word-size primes and Chinese remaindering.

Sets den to the denominator of B_n in lowest terms: 1 for odd n \ge 3 and n = 0, 2 for n = 1, and for even n \ge 2 the product of the primes p with (p - 1) \mid n, by the von Staudt–Clausen theorem. Values for n \le 178 are read from a table.

Returns b such that |B_n| < 2^{\lfloor b \rfloor}, from |B_n| < 4 \cdot n!/(2\pi)^n and n! \le (n+1)^{n+1} e^{-n}. Odd n are not treated specially. The bound is evaluated in double precision and is not guaranteed for n > 10^{14}.

Sets poly to the Bernoulli polynomial B_n(x) = \sum_{k=0}^n \binom{n}{k} B_k x^{n-k}, computing B_0, \ldots, B_n with _arith_bernoulli_number_vec and scaling by binomial coefficients over a common denominator.

Sets res to E_n. A wrapper of arb_fmpz_euler_number_ui, which uses a table for small n, the Dirichlet beta function \beta(n+1) for n < 2000 and a combination of the beta function with a multimodular method (as for Bernoulli numbers) for larger n.

Sets res to E_0, E_1, \ldots, E_{n-1}, for n \ge 0.

Returns b such that |E_n| < 2^{\lfloor b \rfloor}, from |E_n| < 2^{n+2} n!/\pi^{n+1} and n! \le (n+1)^{n+1} e^{-n}. Odd n are not treated specially. Not guaranteed for n > 10^{14}.

Sets poly to the Euler polynomial E_n(x), using

with B_{n+1}(x) computed once by arith_bernoulli_polynomial and rescaled.

Set s to |s(n,k)|, s(n,k) or S(n,k), for any n, k \ge 0. These functions compute an isolated value, with algorithms chosen according to n and k/n (binary splitting, power sums, power series and multimodular methods).

Set row to the values for k = 0, 1, \ldots, \mathit{klen} - 1 of |s(n,k)|, s(n,k) or S(n,k). A full row has \mathit{klen} = n + 1; entries with k > n are set to zero.

Set the entry (n, k) of the r \times c matrix mat to |s(n,k)|, s(n,k) or S(n,k), for 0 \le n < r and 0 \le k < c; the entries above the diagonal are zero. The square matrices of s and S are inverses of each other. Wrappers of gr_mat_stirling, which fills the rows with the triangular recurrences.

Set the result to the Bell number B_n. The default version uses a table for n \le 25 (64-bit), the Bell triangle in fixed-size multiword arithmetic for n \le 58, Dobiński's formula for n \le 3400 and the multimodular algorithm above.

Set b to B_0, B_1, \ldots, B_{n-1}. The recursive version uses the Bell triangle (Aitken's array), with O(n^2) additions of numbers of O(n \log n) bits; the multi_mod version computes the vector modulo word-size primes with arith_bell_number_nmod_vec and combines them by Chinese remaindering, in O(n^2 \log^{O(1)} n). The default version uses the recursive algorithm for n < 5000.

Returns B_n modulo the modulus of mod, which can be any integer \ge 1.

Set b to B_0, \ldots, B_{n-1} modulo the modulus of mod.

Returns b such that B_n < 2^{\lfloor b \rfloor}, from de Bruijn's asymptotic expansion of \log B_n [deB1958] with a margin. The bound is verified for n < 2^{64} but not proved in general; an earlier version used the weaker bound B_n < (0.792n/\log(n+1))^n of [BerTas2010].

Sets x to p(n). A wrapper of partitions_fmpz_ui, which uses the Hardy–Ramanujan–Rademacher formula for large n.

Set res to p(0), p(1), \ldots, p(\mathit{len} - 1), exactly or modulo the modulus of mod, by inverting Euler's pentagonal series \prod_{k \ge 1} (1 - x^k) = \sum_{j \in \mathbb{Z}} (-1)^j x^{j(3j-1)/2} with _fmpz_poly_inv_series or _nmod_poly_inv_series. The cost is O(M(n)) operations on numbers of O(\sqrt n) bits, or modulo the modulus.

Initialises prod to the empty product with prefactor 1. Inline; no memory is allocated.

Multiplies prod (which must be initialised with trig_prod_init) by a symbolic expression for the exponential sum

of the Hardy–Ramanujan–Rademacher formula, where s(h,k) is a Dedekind sum, as a product of cosines.

Sets r to the number r_k(n) of representations of n as an ordered sum of k squares of integers (signs and order count), with r_k(0) = 1 and r_k(n) = 0 for n < 0.

Sets r_i to r_k(i) for 0 \le i < n, the first n coefficients of

computed from the sparse expansions of \vartheta_3 and \vartheta_3^2 and a truncated power.

Sets res to \tau(n), the coefficient of q^n in \Delta(q) = q \prod_{k \ge 1} (1 - q^k)^{24}, or to 0 for n \le 0.

Sets res to the polynomial with coefficients \tau(0), \tau(1), \ldots, \tau(n-1), using Jacobi's identity

evaluated with three squarings of which the first, of a very sparse series, is done directly.

Sets the coefficients of res to the positive divisors of |n| in increasing order (so res has length \sigma_0(n)), and to the zero polynomial if n = 0. Uses a table for |n| < \mathtt{FLINT\_BITS} and otherwise factors n with fmpz_factor and generates the products of prime powers.

Sets res to the first len values g(0), g(1), \ldots of Landau's function, the largest order of an element of the symmetric group S_n, equivalently the largest \operatorname{lcm}(n_1, \ldots, n_r) with n_1 + \cdots + n_r \le n.