Thanks @angiland for pointing out the mistakes. I'll try to fix it when I've time

ThE-dArK-lOrD wrote: 2. There exists two distinct prime numbers $q,r$ that $v_q(k)\geq 1009$ and $v_r(k)\geq 2$. This is more than necessary. As long as $v_q(k) \geq 1009$ and $q$ is odd, you can find a desirable sequence such that no term is a perfect square. Then each term has an even number of divisors. This suggests we do not need $v_r(k) \geq 2$.

I got a different set of $k$. Hope I didn't mess anything up. Please point out if I did. The answer is that $k$ must have a prime divisor $p$ with $\nu_p(k) \ge 1009$, and $k \neq 2^{1009}$. Say $k$ that satisfy the condition are ``good''. We begin with two simple observations: (i) multiples of good numbers are good, (ii) to show $k$ is bad it's enough to show each residue class modulo $k$ contains arbitrarily large non-interesting numbers. We begin by proving that all numbers of the form claimed earlier are good. Let $p$ and $q$ be odd primes: If $p > 2$, we claim $p^{1009}$ is good. Let $t$ be a quadratic non-residue modulo $p$. Consider the numbers $n \equiv tp^{1008} \pmod{p^{1009}}$. All of these numbers have $\nu_p(n) = 1008$. Moreover, $n$ is not a perfect square, since $\frac{n}{p^{1008}} \equiv t \pmod p$. Thus $d(n)$ is even and divisible by $\nu_p(n)+1=1009$, hence $n$ is interesting. We claim $2^{1009} q$ is good. Letting $t$ be a quadratic non-residue modulo $q$, the numbers $n \equiv t \cdot 2^{1008} \pmod{2^{1009}}$ are all interesting for the same reason. The number $2^{1010}$ is also good, by taking $n \equiv 3 \cdot 2^{1008} \pmod{2^{1010}}$ since no perfect square is $3 \pmod 4$. Combined with observation (i) earlier this resolves one direction. Next, we prove that: Claim: All numbers of the form $k = (p_1 p_2 \cdots)^{1008}$ are bad, for any primes $p_i$ (possibly including $2$). Proof. Consider a residue class $c \pmod k$. Note that we can find an element $a$ in this residue class modulo $k$ with $\nu_p(a) \neq 1008$ for all $p \mid k$. Indeed, this follows by Chinese remainder theorem: if $\nu_p(c) \ge 1008$ we require $p^{1009} \mid a$, else we require $a \equiv p^{\nu_p(c)} \pmod{p^{1009}}$, for each prime $p$. Now let $M = \prod_{p \mid k} p^{1009}$ and consider the residue class $a \pmod M$ (a subset of the arithmetic progression). By Dirichlet theorem, there exist arbitrarily large numbers of the form $n = q \gcd(a,M)$ in this sequence, where $q \nmid M$ is prime. Since $\nu_p(n) \in \{0, 1, 2, \dots, 1007, 1009\}$ for every prime $p$, the number $n$ is not interesting. $\blacksquare$ Finally, we show $2^{1009}$ is bad. Consider the residue class $a \pmod{2^{1009}}$. If $a \equiv 0$ then $2^{2018i-2}$ is uninteresting for all $i$. If $a \equiv 2^{1008}$ then $m^2 \cdot 2^{1008}$ is uninteresting for $m$ an odd integer. For any other $a$, we can find uninteresting numbers of the form $q\gcd(a,2^{1009})$, where $q$ is an odd prime, again by Dirichlet theorem. Thus $2^{1009}$ is bad.

I have the same idea as Evan Chen's.

v_Enhance wrote: [*]We claim $2^{1009} q$ is good. Letting $t$ be non-residue modulo $q$, the numbers $n \equiv tp^{1008} \pmod{p^{1009}}$ are all interesting for the same reason. There is a typo. And a little correction: $t$ has to be odd.

