Most "compact" sequence such that there is at least one prime between a(n) and a(n+1)

[Stefan Steinerberger]

> Thus a clarification; generating the sequence shouldn't
> require that we know which numbers are prime.

That's a bit vague, is it not? Let's define a(1) = 2 and
a(n+1) as the smallest number that can't be written
as the product of numbers in {1,2,3,...,a(n)} plus 1.
That way we should always get a prime in between
without knowing what primes are.

An almost number-theoretic free sequence could be defined
as such: Andrica's conjecture implies p_(n+1) - p_(n) < 2*sqrt(p_n) +1.
Assuming its truth and defining a(1) = 2 and
a(n+1)  = ceiling(a(n) + 2*sqrt(a(n)) + 1) should give such
a sequence. (Are there any nice proven bounds like that?)

Stefan