1
$\begingroup$

Let $n, k \in \mathbb{N}$, with $k \le n$. Which $k$ natural numbers not greater than $n$ have the largest amount of divisors altogether?

Formally, let $D(x)$ be the set of positive divisors of some $x \in \mathbb{N}$. We want to find a subset $S \subseteq \{1, 2, \dots, n\}$ such that $|S| = k$ which maximizes $|\bigcup_{x \in S}{D(x)}|$. And what is the maximum cardinality achievable for $\bigcup_{x \in S}{D(x)}$?

The problem is straightforward for extremal values of $k$. For instance:

  • if $k = 1$, an optimal solution is the set containing the largest highly composite number not greater than $n$.
  • if $k = n$, then $\bigcup_{x \in S}{D(x)} = \{1, 2, \dots, n\}$.

What about for $1 < k < n$?

I would like to know how one should go about this type of construction. Can an exact solution be produced in general? Are there heuristics that (provably) approximate well such a solution? If not, is there any useful characterization of the cardinality of such a set using $\mathcal{O}(\cdot)$ notation?

Thank you!

$\endgroup$
2
  • $\begingroup$ If $2 k \ge n$, you can take $S = \{n-k+1 ,\ldots, n\}$ and get $\{1,2,\ldots,n\}$. And this is best possible, since if $x > n/2$ the only number from $1$ to $n$ with $x$ as a divisor is $x$ itself. $\endgroup$
    – Robert Israel
    Commented Oct 30, 2022 at 17:02
  • $\begingroup$ @RobertIsrael Yes, that is a good observation. Thank you! A consequence is that, if $2k < n$, we can always construct an optimal $S$ using only elements $> \lfloor n/2 \rfloor$. $\endgroup$
    – James Threshold
    Commented Oct 31, 2022 at 0:32

0

Reset to default

You must log in to answer this question.