We claim that the only solutions are the positive integers $k$ with $v_{p}(k) \ge 1009$ for some prime $p$ and $k \neq 2^{1009}$. First, we claim that all such $k$ are solutions. Let $k = p^{1008} \cdot X$. Choose the arithmetic progression $p^{1008}(Xn + r)$, where $r$ is a quadratic non-residue modulo $X$ (which exists since $X > 2$). Note that $Xn + r$ is coprime to $p$ and also note that for every positive integer $n$, the number $Xn + r$ is never a perfect square because of the choice of $r$. Thus, $d(p^{1008}(Xn + r)) = d(p^{1008})d(Xn + r) = 1009d(Xn + r)$ is divisible by 2018 because $d(Xn + r)$ is always even (it's not a perfect square). Now, we claim that the rest aren't solutions. Let's rewrite the arithmetic progression as $C(Dx + E)$, where $\gcd(D, E) = 1$. By Dirichlet's Theorem, there exist infinitely many primes in the arithmetic progression $Dx + E$, so we can choose some $P > C$ and we have $2018 \mid d(CP) = 2d(C)$, or $1009 \mid d(C)$. Since $1009$ is a prime, there exist a prime $p$ such that $v_{p}(C) \ge 1008$. If $k = 2^{1009}$, then the arithmetic progression is either of the form $2^{1009}(x + C)$ or $2^{1008}(2x + O)$, where $O$ is some odd positive integer. In the first case, we can choose $x$ such that $x + C$ is a prime while for the second case we can choose $x$ so that $2x + O$ is a perfect square. In any case, the number of divisors of the chosen term will not be divisible by $2018$. Finally, suppose $k \neq 2^{1009}$ and $v_{p}(k) \le 1008$ for all $p$. Consider an arithmetic progression $C(Dx + E)$ with $CD = k$ and $\gcd(D, E) = 1$. Rewrite $C$ as $Y \cdot X^{1008}$, where $X$ is the product of all primes $p$ with $v_{p}(C) = 1008$ (note that we have proven above that $X > 1$). Note that $Y$ is coprime to $X$ and also $D$ is coprime to $X$ because $v_{p}(k) \le 1008$ for all $p$. Let $x = X^{2}q + r$, where $0 \le r < X^{2}$. Then, $Dx + E = DX^{2}q + (Dr + E)$. Since $D$ is coprime to $X$ (and thus $X^{2}$), we can choose $r$ such that $Dr + E \equiv X \pmod{X^{2}}$. We claim that there exist a $q$ such that the term $C(DX^{2}q + (Dr + E))$ is not interesting. Let $g = \gcd(DX^{2}, Dr + E)$. Since $\gcd(D, E) = 1$, $g = \gcd(X^{2}, Dr + E)$. Note that $g \neq X^{2}$ by our choice of $r$, thus $g \mid X^{2}$ and $g < X^{2}$. Choose $q$ such that $\frac{DX^{2}}{g}q + \frac{Dr + E}{g}$ is a prime larger than $Cg$ (which exists by Dirichlet's Theorem). Our term is thus $Z = Y \cdot X^{1008} \cdot g \cdot P$, for some prime $P > Cg$. We claim that $1009$ does not divide $d(Z)$. Clearly, $Z$ and $Y$ does not contribute anything to the divisibility of $d(Z)$ by $1009$, because $Z$ and $Y$ are both coprime to $Xg$ (recall that $g \mid X^{2}$) and their prime powers are all strictly less than $1008$. Write $g = Xg'$, where $X \nmid g'$. The number $X^{1008}g = X^{1009}g'$ cannot have number of divisors divisible by $1009$, because the prime power of each element in $g'$ is at most $2$ (because $X$ is squarefree and $g' \mid X^{2}$), and thus there is no prime $p$ with $1009 \mid v_{p}(X^{1009}g') + 1$, as desired.

Darn the details are WAYYYY trickier than I was envisioning. We'll replace $d(x)$ with $f(x)$. The answer is all $k$ which have $\nu_p(k)\ge 1009$ for some $p$, and $k\not=2^{1009}$. We first show that if $\nu_p(k)\le 1008$ for all primes $p$, then $k$ fails. Firstly, take a subset of the AP such that $\nu_p(k)=1008$ for all primes $p\mid k$, and say the primes are $p_1,\ldots,p_r$. Our AP consists of sufficiently large $n$ with $n\equiv a\pmod{k}$ for some fixed $a$. Let $d=\gcd(a,k)$. By Dirichlet, we can pick $n=dP$ for some very large prime $P$ (I think bigger than $d$ suffices). We then have $f(dP)=2f(d)$, so we must have $1009\mid f(d)$. Since $1009$ is prime, and $\nu_p(k)\le 1008$ for all $p=p_i$, we see that to get $1009\mid f(d)$, we must have $p^{1008}\mid d$ for some $p=p_i$. WLOG, suppose $p_1^{1008},\ldots,p_\ell^{1008}\mid d$ and no others. Letting $M=kp_1^2\cdots p_{\ell}^2$, pick $n\equiv ap_1\cdots p_{\ell}\pmod{M}$. It is not hard by CRT to see that this implies $n\equiv a \pmod{k}$, so this is a further subset of the AP. However, the way this is set up, we have that $\nu_{p_i}(n)=1009$ for $1\le i\le\ell$, and $\nu_{p_i}(n)\le 1007$ for $\ell+1\le i\le r$. Now,$\gcd(ap_1\cdots p_\ell,M)=p_1\cdots p_\ell d$, so again by Dirichlet, we can choose $n=ap_1\cdots p_\ell P$ for some really huge prime $P$. We now have that $f(n)$ has factors $2,3,\ldots,1008,1010$ by the observation about the $\nu_{p_i}$ so since $1009$ is prime, we cannot possibly have $1009\mid f(n)$. Therefore, we must have $\nu_p(k)\ge 1009$ for some prime $p$. Now pick $n\equiv p^{1008}a\pmod{k}$ where $a$ is a quadratic non-residue mod $k/p^{1008}$ and $\gcd(a,k)=1$, if it exists. Note that if $q>2$ is a prime factor of $k$, then it clearly exists as we can take a QNR mod $q$. Else, $k=2^{1009+j}$ for some $j\ge 0$. If $j\ge 1$, then we can pick $a=3$, as it is not a square mod $4$. So the only case left is $k=2^{1009}$, and we'll deal with this later. So unless $k=2^{1009}$, this $a$ exists. Therefore, $\nu_p(n)=1008$ and since $n$ can't be a square, $f(n)$ must be even. Thus, $1009,2\mid f(n)$, so $2018\mid f(n)$, as desired. Finally, let us dispose of the case $k=2^{1009}$. By the same Dirichlet argument, if $\gcd(a,k)<2^{1008}$, then we can pick $n=P\cdot 2^\ell$ for $\ell\le 1007$, and this clearly fails. Therefore, $a=2^{1008}$, so $n=2^{1008}(1+2y)$. We see that $1+2y$ is a square for arbitrarily large $y$, so $f(n)$ is odd, so $2018\nmid f(n)$. Therefore, this case fails, and the solution is complete. $\blacksquare$

Same idea with this problem! https://artofproblemsolving.com/community/u218439h548036p7592324

Solution found with dantaxyz. This problem is so finnicky ahhh We claim there exists an AP of only interesting numbers with common difference $k$ works iff $p^{1009} \mid k$ for $k\not = 2^{1009}$. Throughout the following solution, we let $a$ be the first term of the AP. First we show that we can construct an AP if $k=p^{1009}m$ for some $p\nmid m$, $p\not = 2$. Suppose $a=a'p^{1008}$. Then a general term in the AP is $a+\ell k = a'p^{1008} + p^{1009}\ell m = p^{1008}(a'+p\ell m)$, for $\ell \ge 1$. The number of factors of this expression is a mutiple of 2019 iff there is some odd exponent in the p.f. of $a'+p\ell m$, which happens iff $a'+p\ell m$ is not a square. We want $a'+pm\ell$ to not be a square for any $\ell \ge 1$, so choose some $a'$ such that $a'$ is an QNR mod $pm$. Then the sequence $\{a+\ell k\}_{\ell \ge 0}$ contains only interesting numbers. Now suppose there exists no $p$ such that $p^{1009} \mid k$. Then we claim that $k$ is not good. Let $k=p_1^{e_1}p_2^{e_2}\cdots p_j^{e_j}$, so $e_1,e_2,\ldots,e_j \le 1008$. Note that by Dirichlet, our AP contains infinitely many primes iff $\gcd(a,k)=1$. But it clearly cannot contain infinitely many primes, so $\gcd(a,k) > 1$. Let $\gcd(a,k)=g>1$. Then $\gcd(a/g,k/g)=1$, so there are infintely many primes in $\{\tfrac{a}{g} + \tfrac{k}{g}\ell\}_{\ell \ge 0}$ by Dirichlet. Take some prime $p$ such that $\gcd(p,g)=1$ in this sequence; then $a+k\ell = gp$, so $gp$ is in the original AP. So $2018\mid d(gp)=2d(g) \implies 1009\mid d(g)$. So $q^{1008} \mid g$ for some prime $q$. Thus, $q^{1008} \mid k$. There are two cases, 1) some other prime divides $k$, 2) no other prime except $q$ divides $k$. Case 1: Say $r\mid k, r\not=q$. So $rq^{1008} \mid k$. Then a general term is $q^{1008}(\tfrac{a}{q^{1008}} + \tfrac{k}{q^{1008}}n)$. But $\gcd(q,\tfrac{a}{q^{1008}} + \tfrac{k}{q^{1008}}n)$ will be greater than 1 for some $n$ unless $q\mid \tfrac{k}{q^{1008}}$, which is a contradiction since $q^{1009} \nmid k$ by assumption. Case 2: So suppose $q$ is the only prime dividing $k$. But since $q^{1009} \nmid k$, we must have $k=q^{1008}$. The terms in the AP are $a+q^{1008}\ell$ for $\ell \ge 0$. But $q^{1008} \mid a$, (since $q^{1008} \mid g = \gcd(a,k)$), So the terms in the AP are $yq^{1008}$ for all $y$ sufficiently large. Then take some prime $s$ such that $s^2q^{1008}$ is a term of the sequence. This must be interesting, so $2018 \mid 3\cdot 1009$, a contradiction! So $k$ is not good. If $k=2^{1009}m$ for some odd $m$, then we claim there exists no good AP. Suppose $\{a+2^{1009}m \ell\}_{\ell \ge 0}$ contains only interesting numbers for some $a$. This case is not too hard using the same Dirichlet idea we used before. EDIT: This is incorrect in particular the proof for case 1 is flawed. I'll try to fix this later by proving that $k=t^{1008}$ does not work for squarefree $t$.

I claim the answer is all $k$ that have a prime factor with $\nu_p\ge 1009$, except for $k=2^{1009}$. First I will show these work. Suppose $k=p^{1009}k_1$; then, let $a_1$ be a nonquadratic residue mod $pk_1$ (which is possible since $pk_1>2$). Next, set $a=p^{1008}a_1$. To see that this works, note $\nu_p(a+nk)=1008$ for all $n$, so $1009|\tau(a+nk)$. Also, $a+nk=p^{1008}(a_1+pk_1)$ cannot be a square due to our choice of $a_1$, so $2|\tau(a+nk)$; hence, $2018|\tau(a+nk)$, as desired. Next, suppose $k$ works, and I will prove that there exists $p$ such that $\nu_p(k)\ge 1009$. Let $\gcd(a, k)=d$, $a=dx, k=dy$, where $\gcd(x, y)=1$. Thus, the arithmetic progression is $dx, d(x+y), d(x+2y), ...$. By Dirichlet theorem we can choose $n$ such that $x+ny=q>d$ for prime $q$; then, $dq$ is interesting, meaning there exist $p|d$ such that $\nu_p(d)\equiv -1\pmod{1009}$. Now let $p_1, p_2, ..., p_j$ be all the prime factors of $d$ with $\nu_p(d)\equiv -1\pmod{1009}$; note that if for any $i$ we have $\nu_{p_i}(y)>0$ then we are done, so suppose FTSOC that $p_i\nmid y$ for all $i$. Let $M=p_1p_2...p_j$, and consider arbitary sufficiently large $z$. Then, note that for all $n$ where $n\equiv (M^z-x)y^{-1}\pmod{M^{z+1}}$, we'll have $x+yn\equiv M^z\pmod{M^{z+1}}$, so let $n_1, n_2, ...$ be the sequence of $n\ge 0$ which satisfy this. We see that $n_1, n_2, ...$ is an arithmetic progression with common difference $M^{z+1}$, meaning $x+yn_1, x+yn_2, ...$ is an arithmetic progression with common difference $yM^{z+1}$ and starting term $aM^{z+1}+M^z$ for some $a$. When we divide each term in this sequence by $M^z$ we get an arithmetic progression with starting term $aM+1$ and common difference $ym$. Note that $aM+1|x+yn_1$ and $\gcd(x+yn_1, y)=\gcd(x, y)=1$, so $\gcd(aM+1, y)=1$. Thus $\gcd(aM+1, yM)=1$, so by Dirichlet, there exist arbitrarily large primes in this arithmetic progression, meaning there exist $n$ such that $x+yn=qM^z$ for arbitrarily large prime $q$. Thus, for this particular $n$, we have $a+kn=dqM^z$, so for all $p\in \{p_1, ..., p_j\}$ we have $\nu_p(a+kn)=1+z$. But since $z$ is arbitrary we can let $1+z\ncong 0\pmod{1009}$, meaning that $a+kn$ is not interesting, which is a contradiction. Finally we show that $k=2^{1009}$ doesn't work. To see this, note that in this case we must have $d=2^{1008}$, so thus $a=2^{1008}a_1$ for odd some $a_1$, so thus $a+nk=2^{1008}(a_1+2n)$ for all $n$. But then we can set $n=\frac{m^2-a_1}{2}$ for some odd $m$, and $a+nk$ will not be interesting. Therefore, we are now done. $\blacksquare$

Stormersyle wrote:

Possibly my favorite solution, but just a little point; why must exists such $n\equiv (M^z-x)y^{-1}\mod M^{z+1} ? $

Al3jandro0000 wrote: Stormersyle wrote:

Possibly my favorite solution, but just a little point; why must exists such $n\equiv (M^z-x)y^{-1}\mod M^{z+1} ? $ Well, we assumed FTSOC that $p_i\nmid y$ for all $i$, meaning that $\gcd(y, M^{z+1})=1$, so $y^{-1}\mod{M^{z+1}}$ must exist. So clearly $(M^z-x)y^{-1}$ is a valid residue $\mod{M^{z+1}}$, and we can just set $x$ congruent to that

Can someone explain what (if anything) I am doing wrong when I prove the converse? I feel like I am oversimplifying things... With a hint from v_enhance: We claim that the answer is all $k$ such that $\nu_p(k)\ge 1009$ for some prime $p$ and $k\ne 2^{1009}.$ First, we show that all such $k$ satisfy the statement of the problem. Let $k=p_{1}^{e_{1}}p_{2}^{e_{2}}\dots p_{m}^{e_{m}},$ where $e_1\ge 1009,$ and let $j=k/(p_{1}^{1008}).$ Additionally, let $q$ be any non-quadratic residue modulo $j$ (such a residue is guaranteed to exist by the Chinese Remainder Theorem). We claim that all terms of the arithmetic sequence with starting term $p_{1}^{1008}q$ are interesting. Consider the $i$th term, which can be written as $$a_i=p_{1}^{1008}(q+ij).$$Since $q$ is not a quadratic residue modulo $j,$ we know $q+ij$ is not a perfect square, so it must have a prime factor $r$ such that $\nu_{r}(q+ij)$ is odd. Additionally, $q\not\equiv 0\pmod{p_{1}}$ and $j\equiv 0\pmod{p_{1}},$ so $\nu_{p_{1}}(a_{i})=1008.$ Therefore, $a_i$ is interesting, so we are done. It remains to show that if $k$ does not have a prime factor $p$ such that $\nu_p(k)\ge 1009,$ then no arithmetic sequence of interesting numbers with common difference $k$ exists. Suppose, for the sake of contradiction, that such an arithmetic sequence exists, and let the first term be $a.$ Then, by Dirichlet's Theorem, some term of the sequence is of the form $P\cdot\gcd(a,k),$ where $P$ is a prime larger than both $a$ and $k.$ Therefore, since all terms of the sequence are interesting, we must have $\nu_{p_{1}}(\gcd(a,k))=1008$ for some prime $p_1,$ so let $$a=p_{1}^{1008}\cdot m,$$$$k=p_{1}^{1008}\cdot n,$$where $\nu_{p_{1}}(n)=0.$ Then, the $i$th term of the arithmetic sequence can be expressed as $$p_{1}^{1008}(m+in).$$However, note that $\gcd(n,p_{1})=1,$ so we can always find some integer $r$ such that if $i\equiv r\pmod{p_{1}},$ then $m+in\equiv 0\pmod {p_{1}}.$ But clearly, we cannot have $m+in\equiv 0\pmod{p_{1}^{1008}}$ for all such $i.$ Hence, there must be another prime $p_2$ such that $m\equiv n\equiv 0\pmod{p_{2}^{1008}}.$ In this way, we can show that there are infinitely many primes $p$ such that $\nu_p(k)\ge 1008,$ which is impossible. Finally, we show that we cannot have $k=2^{1009}.$ Assume there exists an arithmetic sequence with all terms interesting, starting term $a,$ and common difference $2^{1009}.$ Then, by Dirichlet, there is some prime $P$ greater than $a$ and $2^{1009}$ such that $P\gcd(a,2^{1009})$ is a term of the sequence. Since this expression must be interesting, we must have $\gcd(a,2^{1009})=2^{1008},$ so $a=2^{1008}.$ But $$2^{1008}+4\cdot 2^{1009}=3^{2}2^{1008}$$is not interesting, so we are done.

The answer is any $k$ such that there exists a prime $p$ with $\nu_p (k) \geq 1009$, with the exception of $k=2^{1009}$ which doesn't work. First we show that this solution set works; in particular we will show $p^{1009}$ works for any odd prime $p$. Let $q$ be a quadratic nonresidue $\pmod{p}$; consider the arithmetic sequence $$p^{1008}(q), p^{1008}(q+p), p^{1008}(q+2p), \dots$$which has common difference $p^{1009}$. Every term $x$ in this sequence has $\nu_p (x)=1008$ and since $q+np$ is never a perfect square for any $n$, the number of factors of $x$ is always a multiple of $2018$ as desired. Now we just need to show $2^{1009} \cdot s$ is good for any integer $s>1$, which follows by taking a quadratic nonresidure $q \pmod{2s}$ and considering the arithmetic sequence $$2^{1008}(q), 2^{1008}(q+2s), 2^{1008}(q+4s), \dots$$. Now we show all other $k$ are bad; in particular we first show that if $k$ is good, then there must be some $p$ with $\nu_p(k) \geq 1009$. Assume for contradiction that for every prime $p$ we had $\nu_p(k) \leq 1008$, and let the sequence be $\ell+kn$ as $n$ ranges over the positive integers. Letting $\text{gcd}(\ell,k)=d, \frac{\ell}{d}=a, \frac{k}{d}=b$ the sequence becomes $d(a+bn)$. By Dirichlet since $\text{gcd}(a,b)=1$ we can find some $n$ such that $a+bn$ is a large prime; then there must be a prime $p$ such that $\nu_p(d)=1008$. Let $p_1, p_2, \dots , p_j$ be the primes such that $\nu_{p_i}(d)=1008$ and let $t=p_1p_2 \cdots p_j$; note that we must have $\text{gcd}(a,t)=1$ by our assumption. By the chinese remainder theorem we can find an arithmetic progression $x_1, x_2, \dots$ with common difference $t^2$ such that $ax_i+b \equiv t \pmod{t^2}$ for each $i$. If we let $ax_1+b=tm$ then the sequence $ax_i+b$ is $$tm, t(m+at), t(m+2at), \dots$$. Note that $\text{gcd}(m, t)=1$ and $\text{gcd}(m, a) = \text{gcd}(tm -ax_1, a) = \text{gcd}(b,a)=1$. Thus by Dirichlet there are infinitely many primes in the sequence $m, m+at, m+2at, \dots$, and thus we can pick some $i$ such that $ax_i+b=tQ$ for some large prime $Q$. Then $d(a+bx_i)=dtQ$, and there does not exist a prime $p$ such that $\nu_p(dtQ)=1008$, contradiction. It remains to take care of $k=2^{1009}$, assuming for contradiction there was a good arithmetic sequence. Let the sequence be $a+2^{1009}n$ as $n$ ranges over the positive integers. Letting $d=\text{gcd}(a,2^{1009}), \frac{a}{d}=x, \frac{2^{1009}}{d}=y$ the sequence becomes $d(x+yn)$. Since $\text{gcd}(x,y)=1$ by Dirichlet we can pick $n$ such that $x+yn$ is a prime; thus we must have $d=2^{1008}$. However, then we have $y=2$ so we can pick $n$ so that $x+yn$ is a perfect square. $d(x+yn)$ will then have an odd number of factors, contradiction as desired.

Remark: Jesus christ !@(#@!& this !@(#@!&ing problem. I can't even express through words how !@(#@!&ing much this problem has destroyed my mental state. Nobody should go through the pain of trying this !@(#@!&ing problem. My condolences go out to the Chinese students who in 2018 had to do this !@(#@!&ing problem in their TST exam. I claim that our answer is all $k$ with some prime $p \mid k$ satisfying $v_p(k) \geq 1009$ and $k \neq 2^{1009}$. Call a $k$ satisfying the problem statement $\textit{hot}$. For our constructions, we will use the clear fact that if $k$ is hot then all multiples of $k$ are also hot. Consider the following:\begin{itemize} \item Let $p$ be an odd prime. We provide a construction for $p^{1009}$ being hot. Consider all numbers of the form\[n \equiv kp^{1008} \pmod{p^{1009}}\]where $k$ is a non-QR modulo $p$. These numbers clearly form an arithmetic sequence with common term difference $p^{1009}$. Note that all of these $n$ cannot be perfect squares since $\frac{n}{p^{1008}} \equiv k \pmod p$ and $k$ is non-QR. Hence $d(n)$ for all of these $n$ is even. Furthermore, if we write\[n = kp^{1008} + rp^{1009} = p^{1008}(k + pr)\]for some nonnegative integer $r$, clearly $p \nmid pr + k$ hence $v_p(n) + 1 = 1009$ for all of these $n$. Thus $2018 \mid d(n)$ for all $n$ of above described form and thus all $p^{1009}$ for odd primes $p$ are hot. \newline \item Let $p$ be an odd prime. We provide a construction for $2^{1009}p$ being hot. Similar to above, take all $n$ of the form\[n \equiv k\times 2^{1008} \pmod{2^{1009}q}\]for some $k$ non-QR modulo $q$. For similar reasons to the previous point we see that $2018 \mid d(n)$ for all these $n$. \newline \item Lastly, we prove that $2^{1010}$ is hot. Indeed, taking all\[n \equiv 3 \times 2^{1008} \pmod{2^{1010}}\]suffices since squares are not $3$ modulo $4$ and the exponent of $2$ is clearly $1009$. \end{itemize} From these, we can multiply to get that all $k$ that we originally claimed were hot are indeed hot. Hence our constructions are complete. It remains to show that for the remaining $k$ there does not exist an arithmetic sequence with common term difference $k$ for which all terms are interesting. First we tackle $k$ such that for all primes $p \mid k$, $v_p(k) \leq 1008$. Let $(s + kn)$ where ${n : 1 \to \infty}$ be such a working arithmetic sequence. By Dirichlet on arithmetic sequences, if $s$ and $k$ are coprime, then some term in this sequence is prime, hence we let $\gcd(s, k) = t > 1$. Write $s = ts'$ and $k = tk'$. Then the arithmetic sequence can be written as $t(s' + k'n)$ for $n: 1 \to \infty$ except now that $s'$ and $k'$ are relatively prime. Hence again by Dirichlet on arithmetic series we may choose $n$ so that $s' + k'n$ is some very large prime $p$ relatively prime to $t$. We need $2018 \mid d(pt) \implies 1009 \mid d(t)$ and since $d(t) \mid d(k)$ we conclude that some prime $q$ satisfies $q^{1008} \mid k, t$. Let $S$ be the set of all primes $\{p_1, \ldots p_m\}$ such that $v_{p_i}(t) = 1008$. We go back to the sequence $t(s'+ k'n)$. Consider the number $G = p_1p_2\ldots p_m$. Clearly $\gcd(s', G) = 1$ and we can find an arithmetic sequence with difference $G^2$ satisfying $s'x + k' \equiv G \pmod{G^2}$ for all $x$ in that arithmetic sequence so every $s'x + k'$ can be written as $Gr$ for some positive integer $r$. The sequence becomes $Gr, G(r + aG), G(r + 2aG), \ldots$and so on. By Dirichlet again we may pick an $x$ so that the term becomes $tQ$ for large prime $Q$ and then no prime has $v_p$ of it $1008$, which is bad, a contradiction. We can use Dirichlet similarly to kill the case when $k = 2^{1009}$. I am too morally discouraged to write it out. Otherwise, we are done. $\blacksquare$

First, note that an integer $n$ is interesting iff $n=p^{1008}\cdot (non-square)$ I claim that $k$ works iff there is $p$ such that $v_p(k)\geq 1009$ and $k\neq 2^{1009}$. We first construct values for these. Case 1: $p$ is odd. let $q$ be some quadratic nonresidue mod $p$. Write $k=p^{1008}\cdot m$, and take the sequence \[\forall n, x_n= p^{1008} (q+nm)\]Verify that $x_n$ increments by k. Next, clearly $v_p(x_n)=1008$, and $x_n$ is never a square since $q+nm$ cannot be a square. Thus, $2018\mid d(x_n)$. $\square$ Case 2: $p=2$. Let $k=2^{1010}\cdot m$, then take the sequence \[\forall n, x_n = 2^{1008} (3+(4m)n)\]Verify that $x_{n+1}-x_n=k$. Next, we clearly have $v_2(x_n)=1008$, and $3+4mn$ cannot be a square, thus $2018\mid d(x_n)$ and we are done. Alternatively, if $k=2^{1009}\cdot p$, then we may take the sequence \[\forall n, x_n = 2^{1008} (q+(2p)n)\]which also works for some quadratic residue $q$ mod 2p. $\square$ We now show that these are the only solutions. AFTSOC otherwise, write $n=\prod p_i^{1008}$. WLOG we write the progression as $x_n=L(an+d)$ where $\gcd(a,d)=1$ and $k=aL$. Then, due to Dirichlet's, we may find an arbitrarily large $P$ such that $P=an+d, \gcd(p,L)=1$. Then, we have that \[2018\mid d(L\cdot P)\Longrightarrow 1009\mid d(L)\]Thus, if we take the $p$ as the most commonly occuring prime in $L$, then we have that $v_p(L)= 1008$. We now break down into two cases. Similar logic holds for all other $p$, thus $\forall p, v_p(L)\geq v_p(n)\Longrightarrow n\mid L$, so $a=1$. Thus, $x_n = k(n+d)$. At which point, we clearly fail when we choose $n$ such that $\forall p_i$, $v_{p_i}(n+d)=1009-e_i$. Thus, $d(x_n) = 1010^{\text{something}}$, so $x_n$ is not interesting, a contradiction. Finally, we verify $k=2^{1009}$, our sequence must be of the form \[2^i(a + n \cdot 2^{1009-i})\]We must have $i\geq 1008$, and $1009-i\leq 1$, however for both $2^0,2^1$, there are no non-quadratic residues so we will be able to find a square $a + n \cdot 2^{1009-i}$, a contradiction. Thus, we are done $\blacksquare$.

Remark: There are undoubtedly errors in my solutions. First, note that an integer $n$ is interesting iff $n=p^{1008}\cdot (non-square)$ I claim that $k$ works iff there is $p$ such that $v_p(k)\geq 1009$ and $k\neq 2^{1009}$. We first construct values for these. Case 1: $p$ is odd. let $q$ be some quadratic nonresidue mod $p$. Write $k=p^{1008}\cdot m$, and take the sequence \[\forall n, x_n= p^{1008} (q+nm)\]Verify that $x_n$ increments by k. Next, clearly $v_p(x_n)=1008$, and $x_n$ is never a square since $q+nm$ cannot be a square. Thus, $2018\mid d(x_n)$. $\square$ Case 2: $p=2$. Let $k=2^{1010}\cdot m$, then take the sequence \[\forall n, x_n = 2^{1008} (3+(4m)n)\]Verify that $x_{n+1}-x_n=k$. Next, we clearly have $v_2(x_n)=1008$, and $3+4mn$ cannot be a square, thus $2018\mid d(x_n)$ and we are done. Alternatively, if $k=2^{1009}\cdot p$, then we may take the sequence \[\forall n, x_n = 2^{1008} (q+(2p)n)\]which also works for some quadratic residue $q$ mod 2p. $\square$ We now show that these are the only solutions. AFTSOC otherwise, write $n=\prod p_i^{1008}$. WLOG we write the progression as $x_n=L(an+d)$ where $\gcd(a,d)=1$ and $k=aL$. Then, due to Dirichlet's, we may find an arbitrarily large $P$ such that $P=an+d, \gcd(p,L)=1$. Then, we have that \[2018\mid d(L\cdot P)\Longrightarrow 1009\mid d(L)\]Thus, if we take the $p$ as the most commonly occuring prime in $L$, then we have that $v_p(L)= 1008$. We now break down into two cases. Similar logic holds for all other $p$, thus $\forall p, v_p(L)\geq v_p(n)\Longrightarrow n\mid L$, so $a=1$. Thus, $x_n = k(n+d)$. At which point, we clearly fail when we choose $n$ such that $\forall p_i$, $v_{p_i}(n+d)=1009-e_i$. Thus, $d(x_n) = 1010^{\text{something}}$, so $x_n$ is not interesting, a contradiction. Finally, we verify $k=2^{1009}$, our sequence must be of the form \[2^i(a + n \cdot 2^{1009-i})\]We must have $i\geq 1008$, and $1009-i\leq 1$, however for both $2^0,2^1$, there are no non-quadratic residues so we will be able to find a square $a + n \cdot 2^{1009-i}$, a contradiction. Thus, we are done $\blacksquare$.

Cool problem. We will solve the problem for any integer of the form $2p$ for some odd prime $p$ (i.e, $1009$ is replaced by $p$ for the remainder of this solution). $\textbf{Lemma 1:}$ There is a prime $q$ such that $v_q(k) \geq p-1$ $\textbf{Proof)}$ Assume FTSOC that for all primes $q$, $v_q(k) < p-1$, if we write the arithmetic progression as $t(ax+b)$ with $a,b,t \in \mathbb{N}$ with $gcd(a,b)$, setting $ax+b$ to be a prime that is relatively prime to $t$ by Dirichlet gives us that $v_q(t(ax+b)) < p-1$ meaning that $p \nmid t(ax+b)$ which is a contradiction. $\square$ $\textbf{Lemma 2:}$ There is a prime $q$ such that $v_q(k) \geq p$ $\textbf{Proof)}$ Assume that for all primes $q$, $v_q(k) \leq p-1$ and let take $p_1,...,p_n$ to be the primes such that $v_{p_i}(t) = v_{p_i}(k) = p-1$. Then for each such prime, take $$n \equiv \frac{-b}{a} \pmod{p_i}$$and notice that if we let $x \rightarrow p_ix+s$ such that $s \equiv \frac{-b}{a} \pmod{p_i}$, then then we get a new arithmetic progression $t(ap_ix+as+b)$ where $gcd(ap_i,as+b) = p_i$ and after factoring out the $p_i$ we again get an arithmetic progression with relatively prime coefficients. Then, we ultimately get an arithmetic progression of the form $tp_1...p_n(a'x+b')$ with $gcd(a',b') = 1$ and setting $a'x+b'$ to be a prime relatively prime to $tp_1...p_n$, we have that $v_q(tp_1...p_n(a'x+b'))$ is either strictly less than $p-1$ or exactly $p$ meaning that $p \nmid d(tp_1...p_n(a'x+b')$, as desired. $\square$ $\textbf{Lemma 3:}$ If there is some prime such that $v_q(k) \geq p$ with $k \neq 2^p$, we can construct an arithmetic progression with common difference $k$ and only $\textit{interesting}$ terms. $\textbf{Proof)}$ Unless $q = 2$, take $t = q^{p-1}$ and $b$ to be a quadratic non-residue $\pmod{q}$. Otherwise, if $v_2(k) \geq p+1$, take $t = 2^{p-1}$ and take $b \equiv 3 \pmod{4}$, otherwise, if there is some prime $p_1 \neq 2$ such that $p_1 \mid k$, then take again take $t = 2^{p-1}$ and take $b$ to be a quadratic non-residue $\pmod{p_1}$. On the other hand notice that, if $k = 2^p$, we must have that $t = 2^{p-1}$ because we know that if we write the arithmetic progression as $t(ax+b)$, then $t$ must be interesting, yet then there will always be a square of the form $2x+b$ meaning that for some $x \in \mathbb{N}$, $2 \nmid d(2^{p-1}(ax+b))$ and consequently such values do not work. $\square$ Combining $\textbf{Lemma 1, Lemma 2}$, and $\textbf{Lemma 3}$, we have that only $k \in \mathbb{N}$ such that there is some prime $q$ with $v_q(k) \geq p$ and $k \neq 2^p$ works. $\blacksquare$

