One particular limit $\lim_{k\to\infty} \frac{k}{p} = \infty$?

Question

Let's take a value of $2^k$ and $p\#$, such that $2^k < p\#$ (but for the lowest possible $p$).

As $p\#$ I understand primorial (product of the first $p$ primes).

We have:

k         p          k / p
64        16        4.000000
128       21        6.095238
256       34        7.529412
512       58        8.827586
1024      104       9.846154
2048      187       10.951872
4096      342       11.976608
8192      630       13.003175
16384     1169      14.015398
32768     2181      15.024301
65536     4090      16.023472
131072    7699      17.024549
262144    14543     18.025442

The first line means that:

$2^{64} < 16\#$

Can we prove that:

$$\lim_{k\to\infty} \frac{k}{p} = \infty$$

?

Answer 1

It boils down to the fact that $p_n/n \to \infty$, where $p_n$ is the $n^{\text{th}}$ prime. Let us define

$$g(n) = \prod_{m = 1}^n p_m$$

(you denoted that by $n\#$, but the more common use of that notation is different) and

$$h(k) = \min \{ n \in \mathbb{N} : g(n) > 2^k\}.$$

Then we have

$$\log g(n) = \sum_{m = 1}^n \log p_m = \vartheta(p_n)$$

with the first Chebyshev function $\vartheta$. The prime number theorem is $\vartheta(x) \sim x$. Since $\log$ is monotonically increasing, we have

$$g(n) > 2^k \iff \log g(n) > k\log 2,$$

so

$$p_{h(k)} \sim k\log 2.$$

Furthermore, $p_n \sim n\log n$ by the prime number theorem, which yields

$$h(k)\cdot \log h(k) \sim k\log 2$$

and therefore (using $\log h(k) \sim \log k$, which follows from the above)

$$\frac{k}{h(k)} \sim \frac{\log h(k)}{\log 2} \sim \frac{\log k}{\log 2}.\tag{$\ast$}$$

Since you used $k = 2^m$ in your programme, it's easy to compare the experimental results with the theory. It starts out with a large relative difference - $\frac{2^6}{h(2^6)} = 4$ instead of the $6$ predicted by the asymptotic equivalence $(\ast)$ - but gets better. For $k = 2^9$ we are already decently close - $8.83$ vs. $9$ - and for $k = 2^m$ with $m \geqslant 11$ the matches are already pretty good.