Bump, I think this deserves more attention.

Bump this...

The answer is YES. Below I will post the idea from zhengzw11, which as he comments, is routine in such constructions. The key idea is separating the two requirements for the sequence $\{ a_n \}$. Take $a_1 = 1, a_2 = 2, a_3 = 3$. Suppose we have chosen $a_1,a_2,\cdots,a_{2n-1}$ for some $n \geq 2$. Now take $a_{2n+1}$ to be the smallest natural number that has not appeared yet (this makes sure that every positive integer appears), then take $a_{2n}$ to be a natural number large enough (so it is different from $a_1,a_2,\cdots,a_{2n-1}$ and $a_{2n+1}$) and satisfying the required divisibility condition. More precisely, $a_{2n}$ need satisfy the following two divisibility condition: $$2n \mid \tau\left( 2na_{2n+1}^{2n} + (2n+1)a_{2n}^{2n+1} \right),$$$$(2n-1) \mid \tau\left( (2n-1)a_{2n}^{2n-1} + 2n a_{2n-1}^{2n} \right)$$ It is always possible to take such an $a_{2n}$. For example, take two distinct odd primes $p_n,q_n > \max(2n+1,a_{2n-1},a_{2n+1})$ such that $p_n \equiv 2 \pmod{2n+1}$ and $q_n \equiv 2 \pmod{2n-1}$ (by Dirichlet's theorem). Since the reduced residue system modulo an odd prime power $p^e$ is cyclic of order $p^{e-1}(p-1)$, and $p_n(p_n - 1)$ is coprime to $2n+1$, we find that when $x$ goes through a reduced residue system modulo $p_n^{2n}$, so does $(2n+1)x^{2n+1}$, so the congruence equation $$(2n+1)x^{2n+1} \equiv p_n^{2n-1} - 2na_{2n+1}^{2n} \pmod{p_n^{2n}}$$has solutions. Similarly the congruence equation $$(2n-1)x^{2n-1} \equiv q_n^{2n-2} - 2na_{2n-1}^{2n} \pmod{q_n^{2n-1}}$$has solutions. By Chinese remainder theorem, we can take $a_{2n} = x$ to be large enough and satisfy the above two congruence equations. Then the first congruence equation ensures that $v_{p_n}\left( 2na_{2n+1}^{2n} + (2n+1)a_{2n}^{2n+1} \right) = 2n-1$, so $$2n = \tau(p_{n}^{2n-1}) \mid \tau\left( 2na_{2n+1}^{2n} + (2n+1)a_{2n}^{2n+1} \right).$$Analogously, $v_{q_n}\left( (2n-1)a_{2n}^{2n-1} + 2n a_{2n-1}^{2n} \right) = 2n-2$ and $$2n-1 = \tau(q_{n}^{2n-2}) \mid \tau\left( (2n-1)a_{2n}^{2n-1} + 2n a_{2n-1}^{2n} \right)$$. We have inductively constructed a sequence $\{ a_n\}$ which clearly meets all requirements.

Solved with naman12 and solver1104 We claim that the answer is positive. Choose $a_1 = 1$. Suppose $a_1,\dots, a_{2n-1}$ have been constructed, let $a_{2n+1}$ be the smallest positive integer not yet included in the first $2n-1$ terms of the sequence. To show that we can choose $a_{2n}$ satisfying the problem conditions, it suffices to show that there exists $x \in \mathbb Z$ such that $2n-1 | \tau(x^{2n-1} + c_1)$ and $2n + 1 | \tau(a_{2n}^{2n+1} + c_2)$ are satisfied simultaneously for any positive rationals $c_1, c_2$. Choose primes $p_1,p_2$ (sufficiently large) that is $\equiv 2 \pmod{4n^2-1}$, then $p-1$ is relatively prime to $(2n-1)(2n+1) = 4n^2-1$, and by Dirichlet's theorem this is always possible. Since primitive roots exist for prime powers there exists $x \pmod {p_i^{2n-3+2i}}$ with $x \equiv c_i + p_i^{2n-4 + 2i} \pmod {p_i^{2n-3+2i}}$ for all $1\le i \le 2$, so we are done by CRT.

s