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 Hn=1+1/2+⋯+1/nH_n = 1 + 1/2 + \cdots + 1/n, with H0=0H_0 = 0. Throws if n≥2FLINT_BITS−1n \ge 2^{\mathtt{FLINT\_BITS} - 1}.

Values whose numerator and denominator fit in a word (n≤46n \le 46 on a 64-bit machine) are read from a table. For larger nn the function uses Hn=H⌊n/2⌋/2+∑k≤n, k odd1/kH_n = H_{\lfloor n/2 \rfloor}/2 + \sum_{k \le n,\, k \text{ odd}} 1/k recursively, which gives every odd kk a weight (2d−1)/2d−1(2^d - 1)/2^{d-1} that depends only on the dyadic range n/2d<k≤n/2d−1n/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(nlog⁡n)log⁡n)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-11-02).