Average value of a least common divisor Cayley table

A closed form expression is hopeless, but somewhat useful estimates can be obtained. Since $\DeclareMathOperator{\LCD}{LCD} \LCD(i,j)$ is the smallest prime dividing both $i$ and $j$ if $\gcd(i,j) > 1$ and $0$ otherwise, we can upper bound the sum of the $n^{\text{th}}$ (last) row/column by \begin{equation} \sum_{i = 1}^{n} \LCD(i,n) \leqslant \sum_{p \mid n} p\cdot \frac{n}{p} = n\cdot \omega(n)\,. \end{equation} Clearly the entries in the last row/column are the primes dividing $n$, and each occurs at most $\frac{n}{p}$ times, since there are just that many multiples of $p$ not exceeding $n$. If $n$ has at least two distinct prime divisors the inequality is strict, otherwise equality holds. Thus \begin{align} \sum_{i = 1}^{n} \sum_{j = 1}^{n} \LCD(i,j) &\leqslant 2 \sum_{k = 1}^{n} k\omega(k) \\ &= 2 \sum_{k = 1}^{n} \sum_{p \mid k} k \\ &= 2\sum_{p \leqslant n} \sum_{d \leqslant n/p} dp \\ &= \sum_{p\leqslant n} p\biggl(\biggl\lfloor \frac{n}{p}\biggr\rfloor^{2} + \biggl\lfloor \frac{n}{p}\biggr\rfloor\biggr) \\ &= \sum_{p \leqslant n} \Bigl(\frac{n^{2}}{p} + O(n)\Bigr) \\ &= n^{2}(\log \log n + M) + O(n^{2}/\log n)\,, \end{align} where $M$ is the Meissel–Mertens constant. So $\operatorname{DIV}(k)$ grows at least as fast as $e^{e^{k - M + o(1)}}$.

Another way of estimating $L(n)$ is to not find by how much adding a new row and column increase the sum of entries of $T_{n}$, but directly looking how often each prime appears in $T_{n}$. Clearly, $\LCD(i,j) = 2$ if and only if both are even, so $2$ occurs $\bigl\lfloor \frac{n}{2}\bigr\rfloor^{2} = \frac{n^{2}}{4} + O(n)$ times. And $\LCD(i,j) = 3$ if both are multiples of $3$ and at least one is odd. There are \begin{equation} \biggl\lfloor \frac{n}{3}\biggr\rfloor^{2} - \biggl\lfloor \frac{n}{6}\biggr\rfloor^{2} = \frac{n^{2}}{9}\cdot \biggl(1 - \frac{1}{2^2}\biggr) + O(n) \end{equation} such pairs. Similarly, $5$ occurs \begin{equation} \biggl\lfloor \frac{n}{5}\biggr\rfloor^{2} - \biggl\lfloor \frac{n}{10}\biggr\rfloor^{2} - \biggl\lfloor \frac{n}{15}\biggr\rfloor^{2} + \biggl\lfloor \frac{n}{30}\biggr\rfloor^{2} \end{equation} times. From the number of pairs of multiples of $5$, we subtract the number of pairs where both members are also multiples of $2$ or $3$ respectively, and since we have subtracted the number of pairs where both members are multiples of $2,3$ and $5$ twice, we re-add that number.

