# 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: 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}$$ 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[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$).
• 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. – Stephan Kolassa Sep 23 '18 at 14:20