Yes, there exists. Let us partition the set of prime numbers into pairs of $(p_i,q_i)$, take $a_{2n+1}=p_{2n+1}q_{2n+1}\prod_{k=0}^{n-1} p_{2k+1} \prod_{k=1}^{n-1} q_{2k}$ and $a_{2n}=p_{2n}q_{2n}\prod_{k=0}^{n-2} q_{2k+1} \prod_{k=1}^{n-1} p_{2k}$, notice that any two non-consecutive terms have a prime divisor in common, while any consecutive don't have one.

Err.. with the same basic idea, we can make the above form a little less complicated. Construct $a_i$'s inductively. Take $2$ distinct primes not chosen at some previous step $p_{i,0}, p_{i,1}$ and let \[a_i = p_{i,0}p_{i,1} \prod_{j=1}^{i-2}p_{j,i\pmod{2}} \]Then, clearly, $a_i$ shares factors with all $a_j$'s $\forall$ $j \in [1,i-2]$. However, $p_i$ and $p_{i-1}$ are coprime because primes chosen in $a_i$ and $a_{i-1}$ have opposite pairity indices and are therefore distinct.

Yeah, I found this surprisingly easy for an RMM1: Enumerate the primes $p_1$, $q_1$, $p_2$, $q_2$, ... and define \[ a_{n} = p_nq_n \cdot \begin{cases} \prod_{k=1}^{n-2} p_k & n \text{ even} \\ \prod_{k=1}^{n-2} q_k & n \text{ odd}. \end{cases} \] The idea is that you just take every pair $i < j$ you want to not be relatively prime (meaning $\left\lvert i-j \right\rvert \ge 2$) and throw in a prime. You can't do this by using a different prime for every pair (since each $a_i$ must be finite) and you can't use the same prime for a fixed $i$, so you do the next best thing and alternate using even and odd and you're done. Hope to see actual number theory tomorrow

This is remarkably similar to USAMTS round 3 problem 4

Nice intuitive thinking: think of the darn a1. Oh hey it can't be a prime! How about a product of 2 primes, and just alternate stuff. Then just repeat and repeat. QED Could someone make a totally different construction as this?

When will the other problems of today's RMM be posted?

This looks pretty silly; can someone verify this please?

Oh yeah, that's another possible, but very similar construction. Do you know of a TOTALLY DIFFERENT construction? (obviously not just jumbling around the primes), or just multiplying a prime to everything... or is it possible to prove that all possible constructions will follow a similar form? Also, it is really really similar to usamts round 3 problem 4

La respuesta es sí. En efecto, sea $a_1=2 \times 3, a_2=5 \times 7$ y $a_3=2 \times 11$ y sea $a_4=3 \times 5 \times 13$. Luego, para $n \geq 4$, $a_n= \frac{a_{n-2}}{p_{n-2}} \times p_{n-3} \times q_n$, donde $p_i$ representa el mayor primo que aparece en $a_i$ ($i \geq 1$), y $q_i$ representa el menor primo que no divide a ninguno de los siguientes términos: $a_1, a_2, ... , a_{i-1}$, para $i \geq 2$, por ejemplo, $a_5=2 \times 7 \times 17$. Probaremos que esta secuencia funciona. Si demuestro que para cualquier $i \geq 5$, se cumple que $a_i$ y $a_{i-1}$ son coprimos, y $a_i$ con $a_j$ no son coprimos, para todo $1 \leq j \leq i-2$, ya quedaría listo. En efecto, probaremos que para $n \geq 5$, cumple, notemos que la base ya la construimos, pues los $5$ primeros términos ya satisfacen, luego supongamos que todos los términos $a_1, a_2, ... , a_{i-1}$ cumplen lo pedido, entonces como $a_i= \frac{a_{i-2}}{p_{i-2}} \times p_{i-3} \times q_n$. Notemos que $a_{i-1}$ es coprimo con $a_{i-2}$, con $p_{i-3}$, y con $q_i$. Por lo tanto, $a_i$ y $a_{i-1}$ son coprimos. Luego, es fácil ver que $a_i$ y $a_{i-3}$ no son coprimos, también vemos que como $p_{i-2}$ es el mayor de los primos en $a_{i-2}$, entonces no aparece atrás, y por tanto, $\frac{a_{i-2}}{p_{i-2}}$ no es coprimos con $a_j$, para$j \leq i-4$. Por lo tanto, $a_i$ no es coprimo con $a_j$, para todo $j \leq i-2$. Lo cual completa la inducción. Observación: $q_i$ tambíen es igual a $p_i$, solo que usé otro sentido en la fórmula para que se vea la construcción.

