Condition on $n$ for no sequence to exist

Question

I've an integer $n\geq3$. What's the minimum possible value of $n$ so that no sequence $a_0,a_1,...,a_{n-1}$ exists where for all i:-

1. $1\leq a_i\leq10^9$ and all $a_i$s are distinct

2. gcd$(a_i,a_{(i+1)mod\ n})>1$

3. gcd$(a_i,a_{(i+1)mod\ n},a_{(i+2)mod\ n})=1$.

What I thought was that all I've to do is to find prime numbers, until $p_i*p_{i+1}>10^9$. Then, I can assign these consecutive products to my $a_i$s, that is, $a_i=p_i*p_{i+1}$ for $0\leq i\leq n-2$ and $a_{n-1}=p_{n-1}*p_0$ ($p_0=2$). However, I'm not getting the correct answer using this. Can someone please tell me what did I miss in these? Thanks:)

Answer 1

For instance, you could, after your cycle, write $p_2p_4$ then $p_4p_6$ then $p_6p_2$. There was a similar question asked yesterday (link : Sequence of N numbers ) for which my answer proves that for no sequence to exist, $n$ must be greater than $p(p-1)/2$, where $p$ is odd and there are at least $p$ prime numbers lower than $10^{4.5}$. (Meaning we have very crudely $n \geq 720,000$).

Edit: it turns out we can take $p=3401$, leading to $n \geq 5,781,700$.

Then again, this bound is not, and by far, the best one: I still could add $2*65537$ somewhere, for instance.