# Algorithmic counting of nonequivalent compact Huffman codes

Christian Elsholtz  Christian Elsholtz Institute of Analysis and Number Theory
Graz University of Technology Kopernikusgasse 24, A-8010 Graz, Austria
<EMAIL_ADDRESS>,  Clemens Heuberger  Clemens Heuberger Department of
Mathematics Alpen-Adria-Universität Klagenfurt Universitätsstraße 65–67,
A-9020 Klagenfurt am Wörthersee, Austria<EMAIL_ADDRESS>and  Daniel
Krenn  Daniel Krenn Department of Mathematics Alpen-Adria-Universität
Klagenfurt Universitätsstraße 65–67, A-9020 Klagenfurt am Wörthersee, Austria
math<EMAIL_ADDRESS>
###### Abstract.

It is known that the following five counting problems lead to the same integer
sequence $\mathop{{#1}{}}(n)$:

  1. (1)

the number of nonequivalent compact Huffman codes of length $n$ over an
alphabet of $t$ letters,

  2. (2)

the number of “nonequivalent” canonical rooted $t$-ary trees (level-greedy
trees) with $n$ leaves,

  3. (3)

the number of “proper” words,

  4. (4)

the number of bounded degree sequences, and

  5. (5)

the number of ways of writing

$1=\frac{1}{t^{x_{1}}}+\dots+\frac{1}{t^{x_{n}}}$

with integers $0\leq x_{1}\leq x_{2}\leq\dots\leq x_{n}$.

In this work, we show that one can compute this sequence for all $n<N$ with
essentially one power series division. In total we need at most
$N^{1+\varepsilon}$ additions and multiplications of integers of $cN$ bits,
$c<1$, or $N^{2+\varepsilon}$ bit operations, respectively. This improves an
earlier bound by Even and Lempel who needed $\mathop{{O}{}}(N^{3})$ operations
in the integer ring or $\mathop{{O}{}}(N^{4})$ bit operations, respectively.

###### Key words and phrases:

unit-fractions, Huffman codes, $t$-ary trees, counting, generating function

###### 2010 Mathematics Subject Classification:

05A15; 05C05, 05C30, 11D68, 68P30

C. Elsholtz is supported by the Austrian Science Fund (FWF): W1230. C.
Heuberger and D. Krenn are supported by the Austrian Science Fund (FWF):
P28466-N35.

##  1\. Introduction

### Codes, unit fractions and more

Elsholtz, Heuberger and Prodinger [8] studied the number $\mathop{{#1}{}}(r)$
of solutions of the equation

$\sum_{i=1}^{r}\frac{1}{t^{x_{i}}}=1,$

where the $x_{i}$ are nonnegative integers and $0\leq x_{1}\leq\dots\leq
x_{r}$. It is known that this counting problem is equivalent to several other
counting problems, namely the number of “nonequivalent” complete rooted
$t$-ary trees (also called “level-greedy trees”), the number of “proper words”
(in the sense of Even and Lempel [9]), the number of bounded degree sequences,
and the number of “nonequivalent” compact Huffman codes of length $r$ over an
alphabet of $t$ letters. For a detailed survey on the existing results,
applications and literature on these sequences; see [8]. As a small concrete
example, we note that for $t=2$, $r=5$ we have $f_{2}(5)=3$, as can be seen
from working out the following:

$1=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\frac{1}{16}+\frac{1}{16}=\frac{1}{2}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}+\frac{1}{8}=\frac{1}{4}+\frac{1}{4}+\frac{1}{4}+\frac{1}{8}+\frac{1}{8}.$

Since $\mathop{{#1}{}}(r)$ is positive only when $r=1+n(t-1)$, it is more
convenient to study $\mathop{{#1}{}}(n)=f_{t}(1+n(t-1))$ instead. For $t=2$
the values of $\mathop{{#1}{}}(n)$ start with

$1,1,1,2,3,5,9,16,28,50,89,159,\ldots,$

for $t=3$ with

$1,1,1,2,4,7,13,25,48,92,176,338,\ldots,$

and the first terms of $\mathop{{#1}{}}(n)$ are

$1,1,1,2,4,8,15,29,57,112,220,432,\ldots.$

These are sequences A002572, A176485 and A176503 in the On-Line Encyclopedia
of Integer Sequences [28].

### Asymptotics

It has been proved (see Elsholtz, Heuberger, Prodinger [8]) that for fixed
$t$, the asymptotic growth of these sequences can be described by two main
terms and an error term as

$\mathop{{#1}{}}(n)=R\rho^{n}+R_{2}\rho_{2}^{n}+\mathop{{O}{}}\big{(}r_{3}^{n}\big{)},$
(1.1)

where $1<r_{3}<\rho_{2}<\rho<2$. Here all constants depend on $t$. In
particular, if $t=2$, then

$\displaystyle\rho$ $\displaystyle=1.794\ldots,$ $\displaystyle\rho_{2}$
$\displaystyle=1.279\ldots,$ $\displaystyle r_{3}$ $\displaystyle=1.123,$
$\displaystyle R$ $\displaystyle=0.14\ldots,$ $\displaystyle R_{2}$
$\displaystyle=0.061\ldots.$

Moreover, the authors of [8] also show that
$\rho=2-2^{-t-1}+\mathop{{O}{}}\big{(}t\,4^{-t}\big{)}$ as $t\to\infty$.

Beside the enumeration of all the objects, the asymptotic behavior of the
expectation, the variance or the (local) limiting distribution for many
different parameters have been studied; see [17, 18].

### Algorithmic counting

As this family of sequences appears in many different contexts and that the
sequences’ growth rates have been studied in detail (see the section above and
the introduction of [8] for full details), it is somehow surprising that the
current record on the algorithmic complexity of determining the members of the
sequence (in the case $t=2$) appears to be an almost 50 years old paper by
Even and Lempel [9]. Hence it seemed worthwhile to study this complexity from
a new point of view and we thus succeeded to improve the upper bound
complexity considerably; see section below.

The algorithm of Even and Lempel [9]—as mentioned, it seems this is the
fastest known algorithm—produces the sequence $\mathop{{#1}{}}(n)$ for $n<N$.
It takes $\mathop{{O}{}}(N^{3})$ additions of integers bounded by
$\mathop{{O}{}}(\rho^{N})$ (with $\rho<2$; so integers with roughly $N$ bits
in size), which are $\mathop{{O}{}}(N^{4})$ bit operations. They only studied
the case $t=2$ in detail, but mention that their result can be generalized to
arbitrary $t$.

### Main result

In this paper we take an entirely new approach to the problem of evaluating
$g_{t}(n)$. Rather than thinking about an algorithm itself, as Even and Lempel
[9] did, we think about how to evaluate the recently established generating
function in [8] efficiently. As it turns out the cost essentially comes from
one division of power series of precision111We say that a power series $H$ has
precision $N$ if we can write it as
$H(q)=\sum_{n=0}^{N-1}h_{n}q^{n}+\mathop{{O}{}}(q^{N})$ with explicit
coefficients $h_{n}$. $N$ whose coefficients are integers bounded by
$\mathop{{O}{}}(\rho^{N})$ (with $\rho<2$).

Estimating the cost of this evaluation strategy leads to tremendous
improvement of the cost of using [9]. It is not obvious that the cost for
evaluation of numerator and denominator of the generating function are
asymptotically (much) smaller than the total cost; see Theorem 1 for details.
We in particular show that the cost for evaluating numerator and denominator
are asymptotically almost (neglecting logarithmic factors) by a factor $N$
smaller.

Using the multiplication algorithms of Schönhage and Strassen [30] or of Fürer
[12, 13] (see Section 2 for an overview) our algorithm leads to $N(\log
N)^{2}\,2^{\mathop{{O}{}}(\log^{*}N)}$ operations in the integer ring and
$N^{2}(\log N)^{4}\,2^{\mathop{{O}{}}(\log^{*}N)}$ bit operations, where
$\log^{*}N$ denotes the _iterated logarithm_.222The _iterated logarithm_ (also
called _log star_) gives the number of applications of the logarithm so that
the result is at most $1$. For example, we can define it recursively by
$\log^{*}M=1+\log^{*}(\log M)$ if $M>1$ and $\log^{*}M=0$ otherwise.333The
factors $2^{\mathop{{O}{}}(\log^{*}N)}$ might be replaced by
$\mathop{{O}{}}(1)$ (i.e., bounded by a constant) when using the results of
the unpublished manuscript of Harvey and van der Hoeven [16]. Details about
[16] and its current status can be found at
https://web.maths.unsw.edu.au/~davidharvey/papers/nlogn. In Remark 6.2 a
discussion on the memory requirements can be found. An implementation of this
algorithm, based on FLINT [11, 15] (which is, for example, included in the
SageMath mathematics software [29]) is also available;444The code accompanying
this article can be downloaded from https://gitlab.com/dakrenn/count-
nonequivalent-compact-huffman-codes. see also Appendix A for the relevant
lines of code and remarks related to the implementation. In Appendix B, we
discuss the running times of this implementation.

The literature describes a number of algorithms constructing the complete list
of $t$-ary Huffman codes of length $r=1+n(t-1)$; see [19, 23, 26, 27]. There
is no performance analysis given. But, as the number of such codes grows
exponentially in $r$ it is clear that listing all codes is not a fast method
to determine the number of such codes only. The algorithm by Even and Lempel
[9] computes the number $f_{2}(n)$ without listing all codes, and is to the
best of our knowledge the fastest algorithm previously known. Our algorithm
relies on calculations involving power series with large integer coefficients.

It should also be emphasized that the output $f_{t}(n)$ of the algorithm grows
exponentially in $n$ (this was mentioned above), therefore the number of bits
to represent $f_{t}(n)$ is linear in $n$ whereas the input is only logarithmic
in $n$. The quite general survey paper by Klazar [24] studies classes of
problems where the output needs at most a polynomial number of steps, in terms
of the combined size of input and output. As we can compute $f_{t}(n)$
efficiently, this problem falls into the class considered by Klazar.

### Notes

It should be pointed out that in this article, we derive and compare upper
bounds. It might be that the actual cost are smaller. However, as we compute
the first $N$ coefficients all at the same time and the coefficients grow
exponentially in $N$, a lower bound for the number of bit operations
necessarily contains a factor $N^{2}$. Moreover, as multiplication of some
sort is involved, lower order factors (growing with $N$) are expected as well.

We also mention that the following is open: How fast can a single coefficient
$\mathop{{#1}{}}(n)$ (in contrast to all coefficients with $n<N$) be computed?

##  2\. Cost of the underlying operations

In this section, we give a brief overview on the time requirements for
performing addition and multiplication of two integers and for performing
multiplication and division of power series. The current state of the art is
also summarized in Table 2.1.

Task | Ring operations | Bit operations
---|---|---
addition | $N$ | $NM$
multiplication | $N\log N\,2^{\mathop{{O}{}}(\log^{*}N)}$ | $N\log N\,2^{\mathop{{O}{}}(\log^{*}N)}\cdot M\log M\,2^{\mathop{{O}{}}(\log^{*}M)}$
division | $N\log N\,2^{\mathop{{O}{}}(\log^{*}N)}$ | $N^{2}M(\log N)^{2}2^{\mathop{{O}{}}(\log^{*}N)}$
Table 2.1. Cost of operations of power series with precision $N$ and
coefficients with bit size $M$. (We assume $M=\mathop{{O}{}}(N)$ and state a
simpler expression for the bit operations for division.)

### Addition and multiplication

First, assume that we want to perform addition of two numbers bounded by
$2^{M}$, i.e., numbers with $M$ bits. We have to look at each bit of the
numbers exactly once and add those (maybe with a carry). Therefore, we need
$\mathop{{O}{}}(M)$ bit operations.

Next, we look at multiplication of two numbers bounded by $2^{M}$. It is clear
that this can be achieved with $\mathop{{O}{}}(M^{2})$ operations, but it can
be done better. An overview is given in the survey article by Karatsuba [20].
The Karatsuba multiplication algorithm [21, 22] has a complexity of
$\mathop{{O}{}}(M^{\log_{2}3})$. A faster generalisation of it is the
Toom–Cook-algorithm [4]. Combining Karatsuba multiplication with the Fast
Fourier Transform algorithm (see Cooley and Tukey [5]) gives an algorithm with
bit complexity $\mathop{{O}{}}(M(\log M)^{(2+\varepsilon)})$; see [1, 2, 3,
25].

The multiplication algorithm given by Schönhage and Strassen (see [30]) takes
$\mathop{{O}{}}(M\log M\log\log M)$ time. It also uses fast Fourier transform.
The asymptotically fastest known555See also footnote 3 for a recent
development in integer multiplication. multiplication algorithm is given by
Fürer [12, 13]. It has computational complexity $M\log
M\,2^{\mathop{{O}{}}(\log^{*}M)}$, where we again denote the _iterated
logarithm_ by $\log^{*}M$. Fürer’s algorithm uses complex arithmetic. A
related algorithm of the same complexity but using modular arithmetic is due
to De, Kurur, Saha and Saptharishi [7].

### Power series operations

Let us also summarize the complexity of power series computations; for
references see the books of Cormen, Leiserson, Rivest and Stein [6] or Knuth
[25]. The multiplication can, again, be speeded up by using fast Fourier
transform. We can use the algorithms for integer multiplication presented
above; see von zur Gathen and Gerhard [31]. Also, the computational complexity
can be improved: Given power series with precision $N$ (i.e., the first $N$
terms) over a ring, we can perform multiplication with $N\log
N\,2^{\mathop{{O}{}}(\log^{*}N)}$ ring operations using Fürer’s algorithm.

In order to perform division (inversion) of power series with precision $N$,
we can use the Newton–Raphson-method. We need at most $4\mathop{{#1}{}}(N)+N$
ring operations, where $\mathop{{#1}{}}(N)$ denotes the number of operations
needed to multiply two power series with precision $N$; see von zur Gathen and
Gerhard [31, Theorem 9.4] for details; the additional summand
$\mathop{{#1}{}}(N)$ in comparison to that theorem comes from the
multiplication with the numerator. Therefore, by using Fürer’s algorithm, we
can invert/divide with $N\log N\,2^{\mathop{{O}{}}(\log^{*}N)}$ ring
operations.

The bit size occuring in the ring operations for a division of power series
with precision $N$ and coefficients of bit size $M$ is $NM$ by the remarks
after [31, Theorem 9.6]. Therefore and by assuming $M=\mathop{{O}{}}(N)$ for
simpler expressions with respect to the logarithms, we end up with

$N\log N\,2^{\mathop{{O}{}}(\log^{*}N)}\cdot
NM\log\bigl{(}NM\bigr{)}2^{\mathop{{O}{}}(\log^{*}(NM))}=N^{2}M(\log
N)^{2}2^{\mathop{{O}{}}(\log^{*}N)}$

bit operations.

##  3\. Cost for extracting coefficients

Our main result gives the number of operations needed for extracting the
coefficients $\mathop{{#1}{}}(n)$ for all $n<N$. It reflects three different
aspects: First, we count operations on a high level, for example power series
multiplications. (Below we will denote this operation by $\mathbf{M}$.)
Second, we count operations in the ring of integers. There, to stick with the
example on power series multiplication, the precision of the power series is
taken into account, but not the actual size of the integer. Finally and third,
we count bit operations, where also the size of the coefficients (which are
integers) is taken into account.

Let us make this more precise and start with the high level operations. We
denote

  * •

an _addition_ (or a _subtraction_) of two power series by $\mathbf{A}$,

  * •

a _multiplication_ of two power series by $\mathbf{M}$, and

  * •

a _division_ of two power series by $\mathbf{D}$.

As we compute the first $N$ terms, we may assume that all power series are of
precision $N$.

An overview and summary of the number of ring operations and bit operations of
these high level operations is provided in Section 2. Clearly, we have to deal
with the size of the coefficients. We first note that for $n<N$ each
coefficient $\mathop{{#1}{}}(n)$ can be written with
$M\colonequals\lfloor\log_{2}\mathop{{#1}{}}(N)\rfloor+1$ bits and that by
using the asymptotics (1.1) we can bound this by
$N\log_{2}\rho+\mathop{{O}{}}(1)$ when $N$ tends to $\infty$. Here the
constant $\rho<2$ depends on $t$; see [8] for details on $\rho$.

Summarizing, all the operations $\mathbf{A}$, $\mathbf{M}$ and $\mathbf{D}$
are performed on power series of precision $N$ with coefficients written by
$M$ bits (numbers bounded by $2^{M}$), and the cost (number of bit operations)
are stated in Section 2. There is one important remark at this point, namely,
we will see during our main proof (Section 5) that the coefficients appearing
in power series additions and multiplications are actually much smaller than
coefficients written by $M$ bits; we will take this into account for counting
bit operations.

Beside these main power series operations, we additionally denote

  * •

_other power series operations_ of precision $N$ (for example, memory
allocation or writing initial values) by $\mathbf{S}$, and

  * •

_other operations_ , more precisely operations of numbers with less than
$\log_{2}N$ bits (for example additions of indices) by $\mathbf{O}$.

Thus, an operation $\mathbf{O}$ is performed on numbers bounded by $N$ only
(in contrast to the bounded-by-$2^{M}$-operations).

With these notions and by collecting operations as formal sums of
$\mathbf{A}$, $\mathbf{M}$, $\mathbf{D}$, $\mathbf{S}$ and $\mathbf{O}$, we
can write down the precise formulation of our main theorem.

######  Theorem 1.

Calculating the first $N$ terms of $\mathop{{#1}{}}(n)$ can be done with

$\mathbf{D}+\bigl{(}\log_{t}N+\mathop{{O}{}}(1)\bigr{)}\mathbf{M}+2\bigl{(}\log_{t}N+\mathop{{O}{}}(1)\bigr{)}\mathbf{A}+\mathop{{O}{}}(\log
N)\mathbf{S}+\mathop{{O}{}}(\log N)\mathbf{O}$ (3.1)

power series operations,

$N(\log N)^{2}\,2^{\mathop{{O}{}}(\log^{*}N)}$

operations in the ring of integers, and with

$N^{2}(\log N)^{4}\,2^{\mathop{{O}{}}(\log^{*}N)}$ (3.2)

bit operations.666See footnote 3 for a note on replacing the factors
$2^{\mathop{{O}{}}(\log^{*}N)}$ by $\mathop{{O}{}}(1)$.

In order to prove Theorem 1, we look at the cost of calculating the first $N$
terms, which is done by extracting coefficients of the power series

$H(q)=\frac{\sum_{j=0}^{\infty}q^{[j]}(-1)^{j}\prod_{i=1}^{j}\frac{q^{[i]}}{1-q^{[i]}}}{\sum_{j=0}^{\infty}(-1)^{j}\prod_{i=1}^{j}\frac{q^{[i]}}{1-q^{[i]}}}$
(3.3)

with

$[j]\colonequals 1+t+\dots+t^{j-1}.$ (3.4)

This generating function (3.3) can be found in Flajolet and Prodinger [10,
Theorem 2] for $t=2$ and in Elsholtz, Heuberger and Prodinger [8, Theorem 6]
for general $t$. It is derived from the equivalent formulation as counting
problem on trees, which was mentioned in the introduction.

##  4\. Auxiliary results

When extracting the first $N$ coefficients, we do not need the “full”
generating function, i.e., the infinite sums in the numerator and denominator
of (3.3) can be truncated to finite sums. The following lemma tells us how
many coefficients we need. We use this asymptotic result in our analysis of
the algorithm; for the actual computer programme, we can check indices and
exponents by a direct computation.

######  Lemma 4.1.

To calculate numerator and denominator of the generating function (3.3) with
precision $N$, we need only summands with

$j\leq J=\log_{t}N+\mathop{{O}{}}(1).$

###### Proof.

Because of an additional factor $q^{[j]}$ in each summand of the numerator, it
is sufficient that the largest index of the denominator is less than $N$.
Therefore, we will only look at the indices of the denominator.

Consider the summand of the denominator with index $j$. The lowest index of a
non-zero coefficient of the denominator is

$\sigma_{j}=\sum_{i=1}^{j}[i]=\frac{t^{j+1}-t}{(t-1)^{2}}-\frac{j}{t-1}=\frac{t^{j+1}}{(t-1)^{2}}\Bigl{(}1-\frac{j(t-1)}{t^{j+1}}-\frac{1}{t^{j}}\Bigr{)}$

where the notation $[i]$ is defined in Equation (3.4). We only need summands
with $\sigma_{j}<N$. Taking the logarithm yields

$j-1+\log_{t}\Bigl{(}1-\frac{j(t-1)}{t^{j+1}}-\frac{1}{t^{j}}\Bigr{)}-2\log_{t}\Bigl{(}1-\frac{1}{t}\Bigr{)}<\log_{t}N$

As the first logarithm tends to $0$ as $j\to\infty$ and the second is bounded,
the error term $\mathop{{O}{}}(1)$ is large enough and the result follows. ∎

While the bit size of the coefficients $\mathop{{#1}{}}(n)$ is linear in $N$,
the size of the coefficients of numerator and denominator of (3.3) is much
smaller. We make this precise by using the following lemma.

######  Lemma 4.2.

For $n\leq N$, the $n$th coefficient of

$\frac{1}{1-q^{[1]}}\frac{1}{1-q^{[2]}}\frac{1}{1-q^{[3]}}\cdots\frac{1}{1-q^{[j]}}$
(4.1)

with $j\leq J$ and $J$ of Lemma 4.1 as well as the $n$th coefficients of
numerator and denominator of (3.3) can be written with

$\frac{(\log N)^{2}}{2(\log 2)(\log t)}+\mathop{{O}{}}(\log N)$ (4.2)

bits.

###### Proof.

We start proving the claimed result for (4.1) and postpone handling numerator
and denominator of (3.3) to the end of this proof.

Each factor of (4.1) is a geometric series whose coefficients are either $0$
or $1$ and whose constant coefficient is $1$. In particular, these
coefficients are nonnegative. Therefore, it suffices to show the result for
$j=J$.

As the coefficients are either $0$ or $1$, the $n$th coefficient of the
product equals the cardinality of the set

$\bigg{\\{}(a_{1},a_{2},\dots,a_{J})\in\mathbb{N}_{0}^{J}\colon\mathopen{}\sum_{i=1}^{J}a_{i}[i]=n\bigg{\\}}.$

By using the crude estimate $a_{i}\leq n/[i]$, we see that we have at most
$2N/[i]$ choices for $a_{i}$ because $n<N$ and $[i]<N$ by construction. Thus
we can bound the cardinality of the set above by

$\frac{2^{J}N^{J}}{[1][2]\cdots[J]}\leq\frac{2^{J}N^{J}}{1\cdot t\cdot
t^{2}\cdots t^{J-1}}=\frac{2^{J}N^{J}}{t^{(J-1)J/2}}.$

We use $J=\log_{t}N+\mathop{{O}{}}(1)$ of Lemma 4.1 to obtain

$\displaystyle\frac{2^{J}N^{J}}{t^{(J-1)J/2}}$
$\displaystyle=\exp\Big{(}J(\log N)-J^{2}\frac{\log t}{2}+J\frac{\log
t}{2}+J(\log 2)\Big{)}$ $\displaystyle\leq\exp\Big{(}\frac{(\log N)^{2}}{\log
t}-\frac{(\log N)^{2}}{2\log t}+\mathop{{O}{}}(\log N)\Big{)}$

from which follows that the $n$th coefficient of (4.1) is bounded by

$\exp\Big{(}\frac{(\log N)^{2}}{2\log t}+\mathop{{O}{}}(\log N)\Big{)}.$ (4.3)

The result in terms of bit size follows by taking the logarithm.

Numerator and denominator are sums where $J$ summands are added up (or
subtracted). This corresponds to an additional factor $J$ in the bound (4.3)
or an additional summand $\log_{2}J$ in the formula (4.2), respectively. As
$J=\mathop{{O}{}}(\log_{t}N)$ by Lemma 4.1, this is absorbed by the error
term, so the same formula holds. ∎

##  5\. Proof of Theorem 1

We start with an overview of our strategy. For computing the first $N$
coefficients of the generating function $H(q)$ (see (3.3)), we only need the
summands of the numerator and the denominator with $j<J$ according to Lemma
4.1.

First, consider the denominator of $H(q)$. We compute the products

$\prod_{i=1}^{j}\frac{q^{[i]}}{1-q^{[i]}},$

iteratively by expanding the $J$ different terms $q^{[i]}/(1-q^{[i]})$ as
geometric series and perform power series multiplications. After each
multiplication, we accumulate the result by using one power series addition.

We deal with the numerator in the same fashion. However, by performing the
computation of numerator and denominator simultaneously, the above products
only need to be evaluated once.

Finally, to obtain the first $N$ coefficients of $H(q)$, we need one power
series division of numerator and denominator.

Pseudocode for our algorithm is given in Algorithm 1; an efficient
implementation using the FLINT library is presented in Appendix A. The actual
analysis of this algorithm is done by counting the operations needed, in
particular the power series operations, and providing bounds for the bit sizes
of the variables.

j = 0; hp_j = 0; sigma_j = 0; sign = 1 numerator = 1; denominator = 1;
coefficient_product = 1 while True: j += 1; hp_j = 1 + t*hp_j; sigma_j +=
hp_j; sign = -sign # hp_j=[j]; sigma_j = sum_{i=1}^j [j]; sign = (-1)^j if
sigma_j > N: break new_factor = 0 for i in range(hp_j, hp_j, N): new_factor[i]
= 1 # new_factor = q^[j]/(1-q^[j]) coefficient_product *= new_factor #
coefficient_product=prod_{i=1}^j q^[i]/(1-q^[i]) denominator += sign *
coefficient_product numerator += sign * coefficient_product.shifted(hp_j) #
numerator up to summand j; denominator up to summand j result = numerator /
denominator

Algorithm 1 Pseudocode

The above said, let us come to the actual proof.

###### Proof of Theorem 1.

We analyse the code of Algorithm 1; see Appendix A for the details. It starts
by initialising variables (memory allocation and initial values) for the power
series operations, which contributes $\mathop{{O}{}}(1)\mathbf{S}$. Further
initialisation is done by $\mathop{{O}{}}(1)\mathbf{O}$ operations.

For computing the first $N$ coefficients of $H(q)$ (see (3.3)), we only need
the summands of numerator and denominator with
$j<J=\log_{t}N+\mathop{{O}{}}(1)$ according to Lemma 4.1. Speaking in terms of
our computer programme, our outer loop needs $J$ passes. We now describe what
happens in each of these passes; the final cost needs then to be multiplied by
$J$.

Suppose we are in step $j$. After some update of auxiliary variables (needing
$\mathop{{O}{}}(1)\mathbf{O}$ operations), we compute the product

$\prod_{i=1}^{j}\frac{q^{[i]}}{1-q^{[i]}},$

out of the product with factors up to index $i=j-1$. Expanding
$q^{[j]}/(1-q^{[j]})$ as geometric series contributes at most $\mathbf{S}$ and
performing a power series multiplication contributes $\mathbf{M}$ and
additionally one swap $\mathop{{O}{}}(1)\mathbf{S}$. For obtaining the number
of bit operations, we need estimates of the coefficients appearing in the
multiplication. Lemma 4.2 bounds their value by

$\frac{(\log N)^{2}}{2(\log 2)(\log t)}+\mathop{{O}{}}(\log N)$ (5.1)

bits. Therefore each of our power series multiplications $\mathbf{M}$ needs

$N\log N\,2^{\mathop{{O}{}}(\log^{*}N)}\times(\log N)^{2}\log\log
N\,2^{\mathop{{O}{}}(\log^{*}N)}=N(\log N)^{3}\log\log
N\,2^{\mathop{{O}{}}(\log^{*}N)}$

bit operations by Fürer’s result [12, 13]; see also Section 2.

After each multiplication, we accumulate the results for numerator and
denominator by using one power series addition $\mathbf{A}$ for each of the
two. For the numerator, we additionally need $\mathop{{O}{}}(1)\mathbf{S}$
operations for the multiplication by $q^{[j]}$ performed by shifting.
Concerning bit operations, we use the bound of the coefficients for numerator
and denominator provided by Lemma 4.2. In terms of bit size, this leads to the
number of bits given in (5.1). Therefore a power series addition needs

$\mathop{{O}{}}\big{(}N\big{)}\mathop{{O}{}}\big{(}(\log
N)^{2}\big{)}=\mathop{{O}{}}\big{(}N(\log N)^{2}\big{)}$

bit operations.

In total, we end up with

$J\bigl{(}\mathbf{M}+2\mathbf{A}+\mathop{{O}{}}(1)\mathbf{S}+\mathop{{O}{}}(1)\mathbf{O}\bigr{)}$

operations to evaluate the outer loop; these operations translate to

$N(\log N)^{2}\,2^{\mathop{{O}{}}(\log^{*}N)}$

operations in the ring of integers and to

$N(\log N)^{4}\log\log N\,2^{\mathop{{O}{}}(\log^{*}N)}$

bit operations.

We are now ready to collect all costs for proving the first part of Theorem 1.
Additionally to the above, we divide the numerator by the denominator and need
one power series division $\mathbf{D}$. The clean-up accounts to
$\mathop{{O}{}}(1)\mathbf{S}$. This yields (3.1).

Using the Newton–Raphson-method and Fürer’s algorithm (see Section 2 and Table
2.1) a power series division $\mathbf{D}$ results in

$N\log N\,2^{\mathop{{O}{}}(\log^{*}N)}$

operations in the ring. Its operands777The actual bit size during the division
is $\frac{N(\log N)^{2}}{2(\log 2)(\log t)}+\mathop{{O}{}}(N\log N)$; see the
end of Section 2 for details. have bit size

$\frac{(\log N)^{2}}{2(\log 2)(\log t)}+\mathop{{O}{}}(\log N)$

which results in

$N^{2}(\log N)^{4}2^{\mathop{{O}{}}(\log^{*}N)}$

bit operations for our computations.

We note that the number of bit operations of a power series operation
$\mathbf{S}$ is linear in $N$ as the coefficients are bounded and that
$\mathbf{O}$ is an operation on numbers with $\mathop{{O}{}}(\log N)$ bits.
The error term includes all these. Collecting all bit operation results gives
the upper bound (3.2). ∎

##  6\. Remarks

In this last section, we provide some remarks related to the above proof and
coefficient extraction algorithm.

######  Remark 6.1.

In the proof above, we have seen that the cost (bit operations) of the power
series division is asymptotically roughly (not taking logarithms and smaller
factors into accout) a factor $N$ larger than the cost for computing numerator
and denominator, and all the overhead cost.

Moreover, only focusing on the computation of numerator and denominator, the
costs (again bit operations) for computing these two are asymptotically
dominated by power series multiplication, albeit only by roughly (again not
taking into account logarithmically smaller factors) a factor $\log N$
compared to addition and other power series operations.

Note that when only considering operations in the integer ring, then the
multiplications performed in the evaluation of numerator and denominator take
the asymptotically leading role by $N(\log
N)^{2}\,2^{\mathop{{O}{}}(\log^{*}N)}$ operations compared to $N(\log
N)\,2^{\mathop{{O}{}}(\log^{*}N)}$ ring operations of the power series
division.

At the end of this article we make a short remark on the memory requirements
for the presented coefficient extraction algorithm.

######  Remark 6.2.

Our algorithm needs $\mathop{{O}{}}(N)$ units of memory—a unit stands for the
memory requirements of storing a number bounded by $\rho^{N}$—plus the memory
needed for the power series multiplication and division.888We have been unable
to find a reference for the memory requirements of, for example, the
Schönhage–Strassen-algorithm. It seems that the _GNU Multiple Precision
Arithmetic Library (GMP)_ can do this with $12N$ units of memory; see [14] for
a comment of one of its authors. The above means that we can bound the memory
requirements by $\mathop{{O}{}}(N^{2})$ bits.

## References

  * [1] Allan Borodin and Ian Munro, _The computational complexity of algebraic and numeric problems_ , American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975, Elsevier Computer Science Library; Theory of Computation Series, No. 1.
  * [2] Jonathan M. Borwein, Peter B. Borwein, and David H. Bailey, _Ramanujan, modular equations, and approximations to pi, or how to compute one billion digits of pi_ , Amer. Math. Monthly 96 (1989), 201–219.
  * [3] E. Oran Brigham, _The Fast Fourier transform_ , Prentice-Hall, Englewood Cliffs, NJ, 1974.
  * [4] Stephen A. Cook, _On the minimum computation time of functions_ , Ph.D. thesis, Harvard University, 1966.
  * [5] James William Cooley and Tukey John Wilder, _An algorithm for the machine calculation of complex Fourier series_ , Math. Comput. 19 (1965), 297–301.
  * [6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, _Introduction to algorithms_ , second ed., The MIT Press, 2001.
  * [7] Anindya De, Piyush P. Kurur, Chandan Saha, and Ramprasad Saptharishi, _Fast integer multiplication using modular arithmetic_ , Symposium on Theory of Computation (STOC), 2008.
  * [8] Christian Elsholtz, Clemens Heuberger, and Helmut Prodinger, _The number of Huffman codes, compact trees, and sums of unit fractions_, IEEE Trans. Inf. Theory 59 (2013), 1065–1075.
  * [9] Shimon Even and Abraham Lempel, _Generation and enumeration of all solutions of the characteristic sum condition_ , Information and Control 21 (1972), 476–482.
  * [10] Philippe Flajolet and Helmut Prodinger, _Level number sequences for trees_, Discrete Math. 65 (1987), no. 2, 149–156.
  * [11] William B. Hart, Fredrik Johansson, and Sebastian Pancratz, _FLINT: Fast Library for Number Theory_ , 2015, Version 2.5.2, http://flintlib.org.
  * [12] Martin Fürer, _Faster integer multiplication_, STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, ACM, New York, 2007, pp. 57–66.
  * [13] by same author, _Faster integer multiplication_, SIAM J. Comput. 39 (2009), no. 3, 979–1005.
  * [14] Torbjörn Granlund, _Schönhage-Strassen_ , gmp-discuss mailing list, August 2010, http://gmplib.org/list-archives/gmp-discuss/2010-August/004277.html.
  * [15] William B. Hart, _Fast library for number theory: an introduction_ , Mathematical software—ICMS 2010, Lecture Notes in Comput. Sci., vol. 6327, Springer, Berlin, 2010, pp. 88–91.
  * [16] David Harvey and Joris Van Der Hoeven, _Integer multiplication in time $O(n\log n)$_, hal-02070778, 2019.
  * [17] Clemens Heuberger, Daniel Krenn, and Stephan Wagner, _Analysis of parameters of trees corresponding to Huffman codes and sums of unit fractions_, Proceedings of the Meeting on Analytic Algorithmics & Combinatorics (ANALCO), New Orleans, Louisiana, USA, January 6, 2013, SIAM, Philadelphia PA, 2013, pp. 33–42.
  * [18] by same author, _Canonical trees, compact prefix-free codes and sums of unit fractions: A probabilistic analysis_, SIAM J. Discrete Math. 29 (2015), no. 3, 1600–1653.
  * [19] Dean Hoffman, Peter Johnson, and Nadine Wilson, _Generating Huffman sequences_, J. Algorithms 54 (2005), no. 1, 115–121.
  * [20] Anatolii Alexeevitch Karatsuba, _The complexity of computations_ , Proceedings of the Steklov Institute of Mathematics, vol. 211, 1995, pp. 169–183.
  * [21] Anatolii Alexeevitch Karatsuba and Ofman Yuri Petrovich, _Multiplication of many-digital numbers by automatic computers_ , Proceedings of the USSR Academy of Sciences, vol. 145, 1962, pp. 293–294.
  * [22] by same author, _Multiplication of many-digital numbers by automatic computers_ , Doklady Physics 7 (1963), 595–596.
  * [23] Mohammadali Khosravifard, Morteza Esmaeili, Hossein Saidi, and T. Aaron Gulliver, _A tree based algorithm for generating all possible binary compact codes with $n$ codewords_, IEICE Trans. Fundamentals (2003), no. 10, 2510–2516.
  * [24] Martin Klazar, _What is an answer? \- remarks, results and problems on PIO formulas in combinatorial enumeration, part I_, arXiv:1808.08449 [math.CO].
  * [25] Donald E. Knuth, _Seminumerical algorithms_ , third ed., The Art of Computer Programming, vol. 2, Addison-Wesley, 1998.
  * [26] Hajar Narimani and Mohammadali Khosravifard, _The supertree of the compact codes_ , Proc. Int. Symposium on Telecommunications, 2008, pp. 649–655.
  * [27] Othmane Niyaoui and Oussama Mohamed Reda, _A new algorithm for generating all binary Huffman codes based on path-length extensions_ , International Journal of Applied Engineering Research 11 (2016), no. 21, 10618–10623.
  * [28] _The On-Line Encyclopedia of Integer Sequences_ , http://oeis.org, 2013.
  * [29] The SageMath Developers, _SageMath Mathematics Software (Version 8.3)_ , 2018, http://www.sagemath.org.
  * [30] Arnold Schönhage and Volker Strassen, _Schnelle Multiplikation großer Zahlen_ , Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292.
  * [31] Joachim von zur Gathen and Jürgen Gerhard, _Modern computer algebra_ , second ed., Cambridge University Press, 2003.

##  Appendix A Code

Below are the relevant lines of a programme written in C for computing the
coefficients $\mathop{{#1}{}}(n)$ with $n<N$. The code can be found at
https://gitlab.com/dakrenn/count-nonequivalent-compact-huffman-codes. The
programme uses FLINT [11, 15]. Note that we do not use aliasing of input and
output arguments in multiplication because providing our own auxiliary
polynomial brings tiny performance improvements.

fmpz_poly_init(result); fmpz_poly_init2(coefficient_product, N);
fmpz_poly_init2(coefficient_product_shifted, 2*N); fmpz_poly_init2(new_factor,
N); fmpz_poly_init2(numerator, N); fmpz_poly_init2(denominator, N);
fmpz_poly_init2(aux, N); fmpz_poly_set_ui(numerator, 1);
fmpz_poly_set_ui(denominator, 1); fmpz_poly_set_ui(coefficient_product, 1);
j=0; hp_j=0; sigma_j=0; sign=1; while(-1) { j++; hp_j=1+t*hp_j; sigma_j+=hp_j;
sign=-sign; /* hp_j=[j]; sigma_j=sum_{i=1}^j [j]; sign=(-1)^j */
if(sigma_j>=N) { break; } for(i=hp_j; i<N; i+=hp_j) {
fmpz_poly_set_coeff_ui(new_factor, i, 1); } /* new_factor = q^[j]/(1-q^[j]) */
fmpz_poly_mullow(aux, coefficient_product, new_factor, N);
fmpz_poly_swap(coefficient_product, aux); /* coefficient_product=prod_{i=1}^j
q^[i]/(1-q^[i]) */ for(i=hp_j; i<N; i+=hp_j) {
fmpz_poly_set_coeff_ui(new_factor, i, 0); } /* new_factor = 0 */ if(sign==1) {
fmpz_poly_add(denominator, denominator, coefficient_product);
if(hp_j+sigma_j<N) { fmpz_poly_set(coefficient_product_shifted,
coefficient_product); fmpz_poly_truncate(coefficient_product_shifted, N-hp_j);
fmpz_poly_shift_left(coefficient_product_shifted, coefficient_product_shifted,
hp_j); fmpz_poly_add(numerator, numerator, coefficient_product_shifted); } }
else { fmpz_poly_sub(denominator, denominator, coefficient_product);
if(hp_j+sigma_j<N) { fmpz_poly_set(coefficient_product_shifted,
coefficient_product); fmpz_poly_truncate(coefficient_product_shifted, N-hp_j);
fmpz_poly_shift_left(coefficient_product_shifted, coefficient_product_shifted,
hp_j); fmpz_poly_sub(numerator, numerator, coefficient_product_shifted); } }
/* numerator= up to summand j; denominator up to summand j */ }
fmpz_poly_clear(coefficient_product);
fmpz_poly_clear(coefficient_product_shifted); fmpz_poly_clear(new_factor);
fmpz_poly_clear(aux); fmpz_poly_div_series(result, numerator, denominator, N);
fmpz_poly_clear(numerator); fmpz_poly_clear(denominator);

Algorithm 2 C-code using FLINT

##  Appendix B Timing

The table below contains timings (in seconds) for computing the first $N$
coefficients with $t=2$.

$t$ | $N$ | $t_{\mathrm{n\&d}}$ | $t_{\mathrm{division}}$ | $t_{\mathrm{total}}$
---|---|---|---|---
2 | 256 | 0.000 | 0.001 | 0.001
2 | 512 | 0.001 | 0.005 | 0.006
2 | 1024 | 0.002 | 0.014 | 0.016
2 | 2048 | 0.005 | 0.045 | 0.050
2 | 4096 | 0.013 | 0.126 | 0.139
2 | 8192 | 0.029 | 0.562 | 0.591
2 | 16384 | 0.067 | 2.225 | 2.292
2 | 32768 | 0.251 | 10.709 | 10.960
2 | 65536 | 0.617 | 45.259 | 45.877
2 | 131072 | 1.189 | 198.995 | 200.184

Here, $t_{\mathrm{n\&d}}$ is the time for generating numerator and
denominator, $t_{\mathrm{division}}$ for the one power series division and
$t_{\mathrm{total}}=t_{\mathrm{n\&d}}+t_{\mathrm{division}}$.

The benchmark was executed on an Intel(R) Xeon(R) CPU E5-2630 v3 at 2.40GHz.
The limiting factor for our computations is the memory requirement; it is the
reason computing at most $N=2^{17}=131072$ coefficients.

The timings in the table and the theoretical result of this article fit
together; we can see the $\mathop{{O}{}}(N^{2+\varepsilon})$ running time of
the algorithm in our implementation.