Quite similar to the other solutions, but does this work as well? Let $a_1=2$, and define the other $a_i$´s recursively: $a_n=p_{n}\cdot\prod_{i=1}^{n-2}a_i$ where $p_n$ denotes the nth prime.

Stens wrote: Quite similar to the other solutions, but does this work as well? Let $a_1=2$, and define the other $a_i$´s recursively: $a_n=p_{n}\cdot\prod_{i=1}^{n-2}a_i$ where $p_n$ denotes the nth prime. It won't work if $a_1$ is prime. since if $a_1$ is prime, $a_3$ and $a_4$ must have a common factor, $a_1$. Such that they cannot be coprime.

We will prove that for each $n$ there exist a sequence $a_1,a_2,\ldots,a_n,$ satisfying the condition in the promp by induction on $n.$ The base case is trivial. For the step let the statement be true for some $n.$ Now we will construct our new sequence with $n+1$ members as follows: Let $p_1,p_2,\ldots,p_{n-1}$ be distinct primes greater than $a_i$ for each $i=1,2,\ldots,n.$ The sequence with $n+1$ members is $a_1p_1, a_2p_2,\ldots,a_{n-1}p_{n-1},a_n,p_1p_2\cdots p_{n-1}.$ Now it is easy to notice, that $(a_kp_k,a_lp_l)=1$ iff $|k-l|=1$ for $k,l<n$ and $(a_n,p_i)=1$ for all $i.$ Therefore $(a_n,a_kp_k)=1$ iff $(a_n,a_k)=1$ iff $|n-k|=1$(By the induction hypothesis), we also have that $(a_n,p_1p_2\cdots p_{n-1})=1$ and for all $i\leq n-1$ $(p_1p_2\cdots p_{n-1}, a_ip_i)=p_i>1.$ Thus, the problem is solved.

The answer is yes. Let the primes be $p_1,p_2,p_3,\ldots$. Now, let $b_n$ be the product of the primes $p_{2k-1}$ where $k\equiv n\pmod{2}$ and $k\le n-2$ and $p_{2\ell}$ where $\ell\not\equiv n\pmod{2}$ and $\ell\le n-3$. Let $a_n=p_{2n}p_{2n-1}b_n$. It is easy to see that this works.

Yes. The following construction works: $a_1=p_1p_3, a_2=p_2p_4, a_3=p_1p_5, a_4=p_2p_3p_6$, and \[ a_n = \begin{cases} p_1(p_4p_6p_8p_{10} \cdots p_{n-3}p_{n-1})p_{n+2} \text{ for } n \text{ odd} \\ p_2(p_3p_5p_7p_9 \cdots p_{n-3}p_{n-1})p_{n+2} \text{ for } n \text{ even}. \end{cases}\]It is not hard to see that this works.