2018 China TST Day 1 Q2 wrote: A number $n$ is interesting if 2018 divides $d(n)$ (the number of positive divisors of $n$). Determine all positive integers $k$ such that there exists an infinite arithmetic progression with common difference $k$ whose terms are all interesting. The only $k$ which work are those which have $\nu_p(k) \ge 1009$ and $k \neq 2^{1009}$ Claim: All numbers of the form $k = (p_1 p_2 \cdots p_k)^{1008}$ don't work. Proof: Let the arithmetic progression be $C(dX+e)$ denoted by the set $S$ Choose $M = \prod_{p \mid k} p^{1009}$ and let $X=p_1^{2007} p_2^{2007}............ \in S$ By Dirchlet's theorem, there exist arbitrarily large numbers of the form $n = q^{10} \gcd(X,M)$ in this sequence, where $q \nmid M$ is prime. Since $\nu_p(n) =1009^k \cdot 11$ for every prime $p$, the number $n$ is not interesting. $\blacksquare$ Claim: $p^{1009}$ works for all $p$ Claim: Let $q$ be a quadratic nonresidue $\pmod{p}$; consider the arithmetic sequence$$p^{1008}(q), p^{1008}(q+p), p^{1008}(q+2p), \dots$$which has common difference $p^{1009}$. Every term $x$ in this sequence has $\nu_p (x)=1008$ and since $q+np$ is never a perfect square for any $n$, the number of factors of $x$ is always a multiple of $2018$ as desired.$\blacksquare$ Claim: $2^{1009}$ doesn't work. Proof: Let the sequence be $a+2^{1009}n$ for $n \in \mathbb{N}$ Let $d=\text{gcd}(a,2^{1009}), \frac{a}{d}=x, \frac{2^{1009}}{d}=y$ the sequence becomes $d(x+yn)$. Since $\text{gcd}(x,y)=1$ by Dirichlet we can pick $n$ such that $x+yn$ is a prime; thus we must have $d=2^{1008}$. However,we have $y=2$ so we can pick $n$ so that $x+yn$ is a perfect square then $d(x+yn)=\text{odd}$,contradiction as desired.

