1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Klaus Draeger Jun 17 '17 at 7:08
  • $\begingroup$ ($s_i, e_i$ obviously mixed up in that second constraint) $\endgroup$ – Klaus Draeger Jun 17 '17 at 7:27
  • $\begingroup$ @KlausDraeger Yes, that is another way to phrase it. $\endgroup$ – Charles Jun 17 '17 at 8:50
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Jun 21 '17 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.