FLINT3.7.0-dev
/

fmpq_next_calkin_wilf, _fmpq_next_calkin_wilf

Synopsis#include <flint/fmpq.h>
void fmpq_next_calkin_wilf(fmpq_t res, const fmpq_t x)source
void _fmpq_next_calkin_wilf(fmpz_t rnum, fmpz_t rden, const fmpz_t num, const fmpz_t den)source

Given a nonnegative canonical xx, set the result to the next fraction in the breadth-first traversal of the Calkin–Wilf tree [CalkinWilf2000]: 0,1,1/2,2,1/3,3/2,2/3,3,1/4,4/3,3/5,5/2,2/5,…0, 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, \ldots Starting from zero, every nonnegative rational is generated exactly once.

The successor of x>0x > 0 is 1/(2⌊x⌋+1−x)1/(2\lfloor x \rfloor + 1 - x), which needs no GCD, so this enumeration is cheaper than fmpq_next_minimal. It is not ordered by height: some fractions of small height appear late.

References#

  • [CalkinWilf2000] N. Calkin and H. S. Wilf, "Recounting the rationals", American Mathematical Monthly 107:4 (2000), 360–363. https://doi.org/10.2307/2589182
Cite this page

The FLINT team, “fmpq_next_calkin_wilf, _fmpq_next_calkin_wilf (fmpq.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpq/fmpq_next_calkin_wilf.html (generated 2026-11-02).