The answer is $\boxed{m \cdot p^{1009}}$ for any prime $p$ and any positive integer $m$, excluding the number $2^{2009}$. Observe that there must exist at least one $p$ such that $\nu_p (a_0) \geq 1008$, where $a_0$ is the first term. Construction. Assume that $p>2$. Take the first term equal to $a_0 = n \cdot p^{1008}$ for any $n > 1$ relatively prime to $p$. Evidently $$\nu_p(a_0+ik) = \nu_p(n \cdot p^{1008} + mi \cdot p^{1009}) = 1008,$$by $\nu_p$ properties. Now $1009 \cdot 2 = 2018 \mid d(a_0+ik)$ for all $i$ because there exists another factor of $a_0+ik$. Now assume $p=2$. $2^{2009}$ fails, because for any term of the form $$a^2 \cdot 2^{2008}$$has $d(n) \equiv 1009 \pmod {2018}$ -- and such terms exist because all odd $a \cdot 2^{2008}$ are in the sequence. For numbers of the form $m \cdot 2^{1009}$ for $m>1$, let the first term be $n \cdot 2^{1008}$ where $n$ is a NQR mod $2m$, which always exists for $m>1$. This trivially works, so we have resolved the $p=2$ case. Proof of Necessity Assume that $\nu_p(k) < 1009$ for all $p$. If $\nu_p(k) < 1008$ for any $p$, then $$\nu_p(a_0 + ik) = \min(\nu_p(a_0), \nu_p(ik)) < 1008$$for any $\gcd(i, p) = 1$ as the index. On the other hand, for all $p$ with $\nu_p(k) = 1008$, we claim there exists some $i$ such that $$\nu_p(a_0+ik) > \min(\nu_p(a_0), \nu_p(ik)) = 1008.$$In particular, Claim. There exists an index $i$ such that $\nu_p(a_0+ik) = 1009$ for all $p$ with $\nu_p(k) = 1008$. Label all such $p$ $p_0, p_1, \cdots, p_n$ for some $n$. If $\nu_{p_j}(a_0) < 1008$, there is nothing to prove. If $\nu_{p_j}(a_0) > 1008$, then take $i \equiv p_j \pmod {p_j^2}$ as the index. If $\nu_{p_j}(a_0) = 1008$, then set $a_0 = p_j^{1008} a_0'$ and $k = p_j^{2008} \cdot k'$ for $k', a_0'$ relatively prime to $p_j$. Then $$\nu_{p_j}(a_0+ik) = \nu_{p_j}(p_j^{1008} (a_0' + ik')) =1009$$must hold, which identifies a class of the $p_j-1$ solutions $$i \equiv r + sp_j \pmod {p^2}$$for $0 \leq r \leq p_j-1$ and any $0 \leq s \leq p_j-1$ that we can pick, excluding the solution which causes $p_j^2 \mid a_0' + ik'$. Combining throughout all $j$, this becomes a system of $n$ congruences wrt $p_0^2, p_1^2, p_2^2$, which has a solution by CRT; hence such an $i$ exists. $\blacksquare$ This means that we can always find a counterexample for any starting $a_0$ and prime $p$, so we are done.

