I'm interested in generalizing OEIS sequence A329479:
Number of degree $d$ polynomials $f$ with all nonzero coefficients equal to $1$ such that $f(k)$ is divisible by $3$ for all integers $k$.
In particular, I'm looking for a way to compute $$ c(n,d) = \#\{f(x) = x^{a_1} + \cdots + x^{a_m} \mid d = a_1 > \cdots > a_m \text{ and } n \text{ divides } f(k) \text{ for all } k \in \mathbb Z\}, $$ the number of $(0,1)$-polynomials of degree $d$ that are divisible by $n$ when evaluated for every input.
Polynomial ring over $\mathbb Z/n\mathbb Z$.
I think that the "correct" way to look at this is by counting polynomials $f \in \mathbb Z/n\mathbb Z[x]$ such that all coefficients of $f$ are in $\{0, 1\} \subset \mathbb Z/n\mathbb Z$ and $f(0) = f(1) = \dots = f(n-1) = 0$.
If we write $f(x) = x^{a_1} + x^{a_2} + \cdots + x^{a_m}$ with $d = a_1 > a_2 > \cdots > a_m$, then two simple observations are:
- The $f(0) = 0$ condition implies that $a_m \geq 1$.
- The $f(1) = 0$ condition means that $n \mid m$.
Of course, if $0, 1, \dots, n - 1$ are roots of $f(x)$, then $$ f(x) = \underbrace{x(x + 1)(x + 2)\cdots (x + n - 1)}_{h_n(x)}g(x), $$ so it is equivalent to find the number of polynomials $g$ of degree $d - n$ such that $h_n(x)g(x)$ has all coefficients in $\{0, 1\}$.
Small values of $n$.
$c(2,d) = 2^{d-2}$ for $d \geq 2$, and $c(3,d) = A329479(d)$, which can be computed efficiently via the formulas in the OEIS entry.