Is this sequence unbounded?

---

Problem.
Suppose that a sequence $\{a_n\}_{(n\ge 1)}$ is a strict increasing sequence of positive integers such that $$\forall i,\phantom{;}j(i\neq j);\phantom{;}a_i \not\mid a_j$$ Prove that $a_{n+1}-a_{n}$ is unbounded.

---

I had tried various kinds of ways but I couldn't prove the problem; Instead of it, I proved the following result, which is weaker than the original problem;

---

Weaker result I proved.
Suppose that a sequence $\{a_n\}_{(n\ge 1)}$ is a strict increasing sequence of positive integers such that $$\forall i,\phantom{;}j(i\neq j);\phantom{;}\color{blue}{\gcd(a_i, a_j)=1}$$ Then $a_{n+1}-a_{n}$ is unbounded.

---

I used Chinese remainder theorem to prove this. (I'll post it if you want it.) I tried to apply similar method for the original problem, but I failed;

Do you have some ideas for the problem?

Solution 1:

Sequences of positive integers such that no element of the sequence is divisible by any other are called "primitive", and there has been a lot of work done figuring out how dense these sequences can be. An early result of Erdős is that all primitive sequences must have lower density $0$, which immediately implies that they must have arbitrarily large gaps. The proof is quite short and is given in "Note on sequences of integers no one of which is divisible by any other", J. London Math. Soc. 10 (1935), pp. 126-128. There is also a similar result in Felix Behrend, "On Sequences of Numbers not Divisible one by another", J. London Math. Soc. (1935) s1-10(1): 42-44 (paper is behind a pay wall.)

A later, more precise result by Erdős, Sárközy and Szemerédi ("On a theorem of Behrend", J. Australian Mathematical Society, 7 (1967), pp. 9-16) is that if $(a_1,a_2,\dots)$ is a primitive sequence, then $$ \sum_{a_i<x} \frac{1}{a_i}=o(\frac{\log x}{\sqrt{\log \log x}}), $$ and this is best possible in the sense that the fraction on the right-hand side cannot be divided by any $h(x)$ with $\lim_{x\to\infty} h(x)=\infty.$