If this solution works, I believe it is the first one in this thread without invoking Dirichlet. The answer is $\boxed{m \cdot p^{1009}}$ for any prime $p$ and any positive integer $m$, excluding the number $2^{2009}$. Observe that there must exist at least one $p$ such that $\nu_p (a_0) \geq 1008$, where $a_0$ is the first term. Construction. Assume that $p>2$. Take the first term equal to $a_0 = n \cdot p^{1008}$ for any $n > 1$ relatively prime to $p$. Evidently $$\nu_p(a_0+ik) = \nu_p(n \cdot p^{1008} + mi \cdot p^{1009}) = 1008,$$by $\nu_p$ properties. Now $1009 \cdot 2 = 2018 \mid d(a_0+ik)$ for all $i$ because there exists another factor of $a_0+ik$. Now assume $p=2$. $2^{2009}$ fails, because for any term of the form $$a^2 \cdot 2^{2008}$$has $d(n) \equiv 1009 \pmod {2018}$ -- and such terms exist because all odd $a \cdot 2^{2008}$ are in the sequence. For numbers of the form $m \cdot 2^{1009}$ for $m>1$, let the first term be $n \cdot 2^{1008}$ where $n$ is a NQR mod $2m$, which always exists for $m>1$. This trivially works, so we have resolved the $p=2$ case. Proof of Necessity. Assume that $\nu_p(k) < 1009$ for all $p$. If $\nu_p(k) < 1008$ for any $p$, then $$\nu_p(a_0 + ik) = \min(\nu_p(a_0), \nu_p(ik)) < 1008$$for any $\gcd(i, p) = 1$ as the index. On the other hand, for all $p$ with $\nu_p(k) = 1008$, we claim there exists some $i$ such that $$\nu_p(a_0+ik) > \min(\nu_p(a_0), \nu_p(ik)) = 1008.$$In particular, Claim. There exists an index $i$ such that $\nu_p(a_0+ik) = 1009$ for all $p$ with $\nu_p(k) = 1008$. Label all such $p$ $p_0, p_1, \cdots, p_n$ for some $n$. If $\nu_{p_j}(a_0) < 1008$, there is nothing to prove. If $\nu_{p_j}(a_0) > 1008$, then take $i \equiv p_j \pmod {p_j^2}$ as the index. If $\nu_{p_j}(a_0) = 1008$, then set $a_0 = p_j^{1008} a_0'$ and $k = p_j^{2008} \cdot k'$ for $k', a_0'$ relatively prime to $p_j$. Then $$\nu_{p_j}(a_0+ik) = \nu_{p_j}(p_j^{1008} (a_0' + ik')) =1009$$must hold, which identifies a class of the $p_j-1$ solutions $$i \equiv r + sp_j \pmod {p^2}$$for $0 \leq r \leq p_j-1$ and any $0 \leq s \leq p_j-1$ that we can pick, excluding the solution which causes $p_j^2 \mid a_0' + ik'$. Combining throughout all $j$, this becomes a system of $n$ congruences wrt $p_0^2, p_1^2, p_2^2$, which has a solution by CRT; hence such an $i$ exists. $\blacksquare$ This means that we can always find a counterexample for any starting $a_0$ and prime $p$, so we are done.

