Neighboring non coprime

Let $n > 1$. A sequence $A_n$ of integers greater than 1 having length $n$ is called nice if any two elements are not coprime. That is, $$\gcd(A_i, A_{i+1}) > 1 \forall i, 1 \leq i \leq n-1$$

Find the smallest real number $t$ such that, given any sequence of integers $A_n$ of integers greater than 1 having length $n$, there exists a sequence of positive integers $B_n$ of length $n$ such that:

1. $\max{B_i} \leq n \max {A_i}$

2. $B_n$ differs from $A_n$ in at most $\lceil tn \rceil$ elements.

Solution

Note that for $t=1$ we can just change every single element to a small number like 2. We can try to do better. Satisfying condition 2 is easy, because for $t = 1/2$ we can just change every other element to the the LCM of it's neighboring elements, but this would make it failr condition 1. For example, suppose the sequence consists of very large primes, then this strategy would cause every other element to be the product of the two large primes, failing condition 1.

We propose that $t = 2/3$ satisfies the condition. That is, if $$A_n = a_1, a_2, a_3,a_4,a_5,a_6,\dots,a_n$$ $$B_n = 2a_2, a_2, 2a_2, 2a_5, a_5, 2a_5, \dots$$

We can see that every two neighboring elements are not coprime, and that the maximum of $B_i$ is at most twice that of $A_i$. We show that there is no smaller $t$ that can satisfy, using a series of counter examples.

For $n=3$, consider the sequence $p_1,p_2,p_3$ of very large primes. There is no way to only change one element to be nice, while keeping the maximum element manageable. The only way to change one element to be nice is to change $p_2 \to p_1p_3$, which then would fail condition 1. So we must change at least 2 elements, which means $\lceil 3t \rceil \geq 2$, so $t > \frac{1}{3}$

For $n=5$ consider the sequence $p_1,p_2,p_3,p_4,p_5$. If we were to change only 2 elements, either we change $p_2,p_4$, or we leave two neighboring primes intact. But if we change $p_2,p_4$, this could mean we have to change $p_2$ to LCM of $p_1,p_3$ and so on, violating condition 1. So we must change at least 3 elements, which means $\lceil 5t \rceil \geq 3$ so $t \frac{2}{5}$