1
$\begingroup$

The problem

I have a multiset $M=\{m_1, \dots, m_n\}$ of positive integers (that is, a number $m_i$ can appear multiple times in $M$), and a positive integer $k$.

I am looking for an algorithm to determine the greatest greatest common divisor (greatest gcd; "greatest greatest" is not a typo) of all sub-multisets that can be derived from $M$ by deleting $k$ elements. Formally,

$$ \text{gcd}_k(M) := \max_{\substack N\subset M \\ \#N=k} \text{gcd} (M\setminus N), $$

where $N$ is again a multiset.

What I've tried

  • The case $k=0$ is the "ordinary" $\text{gcd}$, which I'll assume we can calculate easily:

    $$ \text{gcd}_0(M) = \text{gcd}\big(\text{set}(M)\big), $$

    where $\text{set}(M)$ associates to a multiset $M$ its underlying set.

  • Without loss of generality, we can assume that the multiplicity of each entry in $M$ is greater than $k$, because any element of $M$ that occurs more than $k$ times will not be "active" in determining $\text{gcd}_k(M)$. Formally, if $M'\subset M$ consists of those elements of $M$ with multiplicity at most $k$ (with multiplicities, i.e., $M'$ is again a multiset), then

    $$ \text{gcd}_k (M) = \text{gcd}\Big(\big\{\text{gcd}_k(M')\} \cup \text{gcd}\big\{\text{set}(M\setminus M'\big)\}\Big). $$

  • We can calculate $\text{gcd}_k(M)$ recursively,

    $$ \text{gcd}_k(M) = \max_{m\in M} \text{gcd}_{k-1}\big(M\setminus\{m\}\big). $$

    This is what I am doing right now on a dataset, and which is running long enough for me to post this question. I'd prefer something quicker...

Environment

I don't have large numbers. $M$ won't contain much more than 100 numbers, counted with multiplicities, and $k$ won't exceed 10. However, I do need to do this quickly on thousands or even millions of different $M$s.

Why do I care?

I am working on time series that are "almost-multiples" of an underlying $\text{gcd}$, like this one:

time series

These are orders a retail store places at the wholesaler. The underlying multiple is a logistical unit, which I would like to infer from the orders, since it may not be available elsewhere in the system. What complicates matters, and motivates the "leave-$k$-out" aspect, is that sometimes orders are placed which are "not" multiples of this logistical unit.

Disregarding the time dimension for the moment, a table of the values here looks like this (I'll discard the zeros first thing):

$$ \begin{array}{|c|*{5}{c}|} \hline m_i & 0 & 240 & 432 & 552 & 864 \\ \hline \#m_i & 705 & 1 & 15 & 1 & 3 \\ \hline \end{array} $$

We can calculate $\text{gcd}_k(M)$ recursively as above and obtain:

$$ \begin{array}{|c|*{7}{c}|} \hline k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \text{gcd}_k(M) & 24 & 48 & 432 & 432 & 432 & 432 & 432 \\ \hline \end{array} $$

GCDs

$\endgroup$
0
$\begingroup$

Are you memoizing $\gcd_k$? Because with $|M| = 100$, $k=10$ that should finish rather quickly. Or alternatively, you can build up a dynamic programming table where $G[n][k]$ is $\gcd_k$ of the first $n$ numbers (with $G[0][k] = 0$ and by convention $\gcd(0, a) = a$). With a recurrence like this:

$$G[n][k] = \max\big(\gcd(G[n-1][k], a_n), G[n-1][k-1]\big)$$

Again, with $|M|\cdot k \approx 1000$ that ought to finish really quickly.

Addendum: to consider multiplicities, the $k-1$ (leaving out $a_n$) should be $k - m_n$ (leaving out all $m_n$ copies of $a_n$).

$\endgroup$
  • $\begingroup$ Sorry, it took me a while to read this in detail. Can you be more explicit about what you mean by "memoizing"? And I don't fully understand how a dynamic table would help me, given that $M$ is a multiset. $\endgroup$ – Stephan Kolassa Sep 23 '18 at 14:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.