The answer is all positive integers $k$ for which there exists a prime $p$ such that $v_p(k)>1008$ except $2^{1009}$. We have that $2018=2.1009$. Assume that for all $k$ there exists such an arithmetic progression and let $T$ be it's first element, thus all elements are of the form $T+ak$ where $a$ is a non negative integer. Let $d=gcd(T,k)$ thus $T=d.t$; $k=d.k_0$ and $gcd(t,k_0)=1$ and $d$ is a divisor of $k$. Now $T+ak=d(t+ak_0)$ and from Dirichlet's there exists a prime $q$ larger than $d$ of the form $q=t+ak_0$ for some $a$, so we get that $d$ should have a prime divisor $p$ with $v_p(d)=1009k-1$ and thus $v_p(d)> \geq 1008$, thus $k$ should have a prime divisor $p$ with $v_p(k)\geq 1008$ Now I'll prove that it is not possible that for every prime $p$ to have $v_p(k)<1009$. Let $d=p_1^{1008}p_2^{1008}\cdots p_k^{1008}.x$ and $k_0=y$, where we have that for every prime $q$ $v_q(x)<1008$; also $gcd(y,t)=gcd(y,p_1p_2\cdots p_k)=1$. Now $$T+ak=d(t+ak_0)=p_1^{1008}p_2^{1008}\cdots p_k^{1008}.x(t+ay)$$Now let $x$ be an integer such that $t+xy\equiv 0 (mod p_1p_2\cdots p_k)$, which exists because $ay$ goes trough all residues $(mod p_1p_2\cdots p_k)$. Now let $a=bp_1p_2\cdots p_k +x$ for an integer $b$ which we can vary. Now $$t+ay=t+byp_1p_2\cdots p_k+xy=t+xy+byp_1p_2\cdots p_k=p_1p_2\cdots p_k(\frac{t+xy}{p_1p_2\cdots p_k}+by)$$Now since $gcd(t+xy,y)=gcd(t,y)=1$ we have by Dirichlet that there exists a prime $q>k$ such that $q=\frac{t+xy}{p_1p_2\cdots p_k}+by$ for some $b$ $\Leftrightarrow$ There exists an integer $a$ for which $t+ay=qp_1p_2\cdots p_k$. But this integer can't be interesting$\Leftrightarrow $ In order for an integer $k$ to satisfy the criteria there should be a prime $p$ such that $v_p(k)>1008$. Now if $p>2$ pick $d=p^{1008}$ and let $k_0=px$. Now $$T+ak=p^{1008}(t+apx)$$Pick a $t$ such that $t$ is equivalent to a non quadratic residue $mod$ $p$ and $t\equiv 1$ $mod$ every prime divisor of $k$ different than $p$. This assures us that $p$ doesn't divide $t+apx$ and $t+apx$ is never a square(because of $mod$ $p$),thus all integers in this arithmetic progression are interesting. Now if $p=2$ and $k$ has some other prime divisor $q$ and $d=2^{1008}; k = 2^{1009}qx$ , then $$T+ak=2^{1008}(t+a2qx)$$Now we can choose $t$ by CRT such that $t$ is equivalent to a non quadratic residue mod $q$ and $gcd(t,k)=1$, so $t+a2qx$ is never a perfect square and it's not divisible by 2, so this works. Now if the only prime dividing $k$ is $2$ we have that if $v_2(k)\geq 1010$ by picking $d=2^{1008} $ and $t\equiv 3(mod$ $4)$ we can guarantee that $t+ak_0$ is never a square and it's not divisible by $2$, so all such numbers work. If $k=2^{1009}$ we should have $d=2^{1009}$ and $k_0=2$, but then $t+a2$ is going to be a perfect square and $2018$ won't divide $d(2^{1009}(t+2a))$, so $k=2^{1009}$ doesn't work and we're done!