Here's a solution which I think is not new, but written in a different way. socrates wrote: Does there exist an infinite sequence of positive integers $a_1, a_2, a_3, . . .$ such that $a_m$ and $a_n$ are coprime if and only if $|m - n| = 1$? The answer is yes. By looking at the prime factors, we only need to find an infinite number of sets so that $S_i \cap S_J=\phi$ if and only if $|i-j|=1.$ Here's the construction: Let $p_i$ denote the $i$th prime. Consider the sets $A_1=\{p_1,p_2\},A_2=\{p_3,p_4\},\dots.$ Then, add alternating elements from previous sets, as shown: $$\begin{array}{c | c | c | c | c | c | c | c | c | c} A_i & \{2,3\} & \{5,7\} & \{11,13\} & \{17,19\} & \{23,29\} & \{31,37\} & \{41,43\} & \{47,53\} & \\ \text{From } A_1 & & & 2 & 3 & 2 & 3 & 2 & 3 & \\ \text{From } A_2 & & & & 5 & 7 & 5 & 7 & 5 & \\ \text{From } A_3 & & & & & 11 & 13 & 11 & 13 & \dots \\ \text{From } A_4 & & & & & & 17 & 19 & 17 & \\ \text{From } A_5 & & & & & & & 23 & 29 &\\ \text{From } A_6 & & & & & & & & 31 &\\ % & & & & \vdots & & & & &\\ \end{array}$$Then the sets $S_i$ to be $A_i$ $\cup$ the $i$th column works, for instance $S_1=\{2,3\}$ and $S_4=\{17,19,3,5\}.$ $\blacksquare$ Edit: Oh yeah, this is the same as v_Enhance's solution at #4. Oops.

The answer is yes. Let the prime numbers be $p_1,p_2,p_3,\dots$ since there are infinitely many of them. Let $a_1=p_1p_2$, $a_2=p_3p_4$, $a_3=p_1p_5$, and \begin{align*} a_{2n} &= p_2p_3p_5p_7\dots p_{2n-1}p_{2n+2}\\ a_{2n+1} &= p_1p_4p_6p_8\dots p_{2n}p_{2n+3}.\\ \end{align*}

Remark: Do RMM 1 when you can't do RMM 2. The answer is yes. Let the primes be $p_1 < q_1 < p_2 < q_2 < \ldots $ and suppose we let\[a_n = (p_nq_n)\cdot (p_1p_2\ldots p_{n-2})\]if $n$ is even and\[a_n = (p_nq_n) \cdot (q_1q_2\ldots q_{n-2})\]if $n$ is odd. It is easy to check that this works.

Very nice problem

The answer is yes. We will build our sequence so that it only contains square-free integers. Now lets do some notations: Consider $p_1,p_2,\ldots $ the prime numbers. For any $a_m=p_{b_1}p_{b_2}\ldots p_{b_k}$ with $b_1<b_2<\ldots <b_k$ denote $deg(a_m)=p_{b_k}$. For any $a_m=p_{b_1}p_{b_2}\ldots p_{b_k}$ with $b_1<b_2<\ldots <b_k$ denote $\overline{a_m}=\frac{p_1p_2\ldots p_{b_k}}{a_m}$. Build the sequence as following: $a_1=p_1p_2$ and $a_2=p_3p_4$ $a_n=\frac{\overline{a_{n-1}}}{deg(\overline{a_{n-1}})}\cdot p_{n+2}$ This construction satisfies the given condition, so we are done.

laikhanhhoang_3011 wrote:

I had the same idea at first but I don't think this works. In particular, if we pick, say, $p_1$ for $a_1$, and then down the line we are forced to pick $p_3$ for some $a_i$, then $a_1 \mid a_{n+1}$. Then $a_{n+2}$ should be coprime to $a_{n+1}$, but also not coprime with $a_1$, which is impossible.

Yes. Let the primes be $p_1,\ldots,$ in some order. Let $$a_n=p_{2n-1}p_{2n}\cdot \prod_{i=1}^{n-2} p_{2i-(n\%2)}$$where $n\%2=1$ if $n$ is odd and $0$ otherwise. It is easy to check that this works, since $\gcd(a_n,a_{n+1})=1$ and $\gcd(a_m,a_n)=p_{2m-(n\%2)}$ for $m\leq n-2$. $\blacksquare$

