<p>Given a set $S$, its multiplicative closure is the set
$$
\mathcal{M}(S) = \{s_1s_2\cdots s_k: k\in\mathbb{N},s_i\in S\}
$$
of products of zero or more elements of $S$. So the multiplicative closure of $\{2,3\}$ is the set of integers of the form $2^m3^n,$ for example.</p>

<p>I'm looking for an efficient algorithm to compute the number of elements of $\mathcal{M}(S)$ up to a given bound $x,$ given a finite set $S$ of positive integers. <strong>You may assume</strong> (it is true in my case, and simplifies the problem) that each element of $\mathcal{M}(S)$ has a unique factorization in $S$. In my case $S$ is small (150-250 elements) and $x$ is large ($10^{35}$ to $10^{50}$ or more).</p>

<p>A naive algorithm would construct all of the numbers and count them. This is slow, and more importantly consumes a lot of memory.</p>

<p>A better approach (dynamic programming) is to split the set roughly in half, let's say into $S_1$ and $S_2$, and construct the multiplicative closures of both. Then each element of $\mathcal{M}(S)$ is a product of an element of $\mathcal{M}(S_1)$ and an element of $\mathcal{M}(S_2)$, and by the special property no other product is equal to this value. So you can iterate through one of these, let's say $\mathcal{M}(S_1)$, and for each $m$ in that set the number of products which are at most $x$ is the number of elements in $\mathcal{M}(S_2)$ which are at most $x/m.$ This can be determined with a binary search.</p>

<p>Is there a way to push this method further? Is there a completely different approach which is more efficient? Is there literature I can read?</p>

CC BY-SA 3.0
2017-06-17T07:08:26.547Z
With your unique factorization assumption in place, this is equivalent to counting tuples $(e_1,\ldots,e_n)$ with $s_1^{e_1}\ldots s_n^{e_n}\le x$, where $S = \{s_1,\ldots,s_n\}$. Equivalently, $s_1 \log(e_1) + \ldots + s_n \log(e_n)\le \log(x)$, i.e. you are counting lattice points in a simplex.
Klaus Draeger
CC BY-SA 3.0
2017-06-17T07:27:54.343Z
($s_i, e_i$ obviously mixed up in that second constraint)
Klaus Draeger
CC BY-SA 3.0
2017-06-17T08:50:40.520Z
@KlausDraeger Yes, that is another way to phrase it.
Charles
CC BY-SA 3.0
2017-06-21T00:04:31.590Z
I suggest you search on counting lattice points in a simplex -- I think I remember seeing some algorithms for that on a different question on this site.  It's not just another way to phrase it -- you asked for a different approach that is more efficient, and I think that's what Klaus Draeger gave you.
D.W.
<ds.algorithms><reference-request><co.combinatorics><dynamic-programming>
Counting multiplicative closures
Charles
# Counting multiplicative closures

(Asked by: username_0 on 2017-06-16)

Given a set $S$, its multiplicative closure is the set
$$
\mathcal{M}(S) = \{s\_1s\_2\cdots s\_k: k\in\mathbb{N},s\_i\in S\}
$$
of products of zero or more elements of $S$. So the multiplicative closure of $\{2,3\}$ is the set of integers of the form $2^m3^n,$ for example.

I'm looking for an efficient algorithm to compute the number of elements of $\mathcal{M}(S)$ up to a given bound $x,$ given a finite set $S$ of positive integers. **You may assume** (it is true in my case, and simplifies the problem) that each element of $\mathcal{M}(S)$ has a unique factorization in $S$. In my case $S$ is small (150-250 elements) and $x$ is large ($10^{35}$ to $10^{50}$ or more).

A naive algorithm would construct all of the numbers and count them. This is slow, and more importantly consumes a lot of memory.

A better approach (dynamic programming) is to split the set roughly in half, let's say into $S\_1$ and $S\_2$, and construct the multiplicative closures of both. Then each element of $\mathcal{M}(S)$ is a product of an element of $\mathcal{M}(S\_1)$ and an element of $\mathcal{M}(S\_2)$, and by the special property no other product is equal to this value. So you can iterate through one of these, let's say $\mathcal{M}(S\_1)$, and for each $m$ in that set the number of products which are at most $x$ is the number of elements in $\mathcal{M}(S\_2)$ which are at most $x/m.$ This can be determined with a binary search.

Is there a way to push this method further? Is there a completely different approach which is more efficient? Is there literature I can read?

**Tags:** ds.algorithms, reference-request, co.combinatorics, dynamic-programming
> **Comments:**
> **username_1**: With your unique factorization assumption in place, this is equivalent to counting tuples $(e_1,\ldots,e_n)$ with $s_1^{e_1}\ldots s_n^{e_n}\le x$, where $S = \{s_1,\ldots,s_n\}$. Equivalently, $s_1 \log(e_1) + \ldots + s_n \log(e_n)\le \log(x)$, i.e. you are counting lattice points in a simplex.  
> **username_1**: ($s_i, e_i$ obviously mixed up in that second constraint)  
> **username_0**: @KlausDraeger Yes, that is another way to phrase it.  
> **username_2**: I suggest you search on counting lattice points in a simplex -- I think I remember seeing some algorithms for that on a different question on this site.  It's not just another way to phrase it -- you asked for a different approach that is more efficient, and I think that's what Klaus Draeger gave you.  

---

## 0 answers

