We find all the values of k when x³+x+k is reducible
and subtract from 1000.

If x³+x+k is reducible over the polynomials
with integer coefficients, then it is factorable as
the product of a linear binomial and a quadratic
trinomial both with leading coefficients 1.  That
is, integers A,B,C exist such that:

x³+x+k = (x+A)(x²+Bx+C)

Multiplying the right side out we get

         (x+A)(x²+Bx+C) = x³+(A+B)x²+(AB+C)x+AC

So we have the identity:

x³+(A+B)x²+(AB+C)x+AC ≡ x³+x+k 
  
So we can equate coefficients:

(1)     A+B= 0
(2)   AB+C = 1
(3)     AC = k

So from (1), B = -A, and substituting for B in (2),

A(-A)+C = 1
  -A²+C = 1
(4)   C = A²+1

So the factorization

x³+x+k = (x+A)(x²+Bx+C)

becomes

x³+x+k = (x+A)(x²-Ax+A²+1)

Substituting for C from (4), in (3),

A(A²+1) = k
   A³+A = k

Since  1 ≤ k ≤ 1000

1 ≤ A³+A ≤ 1000

A³+A is a strictly increasing function, therefore:

The minimum value of A is 1, when k = A³+A = 1³+1 = 1+1 = 2, and
The maximum value of A is 9, when k = A³+A = 9³+9 = 729+9 = 738.
(For when A = 10, k = A³+A = 10³+10 = 1000+10 = 1010, which is
over 1000.)

So there are 9 values of A, 1 through 9, and therefore 9  
factorizations which are:
 
For k = 1, (x³+x+2) =(x+1)(x²-x+2)
For k = 2, (x³+x+10) =(x+2)(x²-2x+5)
For k = 3, (x³+x+30) =(x+3)(x²-3x+10)
For k = 4, (x³+x+68) =(x+4)(x²-4x+17)
For k = 5, (x³+x+130) =(x+5)(x²-5x+26)
For k = 6, (x³+x+222) =(x+6)(x²-6x+37)
For k = 7, (x³+x+350) =(x+7)(x²-7x+50)
For k = 8, (x³+x+520) =(x+8)(x²-8x+65)
For k = 9, (x³+x+738) =(x+9)(x²-9x+82)

Since for only 9 positive integers 1 ≤ k ≤ 1000, the 
polynomial f_k(x)=x³+x+k is reducible, then for the other
1000-9 or 991 positive integers 1 ≤ k ≤ 1000, the 
polynomial f_k(x)=x³+x+k is irreducible.

Answer: 991

Edwin