Here's an elementary solution without Dirichilet which uses size in NT (we will bound stuff).

Assume $v_p(k) \le 1008$ for all primes $p$ and FTSOC assume $k$ is interesting. Observe $2018 = 2 \cdot 1009$ and $1009$ is a prime. Suppose $a_1,a_2,\ldots$ was the arithmetic progression. For each $a_i$, let $p_i$ be a prime satisfying $1009 \mid v_{p_i} (a_i) + 1$. Claim: For each $p \mid k$, $\exists ~ c$ such that if $i \equiv c \pmod{p^2}$, then $p_i \ne p$. Proof: Let $v_p(k) = e_1 \le 1008$ and $v_p(a_1 - k) = e_2$. We have several cases: $e_1 > e_2$. As then $e_2 < 1008$, so any $c$ works. $e_1 = e_2$. If $1008 \nmid e_2 + 1$ then $c = p$ works. Otherwise, a appropriate $c$ can be chosen so that $v_p(a_i)$ for $i \equiv c$ is $e_1 + 1$. $e_2 > e_1$. If $1008 \nmid e_1 + 1$, then any $c$ not divisible by $p$ works. Otherwise, if $e_2 = e_1 + 1$ then $c=0$ works and if $e_2 \ge e_1 + 2$ then $c = p$ works. This proves our claim. $\square$ Now by CRT, we can find a constant $m$ such that all of $p_m,p_{m+n},p_{m + 2n},\ldots$ are co prime to both $k,n$, where $$n = \prod_{p \mid k} p^2$$Define $q_i = p_{m + n(i-1)} ~ \forall ~ i \ge 1$ and $k ' = k \cdot n$. Observe that: $q_i^{1008} \le l + k' \cdot i$ for all $i$, where $l$ is some fixed constant. If $q_i = q_j = q$, then $q^{1008} \mid n(i - j) \implies q^{1008} \mid i-j$ (as $\gcd(q,n) = 1$), in particular $|i - j| \ge q^{1008}$. Now for a sufficiently large $s$, look at the set $$X = \{q_1,q_2,\ldots,q_{s^{1007}} \}$$By first condition, all elements of $X$ are $\le s$. For each $j \in \{2,3,\ldots,s\}$, denote by $b_j$ the number of time $j$ occurs in $X$. By second condition we must have $$(b_j - 1) \cdot j^{1008} \le s^{1007} \qquad \forall~ 2 \le j \le s$$But we also have $b_2 + b_3 + \cdots + b_s = s^{1007}$. This gives \begin{align*} s^{1007} - s &\le \sum_{j=2}^s (b_j - 1) \le \sum_{j=2}^s \frac{s^{1007}}{j^{1008}} \end{align*}So to obtain our contradiction, it suffices to show $\displaystyle \sum_{j \ge 2} \frac{1}{j^{1008}} < 1 - \epsilon$ for some fixed $\epsilon > 0$. This just follows by $\frac{1}{1^2} + \frac{1}{2^2} + \cdots = \frac{\pi^2}{6}$. But for an elementary proof, note \begin{align*} \sum_{j \ge 2} \frac{1}{j^{1008}} &\le \sum_{j \ge 2} \frac{1}{j^3} = \sum_{i \ge 1} \left( \sum_{j=2^i}^{2^{i+1}} \frac{1}{j^3} \right) \le \sum_{i \ge 1} \left( \frac{2^i}{2^{3i}} \right) = \sum_{i \ge 1} \frac{1}{4^i} = \frac{1}{3} \end{align*}So we obtain our desired contradiction, completing the proof. $\blacksquare$