hmmm it feels like this should work essentially, if we have $a_1$ to $a_n$ chosen, we just need to pick suitable $a_{n+1}$, which essentially just means that the sets of primes $S_i$ dividing $a_i$ satisfy $S_1, S_2, \dots, S_{n-1}$ are not subsets of $S_n$. at this point we can just realize that if we selected $S_1$ to $S_{n-1}$ to contain really large arbitrary sets of primes (think of them as buffers) then this basically works, and we're done

Yes. Denote the primes by $p_1$, $p_2$, $\dots$. The construction is as follows Put $p_{2i}$ in $a_i$, $a_{i+2}$, $a_{i+4}$, $\dots$ where by putting it in we simply mean $p_{2i}$ divides these numbers Put $p_{2i+1}$ in $a_i$, $a_{i+3}$, $a_{i+5}, a_{i+7}, a_{i+9}, \dots$ To show that this works, we just notice the following Proving that consectutive terms are relatively prime is trivial by construction of the sequence. Proving that consecutive terms are not relatively prime is also easy. This is done as fixing a term $a_N$, all terms $a_k$ with $k$ and $N$ having the same parity clearly share a common factor, namely $2$ or $5$. Accesing the odd terms is also easy by the delay of some terms by $3$ indices instead of $2$. This completes the problem.

Yes there does. Order the set of prime numbers as $2 = p_1, p_2, \ldots,$. Let $(g_i)$ denote a sequence of ordered pairs, such that $g_i = (p_{2i-1}, p_{2i})$ for each positive integer $i$ (so $g_1 = (2,3), g_2 = (5,7)$, and so on). Define $a_1 = p_1 p_2 = 2\cdot 3$ and $a_2 = p_3 p_4 = 5\cdot 7$. For odd $n$, we let $a_n$ be the product of all the first elements in each of $g_1, g_2, \ldots, g_{n-2}$ multiplied by the product of both elements in $g_n$. For even $n$, we let $a_n$ be the product of all the second elements in each of $g_1, g_2, \ldots, g_{n-2}$ multiplied by the product of both elements in $g_n$. The first few numbers of this sequence we \[2\cdot 3, 5\cdot 7, 2\cdot 11\cdot 13, 3\cdot 7\cdot 17 \cdot 19, \ldots, 2\cdot 5\cdot 11\cdot 23\cdot 29\] If $m > n + 1$, then $g_n$ divides both $a_n$ and $a_m$, so they aren't relatively prime. If $m = n + 1$, then we can see the prime factors of $a_m$ and $a_n$ are disjoint ($m$ and $n$ have different parity). Therefore, $\gcd(a_m, a_n) = 1 \iff |m-n| = 1$.

My solution is same as (23)

