I don't think a nice asymptotic formula like the one you've mentioned from Tutte's work is available for higher $g$ to the best of my understanding; it is entirely possible that someone who regularly deals with such things will come along and show us otherwise.
Meanwhile, the state-of-the-art on counting triangulations of genus $g$ surfaces is the lovely paper "The KP hierarchy, branched covers, and triangulations" of Goulden and Jackson, available here: see Theorem 5.4. There are two obstacles in terms of going from this Theorem to a Tutte-type asymptotic formula:
- The Goulden-Jackson formula is presented in terms of the face count rather than the vertex count, and
- As is typical in the field, the formula relies on a recursively defined function $f(n,g)$ where (again) $n$ counts the faces rather than the vertices.
I think 1. is surmountable, but 2. might make things difficult: I have no idea how fast $f(n,g)$ grows, but I am sure various simplifications are possible if you set $g = cn$ in their formula.
It seems unlikely that one can prove anything nontrivial,
but it's still interesting to consider what ought to be true,
and to experimentally compute for small $k$.
Let
$$
\delta_k
= \min_{\ell_1<\ell_2} \left(\frac{n_{\ell_2}}{n_{\ell_1}} - 1\right)
= \min_{\ell} \left(\frac{n_{\ell+1}}{n_\ell} - 1\right),
$$
so we're asking how small $\delta_k$ can get.
An easy upper bound is $\delta_k \ll k \log k \, / \, 2^k$,
and one can probably save some power of $k$. The right answer
is probably $\delta_k \sim C^{-k + o(k)}$ for some constant $C>2$,
and it seems reasonable to guess that $C=3$. I'll explain this next,
followed by computational techniques that make it feasible to determine
$\delta_k$ at least for $k \leq 36$; for example
$$
\delta_{28} = \delta_{29} = \delta_{30} = \frac1{1079415718589} \doteq 3^{-25.22}
$$
(the numerator is
$13 \cdot 53 \cdot 59 \cdot 61 \cdot 67 \cdot 73 \cdot 89
= 2 \cdot 3 \cdot 5 \cdot 11 \cdot 17 \cdot 19 \cdot 31
\cdot 43 \cdot 71 \cdot 107 - 1$),
and
$$
\delta_{36} = \frac{145948}{123657879146878688901} \doteq 3^{-31.29}
$$
with
$$
1 + \delta_{36} = \frac
{7 \cdot 13 \cdot 19 \cdot 37 \cdot 41 \cdot 47 \cdot 73 \cdot 83 \cdot 89 \cdot 97 \cdot 127 \cdot 151}
{3 \cdot 17 \cdot 23 \cdot 43 \cdot 59 \cdot 61 \cdot 67 \cdot 71 \cdot 79 \cdot 101 \cdot 131 \cdot 137}.
$$
For the upper bounds: Note that $\delta_k$ is essentially
$\min_{\ell_1<\ell_2} (\log n_{\ell_2} - \log n_{\ell_1}).$
There are $2^k$ numbers $\log n_\ell$ between $\log n_1 = 0$ and
$\log n_{2^k} = \sum_{i=1}^k \log p_i \sim k \log k$;
so when we list them in order the average difference is
$\log n_{2^k} \, / \, (2^k - 1) \sim k \log k \, / \, 2^k$,
and so there must be some difference(s) no larger than that.
To save a power of $k$, note that the variance of the $2^k$ numbers
$\log n_\ell$ is $\frac14 \sum_{i=1}^k \log^2 p_i \sim (k/4) \log^2 k$,
and a positive fraction of them must be within say two standard deviations
of the mean, so we get an upper bound $\sim k^{1/2} \log k \, /\, 2^k$.
For the heuristics: If we had $2^k$ random numbers in an interval,
we'd expect the closest pair to be about $4^{-k}$ apart. But the
separations aren't independent; there are only $(3^k-1)/2$ different
ratios $n_{\ell_2} / n_{\ell_1}$ (namely the values of
$\prod_{i=1}^k p_i^{\alpha_i}$ with each $\alpha_i \in \{-1, 0, 1\}$
that make the product $>1$), so we expect the smallest one to have
logarithm about $3^{-k}$, again up to subexponential factors.
For small $k$ we can compute $\delta_k$ exactly by listing the $2^k$
factors of $\prod_{i=1}^k p_k$, sorting them, setting $\delta=2$,
comparing each $n_{\ell+1} / n_\ell$ with the current value of $\delta$,
and if $n_{\ell+1} / n_\ell$ is smaller then making it the new $\delta$.
This takes about $2^k$ space and $k 2^k$ time.
We can reduce each factor $2^k$ to $3^{k/2}$ by splitting
$\{p_1,\ldots,p_k\}$ into two equal or nearly equal subsets $P_1,P_2$,
listing for $j=1,2$ all the $3^{P_j}$ rationals of the form
$\prod_{p \in P_j} p^{\alpha_p}$ with each $\alpha_p \in \{-1, 0, 1\}$,
merging and sorting the two lists, and minimizing over ratios between
consecutive elements of different lists. This increases the feasible
range by a factor of $\log_3 4 = 1.26\!+$, and is how I computed
$\delta_k$ for $k \leq 36$ (in a few hours running gp on
a computer on which I could allocatemem(2^37)).
We next tabulate, for each $k \leq 36$, the values of $\log_3 (1 / \delta_k)$
(which does seem reasonably close to $k$), followed by the
difference between the two $n_\ell$ with the ratio closest to $1$
and the values of those two $n_\ell$. When $\delta_k = \delta_{k-1}$
we use " marks instead of repeating a row.
1 | 0 1 2 1
2 | 0.631 1 3 2
3 | 1.465 1 6 5
4 | 2.402 1 15 14
5 | 2.771 1 22 21
6 | 3.954 1 78 77
7 | 5.981 1 715 714
8 | " " " "
9 | " " " "
10 | 7.030 1 2262 2261
11 | 8.559 1 12122 12121
12 | " " " "
13 | 10.491 1 101270 101269
14 | 10.765 7 958341 958334
15 | 13.277 1 2162095 2162094
16 | 13.385 9 21894574 21894565
17 | " " " "
18 | 14.237 269 1669770410 1669770141
19 | 15.039 296 4432525097 4432524801
20 | 16.459 95 6768250181 6768250086
21 | 17.492 1 221669903 221669902
22 | 17.989 479 183357752669 183357752190
23 | 20.727 1 7746395147 7746395146
24 | 20.899 241 2256564888159 2256564887918
25 | 22.260 31 1293752274846 1293752274815
26 | 22.260 31 1293752274846 1293752274815
27 | 23.709 8 1641739926263 1641739926255
28 | 25.220 1 1079415718590 1079415718589
29 | " " " "
30 | " " " "
31 | 28.015 3749 87225268563485259 87225268563481510
32 | 29.352 699715 70660131241710008586 70660131241709308871
33 | 30.221 208586 54759581443774708307 54759581443774499721
34 | " " " "
35 | 31.240 4 3216928369004441 3216928369004437
36 | 31.288 145948 123657879146878834849 123657879146878688901
This seems to agree with the computations of Gerhard Paseman up to $k=20$ (except for the error already noted in the final line). I couldn't find a sequence in OEIS that matches any of it.
One could push this computation further using the data structure
described in this paper
by D. J. Bernstein, which reduces the space requirement from
$3^{k/2}$ (or $2^k$) to the square root $3^{k/4}$ (or $2^{k/2}$)
without appreciably increasing the running time. I haven't tried
to implement this.
Finally, for yet larger $k$ one could probably still exhibit some
values of $n_{\ell+1} / n_{\ell}$ that are reasonably close to $1$
using algorithms such as LLL to find approximate
integer relations on $\{ \log p_i \mid 1 \leq i \leq k \}$
(though it would be harder to prove that one has found the minimal one).
I have not tried to do this either.
Best Answer
The primes $p \leq \sqrt{n}$ can be ignored as the number of them is $$\approx \sqrt{n} / \log (\sqrt{n} )= 2 \sqrt{n}/\log n = o (1) \cdot \sqrt { n/\log n}$$
For primes $p> \sqrt{n}$, the exponent of $p$ is simply $\lfloor n/p \rfloor$. So an equivalent problem is to count the number of $1 \leq k \leq \lfloor \sqrt{n} \rfloor$ such that the interval $ (n/(k+1), n/k]$ contains a prime.
When $k$ is small, these intervals are very long, and one can prove that all or almost all contain a prime. When $k$ is large, the intervals are very short, and one can prove that few of them contain two primes and then use the prime number theorem to count primes.
The tricky case is the critical range when $k \approx \sqrt{n / \log n}$, say $ \sqrt{n/\log n}/2 < k < 2 \sqrt{n/\log n}$. In this range, the expected proportion of intervals that contain a prime is strictly between $0$ and $1$. To get the exact constant, we would need to estimate this proportion precisely, which seems quite difficult. Doing this by the moment method would require understanding the expected number of primes in the interval, the expected number of pairs of primes, triples, etc. and I don't think we have asymptotics for anything but the expected number and maybe the pairs.
That said, the Cramér random model suggests that $c$ is exactly
$$\int_{0}^{\infty} \left(1 - e^{ - 2/ x^2} \right) dx = \sqrt{2\pi},$$
if I did the calculation right, with the integrand at $x$ being the probability to have a prime in the interval associated to $k = x \sqrt{n/\log n}$.