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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.