A shift and reduce

Any integer $N$ betwen $1$ and $\tfrac{1}{2}(3^7-1) = 1093$ can be written uniquely in fhe form $N \; = \; \sum_{j=0}^6 a_j 3^j$ where each $a_j$ is one of $1$ , $0$ or $-1$ . Thus the polynomial $f(x) \; = \; -\sum_{j=0}^6 a_j x^j$ has degree at most $6$ . Since $a_j \in \{-1,0,1\}$ for all $j$ , it is clear that the sum of the moduli of the coefficients of $f(x)$ is at most $7$ . Finally $f(3) + N = 0$ , and hence $x-3$ is a factor of $f(x) + N$ .

Provided that $N \ge 5$ the above decomposition for $N$ requires the presence of $3^2$ or a higher power of $3$ , and so this polynomial $f(x) + N$ is at least quadratic, and hence reducible. The polynomial $f(x)+N$ is linear or constant (so zero) when $1 \le N \le 4$ , since $2=3-1$ , $4=3+1$ . However, putting $f(x) = x^2-N$ enables us to find a suitable polynomial $f(x)$ such that $f(x)+N=x^2$ is reducible when $1 \le N \le 4$ .

Thus the condition can be satisfied for all integers $1 \le N \le 999$ .

Every integer can be written uniquely as a linear combination of powers of 3 with coefficients $-1, 0, 1$ . (This follows by induction using the fact that if $x$ is between $3^n$ and $3^{n+1}$ , then exactly one of $3^{n+1}-x$ and $x -3^n$ is less than $3^n$ .)

If $N$ is a positive integer less than $1094$ , we can use this to construct a polynomial $f$ with degree at most six such that $f(3) = -N$ . So $f(x) + N$ will have a root, hence will be reducible over the integers if its degree is at least 2.

But the only $N$ for which its degree is less than 2 are $0, 1, 2, 3, 4$ , and these are handled separately by the polynomials $f(x) = -x^2 + (N-1)x$ .