Generally, for a prime $p$, let $F(p)$ denote the product of all primes strictly less than $p$. The inclusion–exclusion formula says that $p$ occurs \begin{equation} \sum_{d \mid F(p)} \biggl\lfloor \frac{n}{pd}\biggr\rfloor^{2} = \sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \biggl\lfloor \frac{n}{pd}\biggr\rfloor^{2} \end{equation} times in $T_{n}$. The size restriction in the second form is needed to avoid combinatorial explosion in the expansion $\lfloor x\rfloor^{2} = x^{2} - 2x\lbrace x\rbrace + \lbrace x\rbrace^{2}$. Thus the number of times $p$ occurs is \begin{equation} \sum_{\substack{d \mid F(p) \\ d \leqslant n/p}}\mu(d) \Biggl(\frac{n^{2}}{p^{2}d^{2}} + O\biggl(\frac{n}{pd}\biggr) + O(1)\Biggr) = \frac{n^{2}}{p^{2}} \sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \frac{\mu(d)}{d^{2}} + \frac{n}{p} O\Biggl(\sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \frac{1}{d}\Biggr) + O\biggl(\frac{n}{p}\biggr)\,, \end{equation} where the $O$-constants can be taken as $2$ and $1$ respectively (in particular, completely independent from $p$ and $n$). Now, \begin{equation} \sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \frac{1}{d} \leqslant \prod_{q < p} \biggl(1 + \frac{1}{q}\biggr) \sim \frac{6e^{\gamma}}{\pi^{2}} \log p \end{equation} by Mertens' (third) theorem. Hence \begin{align} \frac{1}{n^{2}}\sum_{i = 1}^{n} \sum_{j = 1}^{n} \LCD(i,j) &= \sum_{p \leqslant n} \Biggl( \frac{1}{p}\sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \frac{\mu(d)}{d^{2}} + \frac{1}{n}O(\log p) + \frac{1}{n}O(1)\Biggr) \\ &= \sum_{p \leqslant n} \frac{1}{p} \sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \frac{\mu(d)}{d^{2}} + O(1) + O(1/\log n)\,. \end{align} It would be nice to show that the $O(1)$ is in fact $o(1)$, but since the inner sum is not very nice, that doesn't matter too much. It is easy to see \begin{equation} 2 - \frac{\pi^{2}}{6} < \sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \frac{\mu(d)}{d^{2}} < \frac{\pi^{2}}{6}\,, \tag{$\ast$} \end{equation} hence $L(n) \asymp \log \log n$, and $\operatorname{DIV}(k)$ grows at most as fast as $e^{e^{ck + O(1)}}$, where $c = \frac{6}{12 - \pi^{2}}$. That's not really satisfactory, though. Fortunately, it is not hard to improve on $(\ast)$. Since $\frac{1}{2^{2}} + \frac{1}{3^{2}} > \sum_{m = 4}^{\infty} \frac{1}{m^{2}}$, the upper bound can be reduced to $1$. Because the inner sum is indeed $1$ for $p > n/2$, that bound is sharp. An explicit good lower bound — which is what we're really after — is unfortunately not so easy to find. But for $p \leqslant \sqrt{n}$ all squarefree numbers less than $p$ occur in the sum, so then \begin{equation} \frac{6}{\pi^{2}} - \frac{1}{p-1} < \sum_{\substack{d \mid F(p) \\ d \leqslant n/p}} \frac{\mu(d)}{d^{2}} \leqslant \frac{6}{\pi^{2}} + \frac{1}{p-1} \end{equation} and hence for large $n$ there are many primes for which the inner sum is close to $\frac{6}{\pi^{2}}$. In fact, since \begin{equation} \sum_{\sqrt{n} < p \leqslant n} \frac{1}{p} = \log \log n - \log \log \sqrt{n} + O(1/\log n) = \log 2 + O(1/\log n) \end{equation} and \begin{equation} \sum_{p \leqslant \log n} \frac{1}{p} \sim \log \log \log n \end{equation} we can conclude \begin{equation} \frac{1}{n^2}\sum_{i = 1}^{n}\sum_{j = 1}^{n} \LCD(i,j) = \frac{6}{\pi^{2}}\log \log n + O(\log \log \log n)\,. \end{equation} And from that, \begin{equation} \operatorname{DIV}(k) = \exp\bigl(\exp(\pi^{2}/6\cdot k + O(\log k))\bigr) \end{equation} follows. Hence don't try to find $\operatorname{DIV}(4)$ exactly ;)