FLINT3.7.0-dev
/

arith_hrr_expsum_factored

Synopsis#include <flint/arith.h>
void arith_hrr_expsum_factored(trig_prod_t prod, ulong k, ulong n)source

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

A_k(n) = \sum_{\substack{0 \le h < k \\ \gcd(h, k) = 1}} \exp\left(\pi i \left[ s(h,k) - \frac{2hn}{k}\right]\right)

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

The sum is factored into sums for the prime powers dividing k using the multiplicativity relations of Lehmer and Whiteman [Whiteman1956], and each prime-power sum is a single cosine (or zero) determined by a square root modulo the prime power. The prefactor is set to zero when A_k(n) = 0. Since A_k(n) depends only on n \bmod k, n should be reduced modulo k; the computation needs 24k and 24n to fit in a word. See Computing the partition function.

References#

  • [Whiteman1956] Whiteman, A. L. : A sum connected with the series for the partition function, Pacific Journal of Mathematics 6:1 (1956) 159–176
Cite this page

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