fmpq_next_calkin_wilf, _fmpq_next_calkin_wilf
Synopsis
#include <flint/fmpq.h>Given a nonnegative canonical x, 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, \ldots Starting from zero, every nonnegative rational is generated exactly once.
The successor of x > 0 is 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-10-20).
@misc{flint-doc-fmpq-fmpq-next-calkin-wilf,
author = {{The FLINT team}},
title = {{fmpq\_next\_calkin\_wilf, \_fmpq\_next\_calkin\_wilf (fmpq.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpq/fmpq_next_calkin_wilf.html},
note = {Generated 2026-10-20}
}