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} $$