Really easy just that it's annoying to write out like a decent proof. The answer is yes, and we construct such a sequence recursively as follows. First we let $\mathcal{P}={p_1,p_2,\dots}$ be the set of all prime numbers. Then, we define a sequence of sets $(S_i)$ which are subsets of $\mathcal{P}$ and let $a_i$ be the product of all the primes in $S_i$. In the first two rounds, let $S_1=\{p_1,p_2\}$ and $S_2=\{p_3,p_4\}$. Then, we add $p_1$ to all sets $S_i$ where $i \equiv 1 \pmod{2}$ and $p_2$ to all sets $S_j$ where $j\equiv 0 \pmod{2}$ for all $i\geq 3$. Next, in the third round we add $p_5$ and $p_6$ to $S_3$. Then, we add $p_3$ to all sets $S_i$ where $i \equiv 3 \pmod {2}$ ($i>3$) and $p_4$ to all sets $S_j$ where $j \not \equiv 3 \pmod{2}$ ($j>4$). Similarly, we keep continuing, where in the $k^{\text{th}}$ round we add $p_{2k-1}$ and $p_{2k}$ to $S_k$. Then, we add $p_{2k-1}$ to all sets $S_i$ where $i\equiv 2k-1 \pmod{2}$ ($i>2k-1$) and $p_{2k}$ to all sets $S_j$ where $j \not \equiv 2k-1 \pmod{2}$ ($j>2k$). To explicitly state the sets, \[S_i= \{p_1,p_4,p_5, \dots ,p_{2i-6},p_{2i-5},p_{2i-1},p_{2i}\} \text{ for all } i \equiv 1 \pmod{2} \text{ and } i>1\]and \[S_i = \{p_2,p_3,p_6,p_7, \dots ,p_{2i-6},p_{2i-5},p_{2i-1},p_{2i}\} \text{ for all } i \equiv 0 \pmod{2} \text{ and } i>2\] Now, it is immediately clear that $S_i$ and $S_j$ do not have any common factor for consecutive $i,j$ (since $i\not \equiv j \pmod{2}$, $p_r \nmid \gcd(a_i,a_j)$ for any $r < 2i-1$ and $p_{2i-1}$ and $p_{2i}$ don't divide $a_j$ since they are added only to sets $S_t$ where $t>i+1$ by the nature of our construction). For all $i,j$ where $j>i+1$, $S_i$ and $S_j$ must have one of $p_{2i-1}$ or $p_{2i}$ as a common factor depending on the parity of $j$. Thus, this construction must work and we are done.

Yes. Construction below. Define $S_n$ as a set of positive integers such that $a_n=\prod_{i\in S_n}p_i$ where $p_i$ represents the $i$th prime. Then, let $S_1=\{1,2\}$ and $S_2=\{3,4\}$. For $n>2$, let $S_n=\{2,4,\dots, n-2, n, n+1\}$ for even $n$ and let $S_n=\{1,3,\dots, n-4, n-2, n+3\}$ for odd $n$. This satisfies the assertion, as desired.

this is so abd to writeup Consider an infinite list of primes $p_i$, and split the primes into groups of $4$. Then for $n = 4i +1$, have $p_n$ divide $a_k$ if and only if $k$ is odd and at least $2i + 1$. For $n = 4i + 2$, have $p_n$ divide $a_k$ if and only if $k$ is even and at least $2i + 3$ or $k$ is $2i +1$. For $n = 4i + 3$, have $p_n$ divide $a_k$ if and only if $k$ is even and at least $2i + 2$. For $n = 4i + 4$, have $p_{n}$ divide $a_k$ if and only if $k$ is odd and at least $2i + 4$ or $k$ is $2i + 2$. For simplicity, call $p_{2i + 1}, p_{2i + 2}$ the associated primes of $a_{i + 1}$. Inspecting each individual prime makes it obvious that no two consecutive numbers share a prime divisor. We can also observe any two non consecutive numbers share a prime divisor by considering the one that comes first in the sequence, clearly every number after its successor divides one of its associated primes (in alternating fashion), so we are done.

The answer is yes. The construction is a tad bit underwhelming. Let $p_1 < p_2 < p_3 < \cdots$ be the primes in increasing order. Then for term $a_i$ of the sequence, we let primes $p_{2i-1}$ and $p_{2i}$ divide $a_i$ immediately; for each $j < i - 1$, $p_{2j-1}$ divides $a_i$ if $i \equiv j \pmod 2$, and $p_{2j}$ divides $a_i$ otherwise. To check that this sequence works, notice that: for any $k \leq n-2$, one of $p_{2k-1}$ and $p_{2k}$ divides both $a_k$ and $a_n$ by construction; neither of $p_{2n-3}$ and $p_{2n-2}$ divide $a_n$, and for each $k \leq n-3$, if $p_{2k-1}$ divides $a_{n-1}$ and not $p_{2k}$, then $p_{2k}$ divides $a_n$ and not $p_{2k-1}$, and vice versa. So $\gcd(a_k, a_n) > 1$ when $k \leq n-2$ and $\gcd(a_{n-1}, a_n) = 1$. This is all we need to prove.