Call a positive integer $k$ $\textit{pretty}$ if for every positive integer $a$, there exists an integer $n$ such that $n^2+n+k$ is divisible by $2^a$ but not $2^{a+1}$. Find the remainder when the $2021$st pretty number is divided by $1000$.

[i]Proposed by i3435[/i]
To solve the problem, we need to determine the conditions under which a positive integer \( k \) is considered "pretty." Specifically, for every positive integer \( a \), there must exist an integer \( n \) such that \( n^2 + n + k \) is divisible by \( 2^a \) but not \( 2^{a+1} \).

1. **Evenness of \( k \)**:
   - First, observe that \( n^2 + n \) is always even because \( n(n+1) \) is the product of two consecutive integers, one of which is always even.
   - Therefore, \( k \) must be even for \( n^2 + n + k \) to be even. Let \( k = 2m \) for some integer \( m \).

2. **Valuation of \( n^2 + n + k \)**:
   - Let \( \nu_2(x) \) denote the 2-adic valuation of \( x \), i.e., the highest power of 2 dividing \( x \).
   - We need to show that for every \( a > 0 \), there exists an \( n \) such that \( \nu_2(n^2 + n + k) = a \).

3. **Transformation and Induction**:
   - Consider \( n^2 + n + k \equiv 0 \pmod{2^a} \). This implies \( n^2 + n \equiv -k \pmod{2^a} \).
   - If \( n \) satisfies this congruence, then \( (n + 2^a)^2 + (n + 2^a) + k \equiv n^2 + n + k + 2^{a+1}n + 2^{2a} + 2^a \equiv 2^a(2n + 1) + 2^{2a} \pmod{2^{a+1}} \).
   - Since \( 2^{2a} \equiv 0 \pmod{2^{a+1}} \), we have \( (n + 2^a)^2 + (n + 2^a) + k \equiv 2^a(2n + 1) \pmod{2^{a+1}} \).

4. **Existence of \( n \)**:
   - If \( n^2 + n + k \equiv 0 \pmod{2^{a+1}} \), then \( (n + 2^a)^2 + (n + 2^a) + k \equiv 2^a \pmod{2^{a+1}} \).
   - This shows that if \( \nu_2(n^2 + n + k) > a \) for some \( n \), we can find an \( n \) such that \( \nu_2(n^2 + n + k) = a \).

5. **Conclusion**:
   - The only constraint on \( k \) is that it must be even. Therefore, the sequence of pretty numbers is simply the sequence of even positive integers: \( 2, 4, 6, 8, \ldots \).

6. **Finding the 2021st Pretty Number**:
   - The 2021st even number is \( 2 \times 2021 = 4042 \).

7. **Remainder Calculation**:
   - The remainder when 4042 is divided by 1000 is \( 4042 \mod 1000 = 42 \).

The final answer is \(\boxed{42}\).