Here's a solution that uses bullet points three times! The answer is all $k$ such that there exists a $p$ with $\nu_p(k) \geq 1009$, except for $k=2^{1009}$. Call a number satisfying the (arithmetic progression) condition good, and call it bad otherwise. Note that if a number of good, so is any multiple of it, so if a number is bad, all divisors of it are bad too. Further, $k$ is bad if and only if every residue class of $k$ contains arbitrarily large uninteresting numbers. Finally, note that $1009$ is prime. To begin, we prove that all of the claimed numbers are good: If $p>2$, it suffices to show that $p^{1009}$ is good. Let $r$ be an NQR modulo $p$. Then every number $n \equiv rp^{1008} \pmod{p^{1009}}$ has $\nu_p(n)=1008$, so $1009 \mid d(n)$. Also, $\tfrac{n}{p^{1008}}$ is never a square (else $r$ is a quadratic residue), hence $n$ isn't either so $2 \mid d(n)$. Combined these imply $2018 \mid d(n)$ as advertised. For $p=2$, $k=2^{1009}p$ is good for all $p \neq 2$. Again, take $r$ to be an NQR modulo $p$, and let $n$ satisfy $n \equiv 2^{1008} \pmod{2^{1009}}$ and $n \equiv r \pmod{p}$. Then for mod $p$ reasons $n$ is never a square, and we also have $\nu_2(n)=1008$, so $2018 \mid d(n)$. Also for $p=2$, $k=2^{1010}$ is good for all $p$ by taking $n \equiv 3\cdot 2^{1008} \pmod{2^{1010}}$. This works as $\nu_2(n)=1008$, so $n=2^{1008}(4k+3)$, and $4k+3$ is never a square so $2 \mid d(n)$. Most of the rest of the problem is resolved with the following claim. Claim: For any distinct primes $p_1,\ldots,p_k$, $N=(p_1\ldots p_k)^{1008}$ is bad. Proof: Let $1 \leq r \leq N$ and consider the residue class $r \pmod{N}$. Let $M=(p_1\ldots p_k)^{1010}$, and consider the residue class $c \pmod{M}$ satisfying (by Chinese Remainder Theorem): For all primes $p_i$ such that $\nu_{p_i}(r)<1008$, let $c \equiv r \pmod{p_i^{1010}}$. Clearly $c \equiv r \pmod{p_i^{1008}}$ as well. For all primes $p_i$ such that $\nu_{p_i}(r)\geq 1008$, let $c \equiv p_i^{1009} \pmod{p_i^{1010}}$. Then $c \equiv r \equiv 0 \pmod{p_i^{1008}}$. This implies that the residue class $c \pmod{M}$ is a subset of the residue class $r \pmod{N}$. By Dirichlet, there exist arbitrarily large elements of this residue class that are $n=q \cdot \gcd(c,M)$ where $q \nmid M$ is a prime. Since $\nu_{p_i}(c) \in \{0,\ldots,1007,1009\}$, $\nu_{p_i}(M)=1010$, and there are no other primes dividing $M$, it follows that any prime $p \mid n$ satisfies $\nu_p(n) \not \equiv -1 \pmod{1009}$, hence $1009 \nmid d(n)$. It then follows that $n$ is uninteresting, so $N$ is bad as desired. All that remains is to show that $2^{1009}$ is bad. We split this into three cases based on the residue of $n$: For $n \equiv 0 \pmod{2^{1009}}$, take $n=2^{1009i}$, so $1009 \nmid d(n)=1009i+1$. For $n \equiv 2^{1008} \pmod{2^{1009}}$, we can write $n=2^{1008}(2k+1)$. Taking $2k+1$ to be some arbitrarily large square (which trivially exists) makes $n$ a square as well, whence $2 \nmid d(n)$. Otherwise, let $\nu_2(n)=a \leq 1008$, and let $n'=\tfrac{n}{2^a}$. Then we can write $n=2^a(2^{1009-a}k+n')$. If $a \geq 1$, we can apply the above claim (since there exist arbitrarily large $n$ with $1009 \nmid d(n)$). Otherwise $a=0$, and we can get $n$ to equal arbitrarily large primes, in which case $1009 \nmid d(n)=2$. Combined, these cases imply that $2^{1009}$ is bad as desired, so we obtain the solution set as described. $\blacksquare$

We uploaded our solution https://calimath.org/pdf/ChinaTST2018-2.pdf on youtube https://youtu.be/Ci8d0jYGuzc.

The answer is $k$ such that there exist $p$ such that $\nu_{p}(k) \ge 1009$ and $\frac{k}{p^{1008}} \neq 1, 2$, i.e $k \neq 2^{1009}$. Firstly, we'll construct such arithmetic progression for such $k$. Let $a$ be a first number of the arithmetic progress. Take $a = p^{1008} \cdot b$, where $b$ satisfies $(\frac{b}{p}) = -1$. Then the $n$th number of the arithmetic progression is $p^{1008}(b + \frac{k}{p^{1008}}n)$.Since $b + \frac{k}{p^{1008}}n$ isn't divisible by $p$ and $(b + \frac{k}{p^{1008}}n)$ isn't perfect square, so $2018 \mid d(p^{1008}(b + \frac{k}{p^{1008}}n))$. Now we'll prove that there exist $p$ such that $\nu_{p}(k) \ge 1009$. Let $a$ be first number of the arithmetic progression. Then by Dirichlet's theorem, there exists $n$ such that $\frac{a}{\gcd(a, k)} + \frac{kn}{\gcd(a, k)}$ is prime. Thus $2018 \mid 2d(\gcd(a, k))$, so $1009 \mid \gcd(a, k)$. Therefore there exists prime $p$ such that $\nu_p(k) \ge 1008$. Assume $\nu_p(k) = 1008$. Let $\gcd(a, k) = p^{1008}\cdot d$ and $a_1 = \frac{a}{\gcd(a, k)}$ and $k_1 = \frac{k}{\gcd(a, k)}$. Then take $r$ such that $\nu_p(a_1 + k_1n) = 1$. By Dirichlet's theorem, there exists $n$ such that $a_1 + k_1(r + p^2n) = pq$ for some prime $q$. Thus $d(a + k(r + p^2n))$ isn't divisible by $2018$, a contradiction. Thus there exists $p$ such that $\nu_p(k) \ge 1009$. And it's not hard to check that $2^{1009}$ isn't the answer. This completes proof. $\blacksquare$

$ $

We claim the answer is all $k$ such that $v_pk \ge 1009$ some prime $p$ except $k = 2^{1009}$. Suppose our starting term is $a$: Construction: Factor each term as \[a+kn = p^{1008}(p^{v_pk-1008}+a').\] Suppose we set $a'$ to be a NQR modulo $p$ if $p$ odd or a NQR modulo 4 if working with $v_2k \ge 1010$. The two factors are relatively prime, and since all squares have an even number of divisors, \[d(a+kn) = d(p^{1008}) \cdot d(p^{v_pk-1008}+a') = 1009 \cdot \text{even} \equiv 0 \pmod{2018}.\] Counterexample: Our first case otherwise is to eliminate the case $k = 2^{1009}$, which is easy using casework on $v_pa$ and factoring out $2^{1009-v_pa}$. Otherwise, we must have $n = \prod p_i^{e_i} \mid \pi p_i{1008}$. Suppose $\gcd(a,n) = \prod p_i^{f_i}$. If we factor out $\gcd(a,n)$ from $a+kn$, we have two factors which are sometimes coprime but sometimes share prime factors $p_i$ through CRT. It's easy to use this to our advantage to show that we have some term whose divisor count is not a multiple of 1009 using casework on whether we have some $f_i = e_i = 1008$ or not. $\blacksquare$

MERRY CHRISTMAS !!! We claim that all possible $k$ must have an odd prime $p$ such that $p^{1009}$ divides $k$, be divisible by $2^{2010}$, or be able to be written in the form $ q \cdot 2^{2009}$ where $q$ is has an odd prime divisor. For a construction if an odd prime $p$ exists such that $p^{1009}$ divides $k$ take an NQR modulo $p$ call it $b$ and make the sequence $a_n = b\cdot p^{1008} + nk$. If $k$ is divisible by $2^{1010}$ take the sequence $a_n = 3 \cdot 2^{1008} + nk$. If $k = q \cdot 2^{2009}$ take an NQR for some odd prime that divides $q$ call it $c$ take the sequence $a_n = c \cdot 2^{1008} + kn$, unless $c$ is even then increase it by that odd prime amount. Now if $\nu_p (k ) \le 1008$ for all prime $p$. Then each term of the arithmetic sequence isn't divisible by $p$ or there exist periodic terms with period $p^{2010-\nu_p (k)}$ such that $\nu_p (k) =1009$. By infinite CRT there exists a term that satisfies one of these properties for each prime $p$, a contradiction because if this was true then $d(\text{that term}) =1010^z$ for some $z$ which contains no factors of $1009$. If $k=2^{1009}$ then obviously every term of the sequnce must be in the for $a_n = \text{odd} \cdot 2^{1008} + 2^{1009}n = 2^{1008}(\text{odd}+2n)$ for each odd there exists a value of $n$ such that $a_n$ is a square so $d(a_n) \equiv 1 \pmod{2}$ a contradiction and we are done.