Primitive sequences with elements in every interval $[x, x + \sqrt x)$ We believe there is always a prime in the interval $[x,x+\sqrt{x})$, for $x$ sufficiently large, but proving this is inaccessible, even under RH.
What if we just wanted a sequence of integers free of multiples of previous elements? These sequences are called primitive.  Can we find a primitive sequence with this property?
Defining $a_1 = 6$ and then recursively defining $a_{n+1} = \max\{i: a_n<i<a_n+\sqrt{a_n}, \ a_j \nmid i, 1\leq j \leq n\}$, (if such an integer exists) we obtain a sequence
6,8,10,13,15,17,21,25,29,33,38,44,49,55,62,69,77,83,92,101,111,121,131,142,151,163,173,185,197,211,223,237,251,265,281,295,311,327,341,359,373,389,407,427,447,467,487,...
which appears to be infinite, and (although it doesn't look like it at first) far sparser than the primes.
Is there any hope of proving that it is infinite, or rather that there is some starting point that results in an infinite sequence?  (Note, this process terminates quickly if $a_1$ is chosen to be any smaller than 6.)  Could we do so with $\sqrt{x}$ replaced with smaller powers of $x$?
 A: One can obtain such a sequence after some finite starting point.  Let $k_0$ be large, and for each $k \geq k_0$ we can partition the interval $[2^k,2^{k+1})$ into about $100 \cdot 2^{k/2}$ disjoint intervals of length about $\frac{1}{100} \cdot 2^{k/2}$.  In each such interval $I$, use sieve theory to select a number $a_I$ of the form $a_I = p_k b_I$, where $p_k \sim k \log k$ is the $k^{th}$ prime and $b_I$ is some number with no prime factors less than $p_k$ (so in particular the smallest prime factor of $a_I$ is $p_k$).  It is then a simple case analysis to check that none of the $a_I$ can divide each other (note that no two distinct elements of $[2^k, 2^{k+1})$ can divide each other, whereas for $k < k'$ all the numbers chosen in $[2^k,2^{k+1})$ have the prime factor $p_k$ which is not present in any number chosen in $[2^{k'}, 2^{k'+1})$).
Probably with some computer assistance and some effective sieve theory one can in fact start the sequence at some quite small value such as $6$.
