Minimal Least Common Multiplier for $n$ distinct integers

Question

Let $n\in\mathbb N^+$ be a positive integer.

I am trying to find a set of $n$ distinct positive integers with minimal LCM.

• What is the set of $n$ distinct integers with minimal LCM?

• What is the asymptotics of this LCM as a function of $n$?

---

Observe that we can choose the set to be $\{1,...,n\}$, which would give a bound of $2^{O(n)}$. However, I'm not sure that this is tight.

For example, if $n=9$ then LCM$(\{1,2,3,4,5,6,7,8,9\})=2520$, but we have

LCM$(\{1,2,3,4,6,8,12,16,24\})=48$.

Answer 1

ADDED: see Nicolas on highly composite

Nicolas Full List

you can get a predictably small LCM by taking the first Superior Highly Composite Number with number of divisors at least your target number, you are calling that $n$

https://en.wikipedia.org/wiki/Superior_highly_composite_number

For your $7 \leq n \leq 12,$ you can get a small LCM by taking $n$ divisors of $60$

For your $13 \leq n \leq 16,$ you can get a small LCM by taking $n$ divisors of $120$

For your $17 \leq n \leq 24,$ you can get a small LCM by taking $n$ divisors of $360$

For your $25 \leq n \leq 48,$ you can get a small LCM by taking $n$ divisors of $2520$

Answer 2

HINT:

Given $n$ integers $$ a_{\,1} ,a_{\,2} , \cdots ,a_{\,n} $$ having the prime factorization $$ a_{\,k} = p_{\,1} ^{\,b_{\,1,\;k} } p_{\,2} ^{\,b_{\,2,\;k} } \; \cdots \;p_{\,q} ^{\,b_{\,q,\;k} } $$ then the factorization of their LCM will have exponents which are the "envelope" , i.e.the maximum of the exponents for each prime $$ \eqalign{ & LCM\left( {a_{\,1} ,a_{\,2} , \cdots ,a_{\,n} } \right) = p_{\,1} ^{\,\max \left( {b_{\,1,\;k} } \right)} p_{\,2} ^{\max \left( {\,b_{\,2,\;k} } \right)} \; \cdots \;p_{\,q} ^{\max \left( {\,b_{\,q,\;k} } \right)} = \cr & = 2^{\,l_{\,1} \,m_{\,1} + l_{\,2} \,m_{\,2} + \; \cdots + l_{\,q} \,m_{\,q} } \quad \left| \matrix{ \;l_{\,j} = \log _2 p_{\,j} \hfill \cr \;m_{\,j} = \max \left( {\,b_{\,j,\;k} \left| {\;1 \le k \le n} \right.} \right) \hfill \cr} \right. \cr} $$

Now, taking the integers to be consecutive powers of $2$ we have $$ \left( {2^{\,0} ,2^{\,1} , \cdots ,2^{\,n - 1} } \right)\quad \Rightarrow \quad \left\{ \matrix{ d = No.\,of\,digits = n \hfill \cr \log _2 LCM = n - 1 \hfill \cr} \right. $$ while adding a $3$ $$ \left( {\matrix{ {2^{\,0} ,} & {2^{\,1} ,} & { \cdots ,} & {2^{\,n - 1} ,} \cr {2^{\,0} 3,} & {2^{\,1} 3} & { \cdots ,} & {2^{\,n - 1} 3} \cr } } \right)\quad \Rightarrow \quad \left\{ \matrix{ d = No.\,of\,digits = 2n \hfill \cr \log _2 LCM = n - 1 + \log _2 3 \hfill \cr} \right. $$

That means that taking the products of the first q primes, with all the combinations of the exponents of each varying from $0$ to a given maximum $m_k$, we get $$ Comb.\left( {p_{\,1} ^{\,0, \cdots ,m_{\,1} } p_{\,2} ^{\,0, \cdots ,m_{\,2} } \; \cdots \;p_{\,q} ^{\,0, \cdots ,m_{\,q} } } \right)\quad \Rightarrow \quad \left\{ \matrix{ D = \log _2 No.\,of\,digits = \log _2 n = \sum\limits_k {\log _2 \left( {1 + m_{\,k} } \right)} \hfill \cr L = \log _2 LCM = \sum\limits_k {l_{\,k} \,m_{\,k} } \hfill \cr} \right. $$ and given $D$ to minimize $L$ (or v.v. given $L$ to maximize $D$), wrt the variables $m_k$.