Say a positive integer $n>1$ is $d$-coverable if for each non-empty subset $S\subseteq \{0, 1, \ldots, n-1\}$, there exists a polynomial  $P$ with integer coefficients and degree at most $d$ such that $S$ is exactly the set of residues modulo $n$ that $P$ attains as it ranges over the integers. For each $n$, find the smallest $d$ such that $n$ is $d$-coverable, or prove no such $d$ exists.

[i]Proposed by Carl Schildkraut[/i]
1. **Define the problem and initial observations:**
   We need to determine the smallest degree \( d \) such that for each non-empty subset \( S \subseteq \{0, 1, \ldots, n-1\} \), there exists a polynomial \( P \) with integer coefficients and degree at most \( d \) such that \( S \) is exactly the set of residues modulo \( n \) that \( P \) attains as it ranges over the integers.

2. **Case \( n = 4 \):**
   - Singletons can be covered by constant polynomials.
   - The set \( \{a, b\} \) can be covered by \( (a-b)X^2 + b \).
   - The set \( \{0, 1, 2, 3\} \) is covered by \( X \).
   - The set \( \{0, 1, 3\} \) can be covered by \( X^3 \), and we can take \( X^3 + a \) to get all sets of size 3.
   - It is easy to check that \( \{0, 1, 3\} \) cannot be covered by a degree two polynomial, so \( d = 3 = n-1 \) for this case.

3. **Case \( n = p \) where \( p \) is a prime:**
   - We show how to get sets of the form \( \{0 < a_1 < a_2 < \cdots < a_m < p\} \), and the rest can be obtained by adding a constant to \( P \).
   - Let
     \[
     P(X) = \sum_{i=1}^m a_i (1 - (X-i)^{p-1}).
     \]
   - We see that \( P(i) \equiv a_i \pmod{p} \), and \( P(x) \equiv 0 \pmod{p} \) if \( x \not\equiv i \pmod{p} \) for some \( 1 \le i \le m \), so this works.

4. **Case \( n \) has at least two prime factors:**
   - Let \( n = p_1^{e_1} \cdots p_r^{e_r} \).
   - Suppose \( P(X) \) covers \( (\mathbb{Z}/n\mathbb{Z}) \setminus \{0\} \). Then, there is an \( x_i \) so that \( P(x_i) \equiv p_i^{e_i} \pmod{n} \).
   - Let \( x \equiv x_i \pmod{p_i^{e_i}} \) for all \( i \) (existence is guaranteed by the Chinese Remainder Theorem).
   - We see that \( P(x) \equiv 0 \pmod{p_i^{e_i}} \) for all \( i \), so again by the Chinese Remainder Theorem, we have \( P(x) \equiv 0 \pmod{n} \), a contradiction, as desired.

5. **Case \( n = p^e \) for \( n \ne 4 \):**
   - We'll look at the set \( \{0, 1, \ldots, p\} \).
   - Suppose \( P \) existed that covered this set. By shifting the input, we may assume without loss of generality that \( P(0) = 0 \).
   - We now see that \( P(x) \equiv 0 \pmod{p} \) if and only if \( x \equiv 0 \pmod{p} \), since \( P \) is a surjective function mod \( p \).
   - Thus, letting \( X = pY \), we have \( P(X) = apY \) for some \( a \).
   - If \( a \equiv 0 \pmod{p} \), then this never attains \( p \), and if \( a \not\equiv 0 \pmod{p} \), then this attains \( 2p \) as well, which is a problem for \( n \ne 4 \). Thus, we have the desired contradiction.

6. **Conclusion:**
   - For \( n = 4 \) and \( n \) prime, the answer is \( d = n-1 \).
   - For all other \( n \), such \( d \) does not exist.

The final answer is \( \boxed{ d = n-1 } \) for \( n = 4 \) or \( n \) prime, and no such \( d \) exists otherwise.