FLINT3.7.0-dev
/

fmpq_harmonic_ui, _fmpq_harmonic_ui

Synopsis#include <flint/fmpq.h>
void fmpq_harmonic_ui(fmpq_t x, ulong n)source
void _fmpq_harmonic_ui(fmpz_t num, fmpz_t den, ulong n)source

Set the result to the harmonic number H_n = 1 + 1/2 + \cdots + 1/n, with H_0 = 0. Throws if n \ge 2^{\mathtt{FLINT\_BITS} - 1}.

Values whose numerator and denominator fit in a word (n \le 46 on a 64-bit machine) are read from a table. For larger n the function uses H_n = H_{\lfloor n/2 \rfloor}/2 + \sum_{k \le n,\, k \text{ odd}} 1/k recursively, which gives every odd k a weight (2^d - 1)/2^{d-1} that depends only on the dyadic range n/2^d < k \le n/2^{d-1}, and sums the weighted odd terms by Binary splitting and product trees, accumulating word-size partial sums in the base case. A final GCD puts the result in lowest terms. The cost is O(M(n \log n) \log n) bit operations.

Cite this page

The FLINT team, “fmpq_harmonic_ui, _fmpq_harmonic_ui (fmpq.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpq/fmpq_harmonic_ui.html (generated 2026-10-20).