Journal of Integer Sequences, Vol. 21 (2018), Article 18.2.4 |

INRIA – LFANT

CNRS – IMB – UMR 5251

33400 Talence

France

William Hart

Fachbereich Mathematik

Technische Universität Kaiserslautern

67653 Kaiserslautern

Germany

Fredrik Johansson

INRIA – LFANT

CNRS – IMB – UMR 5251

Université de Bordeaux

33400 Talence

France

**Abstract:**

The main step in numerical evaluation of
classical Sl_{2}(**Z**) modular forms
is to compute the sum of the first *N*
nonzero terms in the sparse *q*-series
belonging to the Dedekind eta function or the Jacobi theta constants.
We construct short addition sequences to perform
this task using *N* + o(*N*) multiplications.
Our constructions rely on the representability of
specific quadratic progressions of integers as sums
of smaller numbers of the same kind. For example, we show that every
generalized pentagonal number *c* ≥ 5 can be written as
*c* = 2*a* + *b*
where *a*, *b* are smaller generalized pentagonal numbers.
We also give a baby-step giant-step algorithm
that uses O(*N* / (log *N*)^{r})
multiplications for every *r* ≥ 0,
beating the lower bound of *N* multiplications required
when computing the terms explicitly. These results lead
to speed-ups in practice.

(Concerned with sequences A001318 A002620 A084848 A085635 A182568.)

Received September 14 2016; revised versions received February 16 2018; February 21 2018.
Published in *Journal of Integer Sequences*, March 3 2018.

Return to