Upper bound on smallest prime $p$ needed to tell two numbers $\leq n$ apart modulo $p$ I'm going through this paper:
E. D. Demaine, S. Eisenstat, J. Shallit, and D. A. Wilson. Remarks on separating words. ArXiv e-prints, March 2011.
And on page 2, there is the following lemma:
Lemma 1. If $0 \leq i,j \leq n$ and $i \ne j$, then there is a prime $p \leq 4.4 \log{n}$ such
that $i \not\equiv j$ (mod $p$).
They don't show where the $4.4 \log{n}$ comes from and I'm not sure where to look for it. Best I could find is this, but it does not provide the solution.
Could someone point me in the correct direction?
 A: High Level Idea
Suppose that $j > i$. Let $k = 4.4 \log n$. Then we need to prove that there is a prime number $p < k$ that doesn't divide $j -i$. Assume to the contrary that this is not the case. Then all primes between $2$ and $k$ divide $j -i$. Since all of them are coprime, the product of all primes between $2$ and $k$ divides $j-i$. In particular, we get
$$\prod_{\substack{2\leq p \leq k\\p\text{ is prime}}}p \leq j -i \leq n.$$
The product in the LHS is sometimes called “primorial” (see http://en.wikipedia.org/wiki/Primorial ). It is known that it roughly equals $e^k$ and therefore is greater than $n$. We get a contradiction.
An Estimate for the Primorial
Let me informally explain why the primorial of $k$ is approximately $e^k$. The factorial of $k$ is approximately $e^{k\ln k}$. In the factorial we multiply all numbers between 1 and $k$, but in the primorial only primes. The density of primes is $1/\ln k$. Therefore, the primorial is approximately $\left(e^{k\ln k}\right)^{1/\ln k} = e^k$.
Numerical Bounds
Note that this proof implies that for large enough  $n$ there is a prime number as desired between $1$ and $(1+ o(1))\ln n$. However, for small $n$ the term $o(1)$ may be relatively large. I computed the value of the primorial numerically in PARI/GP for $k\in{2,\dots, 100000}$ and got that the primorial of $k$ is always at least $\exp(\frac{\ln 2}{2} k)$ (the equality is attained for $k=2$). If this is indeed true for all $k$, as my computation suggests, then there is a desired prime between $1$ and $2\, \log_2 n$.
